add 740

fishercoder1534 · fishercoder1534 · commit 33ca06e80b27 · 2018-03-18T16:23:25.000-07:00
diff --git a/README.md b/README.md
@@ -47,6 +47,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |747|[Largest Number Greater Than Twice of Others](https://leetcode.com/problems/largest-number-greater-than-twice-of-others/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_747.java) | O(n) | O(1) | |Easy|
 |746|[Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_746.java) | O(n) | O(1) | |Easy|
 |744|[Find Smallest Letter Greater Than Target](https://leetcode.com/problems/find-smallest-letter-greater-than-target/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_744.java) | O(logn) | O(1) || Easy|
+|740|[Delete and Earn](https://leetcode.com/problems/delete-and-earn/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_740.java) | O(n) | O(n) | |Medium|
 |739|[Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_739.java) | O(n^2) | O(1) | |Medium| 
 |738|[Monotone Increasing Digits](https://leetcode.com/problems/monotone-increasing-digits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_738.java) | O(n) | O(1) | |Medium|
 |737|[Sentence Similarity II](https://leetcode.com/problems/sentence-similarity-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_737.java) | O(nlogk + k) n is the length of max(words1, words2), k is the length of pairs| O(k) | |Medium| Union Find
diff --git a/src/main/java/com/fishercoder/solutions/_740.java b/src/main/java/com/fishercoder/solutions/_740.java
@@ -0,0 +1,56 @@
+package com.fishercoder.solutions;
+
+/**
+ * 740. Delete and Earn
+ *
+ * Given an array nums of integers, you can perform operations on the array.
+ * In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.
+ * You start with 0 points. Return the maximum number of points you can earn by applying such operations.
+
+ Example 1:
+ Input: nums = [3, 4, 2]
+ Output: 6
+ Explanation:
+ Delete 4 to earn 4 points, consequently 3 is also deleted.
+ Then, delete 2 to earn 2 points. 6 total points are earned.
+
+ Example 2:
+ Input: nums = [2, 2, 3, 3, 3, 4]
+ Output: 9
+ Explanation:
+ Delete 3 to earn 3 points, deleting both 2's and the 4.
+ Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
+ 9 total points are earned.
+
+ Note:
+ The length of nums is at most 20000.
+ Each element nums[i] is an integer in the range [1, 10000].*/
+
+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
+     *
+     * credit: https://leetcode.com/problems/delete-and-earn/discuss/109895/JavaC++-Clean-Code-with-Explanation*/
+    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);
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_740Test.java b/src/test/java/com/fishercoder/_740Test.java
@@ -0,0 +1,29 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._740;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _740Test {
+  private static _740.Solution1 solution1;
+  private static int[] nums;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _740.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    nums = new int[] {3, 4, 2};
+    assertEquals(6, solution1.deleteAndEarn(nums));
+  }
+
+  @Test
+  public void test2() {
+    nums = new int[] {2, 2, 3, 3, 3, 4};
+    assertEquals(9, solution1.deleteAndEarn(nums));
+  }
+}
