4 problems solved.

lintcoder · lintcoder · commit 6e254fa59e34 · 2020-01-23T15:38:56.000+08:00
diff --git a/src/22.cpp b/src/22.cpp
@@ -0,0 +1,31 @@
+vector<string> generateParenthesis(int n) {
+        if (n <= 0)
+            return {};
+        
+        vector<string> res;
+        string s;
+        generate(s, 0, 0, n, res);
+        
+        return res;
+    }
+    
+    void generate(const string& s, int left, int right, int n, vector<string>& res)
+    {
+        if (left == n && right == n)
+            res.push_back(s);
+        else
+        {
+            if (left < n)
+            {
+                string tmp(s);
+                tmp.push_back('(');
+                generate(tmp, left+1, right, n, res);
+            }
+            if (left > right)
+            {
+                string tmp(s);
+                tmp.push_back(')');
+                generate(tmp, left, right+1, n, res);
+            }
+        }
+    }
diff --git a/src/34.cpp b/src/34.cpp
@@ -0,0 +1,12 @@
+vector<int> searchRange(vector<int>& nums, int target) {
+        vector<int> res(2, -1);
+        if (!binary_search(nums.begin(), nums.end(), target))
+            return res;
+        
+        auto iter = lower_bound(nums.begin(), nums.end(), target);
+        res[0] = iter-nums.begin();
+        iter = upper_bound(nums.begin(), nums.end(), target);
+        res[1] = iter-1-nums.begin();
+        
+        return res;
+    }
diff --git a/src/62.cpp b/src/62.cpp
@@ -0,0 +1,23 @@
+int uniquePaths(int m, int n) {
+        vector<vector<int>> path(m, vector<int>(n, 0));
+        
+        return search(0, 0, m, n, path);
+    }
+    
+    int search(int p, int q, int m, int n, vector<vector<int>>& path)
+    {
+        if (p < m-1 && q < n-1)
+        {
+            if (path[p][q] == 0)
+            {
+                int t = search(p+1, q, m, n, path) + search(p, q+1, m, n, path);
+                path[p][q] = t;
+                
+                return t;
+            }
+            else
+                return path[p][q];
+        }
+        else
+            return 1;
+    }
diff --git a/src/64.cpp b/src/64.cpp
@@ -0,0 +1,41 @@
+int minPathSum(vector<vector<int>>& grid) {
+        int row = grid.size();
+        if (row == 0)
+            return 0;
+        int col = grid[0].size();
+        
+        vector<vector<int>> sum(row, vector<int>(col, -1));
+        return search(0, 0, row, col, grid, sum);
+    }
+    
+    int search(int p, int q, int m, int n, const vector<vector<int>>& grid, vector<vector<int>>& sum)
+    {
+        if (sum[p][q] == -1)
+        {
+            if (p < m-1 && q < n-1)
+            {
+                int v1 = search(p+1, q, m, n, grid, sum);
+                int v2 = search(p, q+1, m, n, grid, sum);
+                sum[p][q] = v1 < v2 ? v1+grid[p][q] : v2+grid[p][q];
+                return sum[p][q];
+            }
+            else if (p == m-1)
+            {
+                int t = 0;
+                for (int i = q; i < n; ++i)
+                    t += grid[p][i];
+                sum[p][q] = t;
+                return t;
+            }
+            else
+            {
+                int t = 0;
+                for (int i = p; i < m; ++i)
+                    t += grid[i][q];
+                sum[p][q] = t;
+                return t;
+            }
+        }
+        else
+            return sum[p][q];
+    }
