本期总结：
- 注意拓扑排序的板子，别写错了重复判断的问题，别瞎搞一个inCount[i] = -1这种，不如老实弄个vis
6160. 和有限的最长子序列 - 力扣（LeetCode）
排个序就好了，没啥难的
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;
}
}
|