本期总结：
- bfs时，必须要记得在对第一个入队节点做vis[start]=true的操作！否则一定会导致WA！
算术三元组的数目 - 力扣 (LeetCode) 竞赛
直接3个for循环搞定
受限条件下可到达节点的数目 - 力扣 (LeetCode) 竞赛
这么简单的bfs题竟然错了一次（用bfs是因为节点数量很多有10^5个）
因为bfs时忘了对第一个入队节点做vis[起点] = true;的操作， 直接导致错失前200
另外这题甚至不应该思考， 直接开写才对
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
| class Solution {
public static List<Integer>[] edgToNextNodeLists(int n, int[][] edges) {
List<Integer>[] list = new List[n];
for (int i = 0;i<n;i++) {
list[i] = new ArrayList<>();
}
for (int[] edg : edges) {
int s = edg[0];
int e = edg[1];
list[s].add(e);
list[e].add(s);
}
return list;
}
public int reachableNodes(int n, int[][] edges, int[] restricted) {
List<Integer>[] nextNodes = edgToNextNodeLists(n, edges);
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
Set<Integer> resSet = Arrays.stream(restricted).boxed().collect(Collectors.toSet());
boolean[] vis = new boolean[n];
int count = 0;
vis[0] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
count++;
for (int nextNode : nextNodes[node]) {
if (vis[nextNode] || resSet.contains(nextNode)) {
continue;
}
queue.offer(nextNode);
vis[nextNode] = true;
}
}
return count;
}
}
|
检查数组是否存在有效划分 - 力扣 (LeetCode) 竞赛
可检查范围最多就3个，如果[4,5,6]如果符合，那我只要检查4前面那个数字是否有符合的划分，划分可以传递，因此直接动态规划即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public boolean validPartition(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
for (int i = 0; i < nums.length;i++) {
int num = nums[i];
if (i-1>=0 && nums[i-1] == num) {
dp[i] |= (i-2>=0?dp[i-2] : true);
}
if (i-2>=0 && nums[i-1] == num && nums[i-2] == num) {
dp[i] |= (i-3>=0?dp[i-3] : true);
}
if (i-2>=0 && nums[i-1] == num-1 && nums[i-2] == num-2) {
dp[i] |= (i-3>=0?dp[i-3] : true);
}
}
return dp[n-1];
}
|
最长理想子序列 - 力扣 (LeetCode) 竞赛
显然是动态规划， 在[a-z]中找到符合k差值的字母， 根据字母已记录的最长子序列长度，进行+1即可。
最开始想歪了，想成了k是位置距离了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int longestIdealString(String s, int k) {
int n = s.length();
int[] dp = new int[26];
for (int i = 0; i < s.length();i++) {
int c = s.charAt(i) - 'a';
int max = Integer.MIN_VALUE;
for (int lastc = c-k;lastc <= c+k;lastc++) {
if (lastc < 0 || lastc > 25) {
continue;
}
max = Math.max(max, dp[lastc] + 1);
}
dp[c] = max;
}
return Arrays.stream(dp).max().getAsInt();
}
}
|