Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb31f305

Browse files
authored
Improved tasks 999, 1825, 3425
1 parent093a41b commitb31f305

File tree

5 files changed

+167
-275
lines changed

5 files changed

+167
-275
lines changed
Lines changed: 44 additions & 80 deletions
Original file line numberDiff line numberDiff line change
@@ -1,97 +1,61 @@
11
packageg0901_1000.s0999_available_captures_for_rook;
22

3-
// #Easy #Array #Matrix #Simulation #2022_03_31_Time_0_ms_(100.00%)_Space_41.8_MB_(28.74%)
3+
// #Easy #Array #Matrix #Simulation #2025_03_13_Time_0_ms_(100.00%)_Space_40.75_MB_(94.97%)
44

55
@SuppressWarnings("java:S135")
66
publicclassSolution {
7-
privateint[]directions =newint[] {0,1,0, -1,0};
8-
97
publicintnumRookCaptures(char[][]board) {
10-
intm =board.length;
11-
intn =board[0].length;
12-
introwR = -1;
13-
intcolR = -1;
14-
for (inti =0;i <m;i++) {
15-
for (intj =0;j <n;j++) {
8+
// Find the position of the rook
9+
introokRow = -1;
10+
introokCol = -1;
11+
for (inti =0;i <8;i++) {
12+
for (intj =0;j <8;j++) {
1613
if (board[i][j] =='R') {
17-
rowR =i;
18-
colR =j;
14+
rookRow =i;
15+
rookCol =j;
1916
break;
2017
}
2118
}
22-
}
23-
int[]count = {0};
24-
for (inti =0;i <4;i++) {
25-
intneighborRow =rowR +directions[i];
26-
intneighborCol =colR +directions[i +1];
27-
if (neighborRow >=0
28-
&&neighborRow <m
29-
&&neighborCol >=0
30-
&&neighborCol <n
31-
&&board[neighborRow][neighborCol] !='B') {
32-
if (directions[i] ==0 &&directions[i +1] ==1) {
33-
extracted(board,n,count,neighborRow,neighborCol);
34-
}elseif (directions[i] ==1 &&directions[i +1] ==0) {
35-
extracted1(board,m,count,neighborRow,neighborCol);
36-
}elseif (directions[i] ==0 &&directions[i +1] == -1) {
37-
extracted(board,count,neighborRow,neighborCol);
38-
}else {
39-
extracted1(board,count,neighborRow,neighborCol);
40-
}
41-
}
42-
}
43-
returncount[0];
44-
}
45-
46-
privatevoidextracted(char[][]board,int[]count,intneighborRow,intneighborCol) {
47-
while (neighborCol >=0) {
48-
if (board[neighborRow][neighborCol] =='p') {
49-
count[0]++;
50-
break;
51-
}elseif (board[neighborRow][neighborCol] =='B') {
52-
break;
53-
}else {
54-
neighborCol--;
55-
}
56-
}
57-
}
58-
59-
privatevoidextracted(char[][]board,intn,int[]count,intneighborRow,intneighborCol) {
60-
while (neighborCol <n) {
61-
if (board[neighborRow][neighborCol] =='p') {
62-
count[0]++;
63-
break;
64-
}elseif (board[neighborRow][neighborCol] =='B') {
65-
break;
66-
}else {
67-
neighborCol++;
68-
}
69-
}
70-
}
71-
72-
privatevoidextracted1(char[][]board,int[]count,intneighborRow,intneighborCol) {
73-
while (neighborRow >=0) {
74-
if (board[neighborRow][neighborCol] =='p') {
75-
count[0]++;
19+
if (rookRow != -1) {
7620
break;
77-
}elseif (board[neighborRow][neighborCol] =='B') {
78-
break;
79-
}else {
80-
neighborRow--;
8121
}
8222
}
83-
}
84-
85-
privatevoidextracted1(char[][]board,intm,int[]count,intneighborRow,intneighborCol) {
86-
while (neighborRow <m) {
87-
if (board[neighborRow][neighborCol] =='p') {
88-
count[0]++;
89-
break;
90-
}elseif (board[neighborRow][neighborCol] =='B') {
91-
break;
92-
}else {
93-
neighborRow++;
23+
// Define the four directions: up, right, down, left
24+
int[][]directions = {
25+
// up
26+
{-1,0},
27+
// right
28+
{0,1},
29+
// down
30+
{1,0},
31+
// left
32+
{0, -1}
33+
};
34+
intcaptureCount =0;
35+
// Check each direction
36+
for (int[]dir :directions) {
37+
introw =rookRow;
38+
intcol =rookCol;
39+
while (true) {
40+
// Move one step in the current direction
41+
row +=dir[0];
42+
col +=dir[1];
43+
// Check if out of bounds
44+
if (row <0 ||row >=8 ||col <0 ||col >=8) {
45+
break;
46+
}
47+
// If we hit a bishop, we're blocked
48+
if (board[row][col] =='B') {
49+
break;
50+
}
51+
// If we hit a pawn, we can capture it and then we're blocked
52+
if (board[row][col] =='p') {
53+
captureCount++;
54+
break;
55+
}
56+
// Otherwise (empty square), continue in the same direction
9457
}
9558
}
59+
returncaptureCount;
9660
}
9761
}
Lines changed: 50 additions & 121 deletions
Original file line numberDiff line numberDiff line change
@@ -1,141 +1,70 @@
11
packageg1801_1900.s1825_finding_mk_average;
22

33
// #Hard #Design #Heap_Priority_Queue #Ordered_Set #Queue
4-
// #2022_05_06_Time_83_ms_(60.59%)_Space_96.3_MB_(77.83%)
4+
// #2025_03_13_Time_37_ms_(100.00%)_Space_100.84_MB_(46.09%)
55

6-
importjava.util.ArrayDeque;
7-
importjava.util.Deque;
8-
importjava.util.TreeMap;
6+
importjava.util.LinkedList;
7+
importjava.util.TreeSet;
98

10-
@SuppressWarnings("java:S2184")
119
publicclassMKAverage {
12-
privatefinaldoublem;
13-
privatefinaldoublek;
14-
privatefinaldoublec;
15-
privatedoubleavg;
16-
privatefinalBstmiddle;
17-
privatefinalBstmin;
18-
privatefinalBstmax;
19-
privatefinalDeque<Integer>q;
10+
privatefinalintcapacity;
11+
privatefinalintboundary;
12+
privatefinalint[]nums;
13+
privatefinalTreeSet<Integer>numSet;
14+
privatefinalLinkedList<Integer>order;
2015

2116
publicMKAverage(intm,intk) {
22-
this.m =m;
23-
this.k =k;
24-
this.c =m -k *2;
25-
this.avg =0;
26-
this.middle =newBst();
27-
this.min =newBst();
28-
this.max =newBst();
29-
this.q =newArrayDeque<>();
17+
this.capacity =m;
18+
this.boundary =k;
19+
nums =newint[100001];
20+
numSet =newTreeSet<>();
21+
order =newLinkedList<>();
3022
}
3123

3224
publicvoidaddElement(intnum) {
33-
if (min.size <k) {
34-
min.add(num);
35-
q.offer(num);
36-
return;
37-
}
38-
if (max.size <k) {
39-
min.add(num);
40-
max.add(min.removeMax());
41-
q.offer(num);
42-
return;
43-
}
44-
45-
if (num >=min.lastKey() &&num <=max.firstKey()) {
46-
middle.add(num);
47-
avg +=num /c;
48-
}elseif (num <min.lastKey()) {
49-
min.add(num);
50-
intval =min.removeMax();
51-
middle.add(val);
52-
avg +=val /c;
53-
}elseif (num >max.firstKey()) {
54-
max.add(num);
55-
intval =max.removeMin();
56-
middle.add(val);
57-
avg +=val /c;
58-
}
59-
60-
q.offer(num);
61-
62-
if (q.size() >m) {
63-
num =q.poll();
64-
if (middle.containsKey(num)) {
65-
avg -=num /c;
66-
middle.remove(num);
67-
}elseif (min.containsKey(num)) {
68-
min.remove(num);
69-
intval =middle.removeMin();
70-
avg -=val /c;
71-
min.add(val);
72-
}elseif (max.containsKey(num)) {
73-
max.remove(num);
74-
intval =middle.removeMax();
75-
avg -=val /c;
76-
max.add(val);
25+
if (order.size() ==capacity) {
26+
intnumToDelete =order.removeFirst();
27+
nums[numToDelete] =nums[numToDelete] -1;
28+
if (nums[numToDelete] ==0) {
29+
numSet.remove(numToDelete);
7730
}
7831
}
32+
nums[num]++;
33+
numSet.add(num);
34+
order.add(num);
7935
}
8036

8137
publicintcalculateMKAverage() {
82-
if (q.size() <m) {
83-
return -1;
84-
}
85-
return (int)avg;
86-
}
87-
88-
staticclassBst {
89-
TreeMap<Integer,Integer>map;
90-
intsize;
91-
92-
publicBst() {
93-
this.map =newTreeMap<>();
94-
this.size =0;
95-
}
96-
97-
voidadd(intnum) {
98-
intcount =map.getOrDefault(num,0) +1;
99-
map.put(num,count);
100-
size++;
101-
}
102-
103-
voidremove(intnum) {
104-
intcount =map.getOrDefault(num,1) -1;
105-
if (count >0) {
106-
map.put(num,count);
107-
}else {
108-
map.remove(num);
38+
if (order.size() ==capacity) {
39+
intskipCount =boundary;
40+
intnumsCount =capacity -2 *boundary;
41+
intfreq =capacity -2 *boundary;
42+
intsum =0;
43+
for (intnum :numSet) {
44+
intcount =nums[num];
45+
if (skipCount <0) {
46+
sum +=num *Math.min(count,numsCount);
47+
numsCount -=Math.min(count,numsCount);
48+
}else {
49+
skipCount -=count;
50+
if (skipCount <0) {
51+
sum +=num *Math.min(Math.abs(skipCount),numsCount);
52+
numsCount -=Math.min(Math.abs(skipCount),numsCount);
53+
}
54+
}
55+
if (numsCount ==0) {
56+
break;
57+
}
10958
}
110-
size--;
111-
}
112-
113-
intremoveMin() {
114-
intkey =map.firstKey();
115-
116-
remove(key);
117-
118-
returnkey;
119-
}
120-
121-
intremoveMax() {
122-
intkey =map.lastKey();
123-
124-
remove(key);
125-
126-
returnkey;
127-
}
128-
129-
booleancontainsKey(intkey) {
130-
returnmap.containsKey(key);
131-
}
132-
133-
intfirstKey() {
134-
returnmap.firstKey();
135-
}
136-
137-
intlastKey() {
138-
returnmap.lastKey();
59+
returnsum /freq;
13960
}
61+
return -1;
14062
}
14163
}
64+
65+
/*
66+
* Your MKAverage object will be instantiated and called as such:
67+
* MKAverage obj = new MKAverage(m, k);
68+
* obj.addElement(num);
69+
* int param_2 = obj.calculateMKAverage();
70+
*/

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp