[toc]
第一题简单dfs
LCP 44. 开幕式焰火 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
Set<Integer> set = new HashSet<>();
public int numColor(TreeNode root) {
dfs(root);
return set.size();
}
void dfs(TreeNode node) {
if (node == null) {
return;
}
set.add(node.val);
dfs(node.left);
dfs(node.right);
}
}
|
第二题-记忆化搜索
473. 火柴拼正方形 - 力扣（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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
public boolean makesquare(int[] matchsticks) {
int sum = Arrays.stream(matchsticks).sum();
if (sum % 4!=0) {
return false;
}
int[] vis = new int[matchsticks.length];
Arrays.fill(vis,1);
return dfs(vis,
matchsticks, new HashSet<>(), 0, sum/4);
}
boolean dfs(int[] vis, int[] matchsticks, Set<Integer> set, int nowSum, int target) {
int k = 1;
int sum = 0;
for (int v :vis) {
sum += v * k;
k*=2;
}
if (nowSum == target) {
nowSum = 0;
} else if(nowSum > target) {
set.add(sum);
return false;
}
if (nowSum == 0 && sum == 0) {
return true;
}
if (set.contains(sum)) {
return false;
}
for (int i = 0; i < matchsticks.length;i++) {
if (vis[i] == 0) {
continue;
}
vis[i] = 0;
if(dfs(vis, matchsticks, set, nowSum + matchsticks[i], target)) {
return true;
}
vis[i] = 1;
}
set.add(sum);
return false;
}
}
|
实际上不需要考虑某个火柴放在第0个边还是第4个边，直接按边摆
当你用了第1、3、7、9个火柴时，可以直接尝试往边上拼，正好拼满一个边就下一个
dp[状态压缩标志位]表示当前正在摆的那个边的长度
第三题 枚举回文数，只要枚举前一半
906. 超级回文数 - 力扣（LeetCode）
18位回文数，但又要求是回文数的平方
所以开根号的值是9位， 且必须是回文数
那么9位回文数，最多只要求 前4位的数字，加中间可有可无的一个数字即可。
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
58
59
60
| class Solution {
public int superpalindromesInRange(String left, String right) {
dfs(0, new StringBuilder());
Long leftNum = Long.valueOf(left);
Long rightNum = Long.valueOf(right);
int leftIndex = -1;
int rightIndex = -1;
res.add(1L);
res.add(4L);
res.add(9L);
List<Long> list = new ArrayList<>(res);
Collections.sort(list);
System.out.println(list);
for (int i = 0;i < res.size(); i++) {
if (leftIndex == -1 && leftNum<= list.get(i)) {
leftIndex = i;
}
if (rightIndex == -1 && rightNum <= list.get(i)) {
rightIndex = i;
break;
}
}
if (rightIndex == -1) {
rightIndex = list.size();
}
System.out.println("right=" + rightIndex + ";left=" + leftIndex);
return rightIndex - leftIndex;
}
Set<Long> res = new HashSet<>();
void dfs(int index, StringBuilder sb) {
if (index == 4) {
String s = Integer.valueOf(sb.toString()).toString();
if (s.equals("0")) {
return;
}
for (char i = '0'; i <='9';i++) {
String newS = s + i + new StringBuilder(s).reverse().toString();
doPalid(newS);
}
String newS = s + new StringBuilder(s).reverse().toString();
doPalid(newS);
return;
}
for (char i = '0'; i <='9';i++) {
dfs(index+1, sb.append(i));
sb.deleteCharAt(sb.length()-1);
}
}
public void doPalid(String newS) {
Long newNum = Long.valueOf(newS);
Long mulNum = newNum * newNum;
String mulNumS = String.valueOf(mulNum);
if (mulNumS.equals(new StringBuilder().append(mulNumS).reverse().toString())) {
res.add(mulNum);
}
}
}
|