leetcode

commit 43adbe31a527c08c4168a471226327d1e873b24d
parent 4342f7511e21103b79c9e605241ae41f134cee85
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 23 Jan 2023 16:17:06 +0100

Dynamic Programming I: Day 3

Diffstat:
A
Problems/0213.cpp
 | 
20
++++++++++++++++++++
A
Problems/0740.cpp
 | 
17
+++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 39 insertions(+), 0 deletions(-)
diff --git a/Problems/0213.cpp b/Problems/0213.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+  // see 198. House Robber
+  int rob_single(vector<int> &nums, int start, int end) {
+    if (end - start <= 0) return 0;
+    int prev1 = 0, prev2 = 0;
+    for (int i = start; i < end; i++) {
+      int tmp = prev1;
+      prev1 = max(prev2 + nums[i], prev1);
+      prev2 = tmp;
+    }
+    return prev1;
+  }
+
+  int rob(vector<int> &nums) {
+    if (nums.size() == 0) return 0;
+    return max(nums[0] + rob_single(nums, 2, nums.size() - 1),
+               rob_single(nums, 1, nums.size()));
+  }
+};
diff --git a/Problems/0740.cpp b/Problems/0740.cpp
@@ -0,0 +1,17 @@
+class Solution {
+public:
+  int deleteAndEarn(vector<int> &nums) {
+    int n = *max_element(nums.begin(), nums.end()) + 1;
+    vector<int> count(n);
+    for (int n : nums) count[n] += n;
+
+    int prev1 = 0, prev2 = 0;
+    for (int i = 0; i < n; i++) {
+      int tmp = prev1;
+      prev1 = max(prev2 + count[i], prev1);
+      prev2 = tmp;
+    }
+
+    return prev1;
+  }
+};
diff --git a/README.md b/README.md
@@ -109,6 +109,7 @@ for solving problems.
 |  0207  |   Medium   | [Course Schedule](Problems/0207.cpp)                                                             |
 |  0209  |   Medium   | [Minimum Size Subarray Sum](Problems/0209.cpp)                                                   |
 |  0210  |   Medium   | [Course Schedule II](Problems/0210.cpp)                                                          |
+|  0213  |   Medium   | [House Robber II](Problems/0213.cpp)                                                             |
 |  0217  |    Easy    | [Contains Duplicate](Problems/0217.cpp)                                                          |
 |  0222  |   Medium   | [Count Complete Tree Nodes](Problems/0222.cpp)                                                   |
 |  0223  |   Medium   | [Rectangle Area](Problems/0223.cpp)                                                              |
@@ -194,6 +195,7 @@ for solving problems.
 |  0724  |    Easy    | [Find Pivot Index](Problems/0724.cpp)                                                            |
 |  0733  |    Easy    | [Flood Fill](Problems/0733.cpp)                                                                  |
 |  0739  |   Medium   | [Daily Temperatures](Problems/0739.cpp)                                                          |
+|  0740  |   Medium   | [Delete and Earn](Problems/0740.cpp)                                                             |
 |  0743  |   Medium   | [Network Delay Time](Problems/0743.cpp)                                                          |
 |  0746  |    Easy    | [Min Cost Climbing Stairs](Problems/0746.cpp)                                                    |
 |  0747  |    Easy    | [Largest Number At Least Twice of Others](Problems/0747.cpp)                                     |