最长交替子序列
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
| class Solution {
public int alternatingSubarray(int[] nums) {
int res = -1;
for (int i = 0; i < nums.length - 1; ++i) {
int pre = -1;
for (int j = i + 1; j < nums.length; ++j) {
if (pre == -1) {
if (nums[j] - nums[j - 1] == 1) {
res = Math.max(res, j - i + 1);
pre = 1;
}
else
break;
}
else if (pre == 1) {
if (nums[j] - nums[j - 1] == -1) {
res = Math.max(res, j - i + 1);
pre = -1;
}
else
break;
}
else {
break;
}
}
}
return res;
}
}
|
分组循环
重新放置石块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public List<Integer> relocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int x : nums)
map.put(x, map.getOrDefault(x, 0) + 1);
for (int i = 0; i < moveFrom.length; ++i) {
int from = moveFrom[i], to = moveTo[i];
int fromNum = map.get(from);
map.remove(from);
map.put(to, map.getOrDefault(to, 0) + fromNum);
}
List<Integer> res = new LinkedList<>();
for (int key : map.keySet())
res.add(key);
return res;
}
}
|
将字符串分割为最少的美丽子字符串
方法一：记忆化搜索
题目中有：全部不满足情况下返回-1时，要重视dfs里res的初始化， -inf, inf等，根据具体要求具体分析
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 int minimumBeautifulSubstrings(String s) {
int a = (int) Math.pow(2, 15);
set = new HashSet<>();
for (int i = 0; i <= a; ++i) {
int num = (int) Math.pow(5, i);
if (num > a)
break;
set.add(Integer.toBinaryString(num));
}
int res = dfs(s, 0);
return res == Integer.MAX_VALUE / 2 ? -1 : res;
}
Set<String> set;
Map<Integer, Integer> map = new HashMap<>();
private int dfs(String s, int index) {
if (index == s.length()) {
return 0;
}
if (map.containsKey(index))
return map.get(index);
int res = Integer.MAX_VALUE / 2;
for (int i = index; i < s.length(); ++i) {
if (s.charAt(index) == '0')
break;
String sub = s.substring(index, i + 1);
int splitNum = 0;
if (set.contains(sub)) {
splitNum += dfs(s, i + 1) + 1;
res = Math.min(res, splitNum);
}
}
map.put(index, res);
return res;
}
}
|
方法二：记忆化搜索 预处理
预处理部分放在静态块里，只会执行一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class Solution {
static Set<String> set;
static {
int a = (int) Math.pow(2, 15);
set = new HashSet<>();
for (int i = 0; i <= a; ++i) {
int num = (int) Math.pow(5, i);
if (num > a)
break;
set.add(Integer.toBinaryString(num));
}
}
public int minimumBeautifulSubstrings(String s) {
return -1;
}
|
黑格子的数目
方法一：Map
题解
res[0] = (m - 1L) * (n - 1) - sum; 1L转成long避免m，n太大
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 long[] countBlackBlocks(int m, int n, int[][] coordinates) {
Map<String, Integer> map = new HashMap<>();
int[][] dirs = new int[][]{{-1, -1}, {-1, 0}, {0, -1}, {0, 0}};
for (int[] arr : coordinates) {
for (int[] dir : dirs) {
int row = arr[0] + dir[0], col = arr[1] + dir[1];
if (row >= 0 && col >= 0 && row < m - 1 && col < n - 1) {
String rc = row + "-" + col;
map.put(rc, map.getOrDefault(rc, 0) + 1);
}
}
}
long[] res = new long[5];
long sum = 0;
for (int val : map.values()) {
++res[val];
++sum;
}
res[0] = (m - 1L) * (n - 1) - sum;
return res;
}
}
|