AlgorithmNormal

不知道分到哪里的一般题

890. 查找和替换模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 这个方法挺不错的,使用
class Solution {
public int findPairs(int[] nums, int k) {
Set<Integer> visited = new HashSet<Integer>();
Set<Integer> res = new HashSet<Integer>();
for (int num : nums) {
if (visited.contains(num - k)) {
res.add(num - k);
}
if (visited.contains(num + k)) {
res.add(num);
}
visited.add(num);
}
return res.size();
}
}

532. 数组中的 k-diff 数对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 方法一,用map存储nums-k和nums+k
class Solution {
public int findPairs(int[] nums, int k) {
Set<Integer> visited = new HashSet<Integer>();
Set<Integer> res = new HashSet<Integer>();
for (int num : nums) {
if (visited.contains(num - k)) {
res.add(num - k);
}
if (visited.contains(num + k)) {
res.add(num);
}
visited.add(num);
}
return res.size();
}
}

// 方法二:使用排序+双指针,两个指针是从left=0和right=left+1开始的

954. 二倍数对数组

特别注意treemap的ans比较中的问题,-1和1是等于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
class Solution {
public boolean canReorderDoubled(int[] arr) {
// Map<Integer, Integer> map = new TreeMap<>((a, b) -> Math.abs(a) - Math.abs(b));
// 特别注意,上面这个判断,Math.abs会影响treemap对key的判断的
// 因为本来-1和1,绝对值相减=0,会误认为是同一个元素值???
Map<Integer, Integer> map = new TreeMap<>((a,b)->Math.abs(a)==Math.abs(b) ? a-b : Math.abs(a)-Math.abs(b));

for (int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}

// 0只有跟自己对应
if (map.getOrDefault(0, 0) % 2 != 0) { return false; }
map.remove(0);

for (Integer key : map.keySet()) {
int value = map.getOrDefault(key, 0);
int value2 = map.getOrDefault(key * 2, 0);

if (value2 < value) { return false; }

// 此处map不能在添加新的元素,否则在for循环会有问题的
if (value2 != 0) {
map.put(key * 2, value2 - value);
}
}

return true;
}
}

Author: Jcwang

Permalink: http://example.com/2022/06/16/AlgorithmNormal/