本期总结：
- 滑动窗口最大值，一定要用过期有限队列
2395. 和相等的子数组 - 力扣（LeetCode）
直接哈希表，但是要处理long的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public boolean findSubarrays(int[] nums) {
Set<Long> map = new HashSet<>();
for (int i = 0; i < nums.length;i++) {
if (i + 1 < nums.length) {
int j = i + 1;
if(map.contains((long)nums[i] + nums[j])) {
return true;
}
map.add((long) (nums[i] + nums[j]));
}
}
return false;
}
}
|
2396. 严格回文的数字 - 力扣（LeetCode）
还好，不需要考虑回文比较的性能，直接统计每个数字即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public boolean isStrictlyPalindromic(int n) {
int m = n - 2;
for (int i = 2; i <= n-2;i++) {
int num = n;
StringBuilder sb = new StringBuilder();
while (num > 0) {
sb.append(num % i);
num /= i;
}
String s1 = sb.toString();
String s2 = sb.reverse().toString();
if (!s1.equals(s2)) {
return false;
}
}
return true;
}
}
|
2397. 被列覆盖的最多行数 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int maximumRows(int[][] mat, int cols) {
dfs(mat, cols, 0, new boolean[mat[0].length]);
return maxCount;
}
int maxCount = 0;
public void dfs(int[][] mat, int colRealCount, int colIndex, boolean[] select) {
if (colRealCount == 0) {
int count = 0;
for(int y = 0;y<mat.length;y++) {
boolean flag = true;
for (int x = 0; x < mat[0].length;x++) {
if (mat[y][x] == 1 && !select[x]) {
flag =false;
break;
}
}
if (flag) {
count++;
}
}
maxCount = Math.max(maxCount, count);
return;
}
for (int col = colIndex;col < mat[0].length;col++) {
select[col] = true;
dfs(mat, colRealCount-1, col+1, select);
select[col] = false;
}
}
}
|
直接dfs即可
2398. 预算内的最多机器人数目 - 力扣（LeetCode）
没有做完就总结， 已经忘记当时为什么11点30就提交了第一次，然后改了半个小时也没搞定。。
好像是因为 我要求的应该是滑动窗口的最大值以及滑动窗口的总和， 然而最大值那个好像搞错了，应该要引入过期队列的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
int[][] array = new int[chargeTimes.length][2];
for (int i = 0; i < chargeTimes.length;i++) {
array[i] = new int[]{chargeTimes[i], runningCosts[i]};
}
int left = 0, right = runningCosts.length+1;
while (left < right) {
int mid = left + (right - left) / 2;
int queueCount = mid - 1;
int k = mid;
if (mid == 0) {
return 0;
}
long sum = 0;
boolean flag = false;
Queue<int[]> queue = new PriorityQueue<>((a,b)->(b[1]-a[1]));
for (int i = 0 ; i < array.length;i++) {
sum += array[i][1];
queue.offer(new int[]{i, array[i][0]});
if ( i < mid - 1) {
continue;
}
while (!queue.isEmpty() && queue.peek()[0] < i - queueCount) {
queue.poll();
}
int max = queue.peek()[1];
long ksum = sum ;
long buck = max + k * ksum;
if (buck <= budget) {
flag = true;
break;
}
sum -= array[i - queueCount][1];
}
if(flag) {
left = mid+1;
} else {
right = mid;
}
}
return Math.max(0, left-1);
}
}
|
排个序就好了，没啥难的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
Arrays.sort(nums);
int[] res = new int[queries.length];
for (int i = 0; i < queries.length;i++) {
int sum = 0;
int len = 0;
for (int j = 0;j<nums.length;j++) {
if (sum + nums[j] > queries[i]) {
break;
}
sum += nums[j];
len++;
}
res[i] = len;
}
return res;
}
}
|
6161. 从字符串中移除星号 - 力扣（LeetCode）
既然每次要移除最左边， 我就从右往左边遍历， 碰到星号，说明下次碰到字母时要变星号，记录一个数字即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public String removeStars(String s) {
boolean[] bs = new boolean[s.length()];
int needDeduceCount = 0;
for (int i = s.length()-1;i>=0;i--) {
if (s.charAt(i) == '*') {
needDeduceCount++;
bs[i] = true;
} else if (needDeduceCount > 0) {
needDeduceCount--;
bs[i] = true;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length();i++) {
if (bs[i]) {
continue;
}
sb.append(s.charAt(i));
}
return sb.toString();
}
}
|
6162. 收集垃圾的最少总时间 - 力扣（LeetCode）
这种题目啥情况，啥算法也不用，直接3次遍历即可，主要是得计算到最后一个有这个垃圾的房子时就要截至了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int garbageCollection(String[] garbage, int[] travel) {
char[] cs = new char[]{'G', 'P', 'M'};
int res = 0;
for (char c : cs) {
int sum = 0;
int realSum = 0;
for (int i = 0; i < garbage.length; i++) {
String garba = garbage[i];
int count = 0;
for (char g : garba.toCharArray()) {
if (g == c) {
count++;
}
}
if (count > 0) {
sum += count;
realSum = sum;
}
if (i != garbage.length-1) {
sum += travel[i];
}
}
res += realSum;
}
return res;
}
}
|
6163. 给定条件下构造矩阵 - 力扣（LeetCode）
想了半太天才意识到是拓扑排序， 越是叶子的，越可以放前面， 越是根的，越可以放后面
早点想到的话应该20分钟就做出来了，拓扑还是很简单的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class Solution {
public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
int[] rows = new int[k+1];
int[] cols = new int[k+1];
if (!sort(k, rowConditions, rows)
|| !sort(k, colConditions, cols)) {
return new int[][]{};
}
int[][] res = new int[k][k];
for (int i = 1; i <=k;i++) {
res[rows[i]][cols[i]] = i;
}
return res;
}
private boolean sort(int k, int[][] rowConditions, int[] rows) {
int[] inCount = new int[k+1];
List<Integer>[] outLists = new List[k+1];
for (int i = 1; i <=k;i++) {
outLists[i] = new ArrayList();
}
for (int[] row : rowConditions) {
inCount[row[1]]++;
outLists[row[0]].add(row[1]);
}
int y = 0;
boolean[] vis = new boolean[k+1];
while (true) {
int i;
for (i = 1; i <= k; i++) {
if (inCount[i] > 0 || vis[i]) {
continue;
}
vis[i] = true;
for (int out : outLists[i]) {
inCount[out]--;
}
rows[i] = y;
y++;
break;
}
if(i == k+1) {
break;
}
}
for (int i = 1;i<=k;i++) {
if (inCount[i] >0) {
return false;
}
}
return true;
}
}
|