feat: update solutions to lc problem: No.0740. Delete and Earn

yanglbme · yanglbme · commit e816450dd965 · 2021-07-07T20:12:25.000+08:00
diff --git a/README.md b/README.md
@@ -164,6 +164,7 @@
 - [使用最小花费爬楼梯](./solution/0700-0799/0746.Min%20Cost%20Climbing%20Stairs/README.md)
 - [打家劫舍](./solution/0100-0199/0198.House%20Robber/README.md)
 - [打家劫舍 II](./solution/0200-0299/0213.House%20Robber%20II/README.md)
+- [删除并获得点数](./solution/0700-0799/0740.Delete%20and%20Earn/README.md)
 - [接雨水](./solution/0000-0099/0042.Trapping%20Rain%20Water/README.md)
 - [最大子序和](./solution/0000-0099/0053.Maximum%20Subarray/README.md)
 - [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
diff --git a/README_EN.md b/README_EN.md
@@ -158,6 +158,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
 - [Min Cost Climbing Stairs](./solution/0700-0799/0746.Min%20Cost%20Climbing%20Stairs/README_EN.md)
 - [House Robber](./solution/0100-0199/0198.House%20Robber/README_EN.md)
 - [House Robber II](./solution/0200-0299/0213.House%20Robber%20II/README_EN.md)
+- [Delete and Earn](./solution/0700-0799/0740.Delete%20and%20Earn/README_EN.md)
 - [Trapping Rain Water](./solution/0000-0099/0042.Trapping%20Rain%20Water/README_EN.md)
 - [Maximum Subarray](./solution/0000-0099/0053.Maximum%20Subarray/README_EN.md)
 - [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
diff --git a/solution/0100-0199/0198.House Robber/README.md b/solution/0100-0199/0198.House Robber/README.md
@@ -86,22 +86,14 @@ public:
 class Solution {
 public:
     int rob(vector<int>& nums) {
-        int n;
-        if ((n = nums.size()) == 0) return 0;
-        return robRange(nums, 0, n - 1);
-    }
-
-private:
-    int robRange(vector<int>& nums, int start, int end) {
-        if (end - start == 0) return nums[start];
-        int pre = 0;
-        int cur = nums[start];
-        for (int i = start + 1; i < end + 1; ++i) {
-            int t = max(pre + nums[i], cur);
-            pre = cur;
-            cur = t;
+        int n = nums.size();
+        int a = 0, b = nums[0];
+        for (int i = 1; i < n; ++i) {
+            int c = max(nums[i] + a, b);
+            a = b;
+            b = c;
         }
-        return cur;
+        return b;
     }
 };
 ```
diff --git a/solution/0700-0799/0740.Delete and Earn/README.md b/solution/0700-0799/0740.Delete and Earn/README.md
@@ -45,15 +45,13 @@
 
 <!-- 这里可写通用的实现逻辑 -->
 
-<!-- tabs:start -->
-
 核心思路: **一个数字要么不选，要么全选**
 
 首先计算出每个数字的总和 sums，并维护两个 dp 数组：select 和 nonSelect
 
-- sums[i] 代表值为 i 的元素总和
-- select[i] 代表如果选数字 i，从 0 处理到 i 的最大和
-- nonSelect[i] 代表如果不选数字 i，从 0 处理到 i 的最大和
+- `sums[i]` 代表值为 i 的元素总和
+- `select[i]` 代表如果选数字 i，从 0 处理到 i 的最大和
+- `nonSelect[i]` 代表如果不选数字 i，从 0 处理到 i 的最大和
 
 那么我们有以下逻辑：
 
@@ -65,6 +63,8 @@ select[i] = nonSelect[i-1] + sums[i];
 nonSelect[i] = Math.max(select[i-1], nonSelect[i-1]);
 ```
 
+<!-- tabs:start -->
+
 ### **Python3**
 
 <!-- 这里可写当前语言的特殊实现逻辑 -->
@@ -148,6 +148,31 @@ func deleteAndEarn(nums []int) int {
 }
 ```
 
+### **C++**
+
+```cpp
+class Solution {
+public:
+    int deleteAndEarn(vector<int>& nums) {
+        vector<int> vals(10010);
+        for (int& num : nums) {
+            vals[num] += num;
+        }
+        return rob(vals);
+    }
+
+    int rob(vector<int>& nums) {
+        int a = 0, b = nums[0];
+        for (int i = 1; i < nums.size(); ++i) {
+            int c = max(nums[i] + a, b);
+            a = b;
+            b = c;
+        }
+        return b;
+    }
+};
+```
+
 ### **...**
 
 ```
diff --git a/solution/0700-0799/0740.Delete and Earn/README_EN.md b/solution/0700-0799/0740.Delete and Earn/README_EN.md
@@ -42,15 +42,13 @@ Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
 
 ## Solutions
 
-<!-- tabs:start -->
-
 Intuition: **If we take a number, we will take all of the copies of it**.
 
 First calculate the sum of each number as **sums**, and keep updating two dp arrays: **select** and **nonSelect**
 
-- sums[i] represents the sum of elements whose value is i;
-- select[i] represents the maximum sum of processing from 0 to i if the number i is selected;
-- nonSelect[i] represents the maximum sum of processing from 0 to i if the number i is not selected;
+- `sums[i]` represents the sum of elements whose value is i;
+- `select[i]` represents the maximum sum of processing from 0 to i if the number i is selected;
+- `nonSelect[i]` represents the maximum sum of processing from 0 to i if the number i is not selected;
 
 Then we have the following conclusions:
 
@@ -62,6 +60,8 @@ select[i] = nonSelect[i-1] + sums[i];
 nonSelect[i] = Math.max(select[i-1], nonSelect[i-1]);
 ```
 
+<!-- tabs:start -->
+
 ### **Python3**
 
 ```python
@@ -141,6 +141,31 @@ func deleteAndEarn(nums []int) int {
 }
 ```
 
+### **C++**
+
+```cpp
+class Solution {
+public:
+    int deleteAndEarn(vector<int>& nums) {
+        vector<int> vals(10010);
+        for (int& num : nums) {
+            vals[num] += num;
+        }
+        return rob(vals);
+    }
+
+    int rob(vector<int>& nums) {
+        int a = 0, b = nums[0];
+        for (int i = 1; i < nums.size(); ++i) {
+            int c = max(nums[i] + a, b);
+            a = b;
+            b = c;
+        }
+        return b;
+    }
+};
+```
+
 ### **...**
 
 ```
diff --git a/solution/0700-0799/0740.Delete and Earn/Solution.cpp b/solution/0700-0799/0740.Delete and Earn/Solution.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+    int deleteAndEarn(vector<int>& nums) {
+        vector<int> vals(10010);
+        for (int& num : nums) {
+            vals[num] += num;
+        }
+        return rob(vals);
+    }
+
+    int rob(vector<int>& nums) {
+        int a = 0, b = nums[0];
+        for (int i = 1; i < nums.size(); ++i) {
+            int c = max(nums[i] + a, b);
+            a = b;
+            b = c;
+        }
+        return b;
+    }
+};
