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
| class Solution {
public int deleteAndEarn(int[] nums) {
Map<Integer, Integer> numPointMap = new HashMap<>();
for (int num : nums) {
numPointMap.put(num, numPointMap.getOrDefault(num, 0) + num);
}
List<Map.Entry<Integer, Integer>> numPointPairList = new ArrayList<>(numPointMap.entrySet());
Collections.sort(numPointPairList, (a, b) -> Integer.compare(a.getKey(), b.getKey()));
int first = 0, second = numPointPairList.get(0).getValue();
for (int i = 1; i < numPointPairList.size(); i++) {
int currNum = numPointPairList.get(i).getKey(), currValue = numPointPairList.get(i).getValue();
int lastNum = numPointPairList.get(i - 1).getKey();
if (currNum - 1 != lastNum) {
int currMax = currValue + second;
first = second;
second = currMax;
} else {
int currMax = Math.max(currValue + first, second);
first = second;
second = currMax;
}
}
return second;
}
}
|
House Robber的变体. 我们先把取每个num能得到的score存到一个map中. 比如[2, 3, 3, 3, 4]. 取2的话能得到2, 取3的话能得到9(尽管消除了2和4). 取4得到4. 这里存的只是取某个数字取尽后得到的score. 然后我们根据num大小sort一下. 这样就变成了House Robber. 如果两个num相邻, 那么其实就是house robber, 如果不相邻, 那么直接连着取.
时间复杂度: O(n + klogk) k是distinct num的个数.
空间复杂度: O(k + logk) -> O(k) 因为用map存数据, list存数据, 排序.
