leetcode

commit 5df9f6b9d33ce1eb0775b5f3a73e1c73bcf4e22b
parent b4e4ea8d0be765c17741baeb806ee34e5c179f03
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 14 Dec 2022 21:43:58 +0100

Add some daily problems

Diffstat:
A
Problems/0198.cpp
 | 
13
+++++++++++++
A
Problems/0931.cpp
 | 
27
+++++++++++++++++++++++++++
M
README.md
 | 
2
++

3 files changed, 42 insertions(+), 0 deletions(-)
diff --git a/Problems/0198.cpp b/Problems/0198.cpp
@@ -0,0 +1,13 @@
+class Solution {
+public:
+  int rob(vector<int> &nums) {
+    if (nums.size() == 0) return 0;
+    int prev1 = 0, prev2 = 0;
+    for (int num : nums) {
+      int tmp = prev1;
+      prev1 = max(prev2 + num, prev1);
+      prev2 = tmp;
+    }
+    return prev1;
+  }
+};
diff --git a/Problems/0931.cpp b/Problems/0931.cpp
@@ -0,0 +1,27 @@
+class Solution {
+  int n;
+
+  bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
+
+public:
+  int minFallingPathSum(vector<vector<int>> &matrix) {
+    n = matrix.size();
+
+    for (int i = n - 2; i >= 0; i--) {
+      for (int j = 0; j < n; j++) {
+        int mini = INT_MAX;
+        for (int k = -1; k <= 1; k++) {
+          int x = i + 1;
+          int y = j + k;
+          if (!valid(x, y)) continue;
+          mini = min(mini, matrix[x][y]);
+        }
+        matrix[i][j] += mini;
+      }
+    }
+
+    int mini = INT_MAX;
+    for (int i = 0; i < n; i++) mini = min(mini, matrix[0][i]);
+    return mini;
+  }
+};
diff --git a/README.md b/README.md
@@ -60,6 +60,7 @@ if you have any questions.
 |  0160  |    Easy    | [Intersection of Two Linked Lists](Problems/0160.cpp)                                    |
 |  0167  |   Medium   | [Two Sum II - Input Array Is Sorted](Problems/0167.cpp)                                  |
 |  0189  |   Medium   | [Rotate Array](Problems/0189.cpp)                                                        |
+|  0198  |   Medium   | [House Robber](Problems/0198.cpp)                                                        |
 |  0199  |   Medium   | [Binary Tree Right Side View](Problems/0199.cpp)                                         |
 |  0200  |   Medium   | [Number of Islands](Problems/0200.cpp)                                                   |
 |  0203  |    Easy    | [Remove Linked List Elements](Problems/0203.cpp)                                         |
@@ -126,6 +127,7 @@ if you have any questions.
 |  0876  |    Easy    | [Middle of the Linked List](Problems/0876.cpp)                                           |
 |  0901  |   Medium   | [Online Stock Span](Problems/0901.cpp)                                                   |
 |  0905  |    Easy    | [Sort Array By Parity](Problems/0905.cpp)                                                |
+|  0931  |   Medium   | [Minimum Falling Path Sum](Problems/0931.cpp)                                            |
 |  0933  |    Easy    | [Number of Recent Calls](Problems/0933.cpp)                                              |
 |  0938  |    Easy    | [Range Sum of BST](Problems/0938.cpp)                                                    |
 |  0941  |    Easy    | [Valid Mountain Array](Problems/0941.cpp)                                                |