forked from fishercoder1534/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
_740.java
62 lines (58 loc) · 2.23 KB
/
_740.java
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
61
62
package com.fishercoder.solutions;
import java.util.TreeMap;
public class _740 {
public static class Solution1 {
/**
* Since the number is within range [1, 10000], we can build another array:
* each number in the array denotes the total sum of this number that appears in this array
* and
* use the numbers themselves in the indices of another array
* <p>
* credit: https://leetcode.com/problems/delete-and-earn/discuss/109895/JavaC++-Clean-Code-with-Explanation
* <p>
* Notes:
* 1. In essence, this is the same as House Robber: https://leetcode.com/problems/house-robber/
* 2. We are adding the number itself into values, instead of its frequency because we will directly use this value to compute the result
*/
public int deleteAndEarn(int[] nums) {
int n = 10001;
int[] values = new int[n];
for (int num : nums) {
values[num] += num;
}
int take = 0;
int skip = 0;
for (int i = 0; i < n; i++) {
int takeI = skip + values[i];
int skipI = Math.max(skip, take);
take = takeI;
skip = skipI;
}
return Math.max(take, skip);
}
}
public static class Solution2 {
/**
* A simplified version using treemap instead of an array, credit: https://leetcode.com/problems/delete-and-earn/discuss/109895/JavaC++-Clean-Code-with-Explanation/111626
*/
public int deleteAndEarn(int[] nums) {
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
for (int num : nums) {
treeMap.put(num, treeMap.getOrDefault(num, 0) + num);
}
int prev = 0;
int curr = 0;
for (int key : treeMap.keySet()) {
if (!treeMap.containsKey(key - 1)) {
prev = curr;
curr += treeMap.get(key);
} else {
int tmp = Math.max(prev + treeMap.get(key), curr);
prev = curr;
curr = tmp;
}
}
return curr;
}
}
}