本期总结：
- bfs时，必须要记得在对第一个入队节点做vis[start]=true的操作！否则一定会导致WA！
矩阵中的局部最大值 - 力扣 (LeetCode) 竞赛
直接硬写即可，就是写8个方向的dirs数组比较累
https://leetcode.cn/contest/weekly-contest-306/problems/node-with-highest-edge-score/
看起来也很简单， 遍历一次就等得到所有点的积分了，然后再遍历一次得到最大节点（都不用写sort函数，直接遍历求最大值即可）
比较坑的是相加结果会超int。。。。
-
2 <= n <= 10^5
O(n^2)会超int范围，一定要注意
Arrays.sort不支持直接long类型
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int edgeScore(int[] edges) {
long[][] counts = new long[edges.length][2];
for (int i = 0; i < edges.length;i++) {
counts[edges[i]][0] += i;
counts[edges[i]][1] = edges[i];
}
Arrays.sort(counts, (a,b)->(a[0] != b[0] ? (b[0] - a[0] > 0?1:-1) : (a[1] - b[1] > 0 ? 1 : -1)));
return (int)counts[0][1];
}
}
|
6150. 根据模式串构造最小数字 - 力扣（LeetCode）
我竟然一时无法冷静，看最多就9位，只想到了dfs，然后写了15分钟。。正确答案肯定不是dfs这么蠢的
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
| class Solution {
public String smallestNumber(String pattern) {
int[] nums = new int[]{1,2,3,4,5,6,7,8,9};
for (int i = 1; i <=9; i++) {
List<Integer> rest = new ArrayList<>();
Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
rest.add(i);
set.remove(i);
dfs(pattern, rest, set,0);
}
return min;
}
String min = null;
public void dfs(String p, List<Integer> res, Set<Integer> canSelect,int i) {
if (i == p.length()) {
String s = res.stream().map(r -> String.valueOf(r)).collect(Collectors.joining());
if (min == null || s.compareTo(min) < 0) {
min = s;
}
return;
}
int now = res.get(res.size()-1);
char sort = p.charAt(i);
Set<Integer> copySet = new HashSet<>(canSelect);
for (int select : copySet) {
if (sort == 'I') {
if (select < now) {
continue;
}
} else {
if (select > now) {
continue;
}
}
canSelect.remove(select);
res.add(select);
dfs(p, res, canSelect, i+1);
canSelect.add(select);
res.remove(res.size()-1);
}
}
}
|
最佳做法肯定是一次遍历搞定
有个规律
III的时候，就是选取当前最小值，逐步递增
当DDD的时候， 则应该是从DDD的最右边选当前最小值，逐步往左边递增
处理完DDD的时候更新最小值
结果这个处理也很恶心，写死我了
后来想到每次只判断I这个字母前面所存的数字，后面数字存疑
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
| public String smallestNumber(String pattern) {
int[] results = new int[pattern.length()+1];
int num = 1;
int ri = 0;
for (int i= 0; i < pattern.length();i++) {
if (pattern.charAt(i) == 'I') {
results[ri++] = num++;
} else if (pattern.charAt(i) == 'D') {
int right = i;
while (right+1 < pattern.length() && pattern.charAt(right+1) == 'D') {
right++;
}
int desLen = right - i + 1;
int highNum = num + desLen;
while (desLen-- > 0) {
results[ri++] = highNum--;
}
results[ri++] = num;
num = num + (right - i + 1) + 1;
i = right+1;
}
}
if (results[results.length-1] == 0) {
results[results.length-1] = num;
}
return Arrays.stream(results).boxed().map(r->r.toString()).collect(Collectors.joining());
}
|
6151. 统计特殊整数 - 力扣（LeetCode）
排列组合题
处理0的时候很恶心
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
55
56
57
| class Solution {
public int countSpecialNumbers(int n) {
String s = String.valueOf(n);
int[] nums = new int[s.length()];
for (int i = 0;i<nums.length;i++){
nums[i] = s.charAt(i) - '0';
}
boolean[] select = new boolean[10];
int canSelectCount = 10;
int result = 0;
int i = 0;
boolean flag = false;
for ( i = 0; i < s.length();i++) {
int nowCanSelect = 0;
for (int j = 0;j<nums[i];j++) {
if (!select[j]) {
nowCanSelect++;
}
}
if (i==0) {
nowCanSelect--;
}
if (!flag) {
int r = nowCanSelect * getSum(canSelectCount - 1, s.length() - i - 1);
result += r;
}
if (i > 0) {
int newR = 9*getSum(9, s.length()-i-1);
result += newR;
}
canSelectCount --;
if (select[nums[i]]) {
flag = true;
}
select[nums[i]] = true;
}
if (!flag) {
result++;
}
return result;
}
int getSum(int n, int count) {
int sum = 1;
while (count>0) {
sum *= n;
count--;
n--;
}
return sum;
}
}
|
暂存以下数位DP，后面做一下强化以下
