方法二：归并排序
注意边界条件是i == m, j == n
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
| class Solution {
public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
List<int[]> list = new ArrayList<>();
int i = 0, j = 0, m = nums1.length, n = nums2.length;
while (true) {
if (i == m) {
while (j < n)
list.add(nums2[j++]);
break;
}
if (j == n) {
while (i < m)
list.add(nums1[i++]);
break;
}
if (nums1[i][0] < nums2[j][0])
list.add(nums1[i++]);
else if (nums1[i][0] > nums2[j][0])
list.add(nums2[j++]);
else {
nums1[i][1] += nums2[j++][1];
list.add(nums1[i++]);
}
}
return list.toArray(new int[list.size()][]);
}
}
|
方法一：TreeMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int[] arr : nums1)
map.put(arr[0], map.getOrDefault(arr[0], 0) + arr[1]);
for (int[] arr : nums2)
map.put(arr[0], map.getOrDefault(arr[0], 0) + arr[1]);
int[][] res = new int[map.size()][2];
int index = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
res[index][0] = entry.getKey();
res[index++][1] = entry.getValue();
}
return res;
}
}
|
方法二：记忆化搜索
考虑将每个lowerbit +1或者-1操作，取最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int minOperations(int num) {
dp = new int[Integer.toBinaryString(num).length()];
return dfs(num);
}
private int dfs(int num) {
if (Integer.bitCount(num) == 0)
return 0;
int lowerbit = num & -num;
return Math.min(dfs(num + lowerbit), dfs(num - lowerbit)) + 1;
}
int[] dp;
}
|
base case 可以换成以下形式，如果num & (num - 1)) == 0,那么num是2的幂次，等价于Integer.bitCount(num) == 1
1
2
| if ((num & (num - 1)) == 0)
return 1;
|
方法一：贪心
从前往后遍历(遍历顺序无所谓)，将连续的1分段加入treemap中，
- 如果一段后一段第一个元素与前一段最后一个元素的下标差为2（前一个1与后一个1中间只隔了1个0），先++res
- 如果前一段只有一个元素，不与下一段合并
- 否则，与下一段合并，把flag置为true
- 如果一段后一段第一个元素与前一段最后一个元素的下标差>2
- 如果第一段只有一个元素，并且前一段不和当前第一段合并，那么++res
- 否则，上一段是需要和这一段合并的，res+=2（将最低位+1，比如111 -> 1000，再将这个1减去，两次操作），并将flag还原为false
最开始 s = s + "000";是为了最后遍历的时候，不用再考虑最后一段
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
| class Solution {
public int minOperations(int num) {
if (num == 1)
return 1;
String s = Integer.toBinaryString(num);
s = s + "000";
int res = 0, n = s.length();
TreeMap<Integer, Integer> map = new TreeMap<>();
int preIndex = 0;
for (int i = 0; i < n - 1; ++i) {
char ch1 = s.charAt(i), ch2 = s.charAt(i + 1);
if (ch1 == '1' && preIndex == i)
map.put(i, i);
if (ch1 == '1' && ch2 == '1') {
map.put(preIndex, i + 1);
} else if (ch1 == '0') {
preIndex = i + 1;
}
}
int[][] arr = new int[map.size() + 1][2];
int index = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
arr[index][0] = entry.getKey();
arr[index++][1] = entry.getValue();
}
int i;
boolean flag = false;
for (i = 0; i < arr.length - 1; ++i) {
int[] a = arr[i], b = arr[i + 1];
int len1 = a[1] - a[0];
if (b[0] - a[1] == 2) {
++res;
if (len1 > 0)
flag = true;
} else {
if (len1 == 0 && !flag)
++res;
else {
res += 2;
flag = false;
}
}
}
return res;
}
}
|
方法一：