Merge pull request #1285 from Qualifor/master

melody-li · web-flow · commit 2226812bd1dd · 2019-12-12T18:44:21.000+08:00
471-Week 08
diff --git a/Week 08/id_471/LeetCode_198_471.java b/Week 08/id_471/LeetCode_198_471.java
@@ -0,0 +1,15 @@
+class Solution {
+    public int rob(int[] nums) {
+        int preTwo = 0;
+        int pre = 0;
+        int max = pre;
+
+        for (int i = 0; i < nums.length; i++) {
+            max = Math.max(preTwo + nums[i], pre);
+            preTwo = pre;
+            pre = max;
+        }
+
+        return max;
+    }
+}
diff --git a/Week 08/id_471/LeetCode_300_471.java b/Week 08/id_471/LeetCode_300_471.java
@@ -0,0 +1,26 @@
+class Solution {
+    public int lengthOfLIS(int[] nums) {
+        int tail[] = new int[nums.length];
+        int size = 0;
+        
+        for (int num : nums) {
+            
+            int i = 0, j = size;
+            while (i < j) {
+                int mid = i + ((j - i) >> 1);
+                
+                if (tail[mid] < num) {
+                    i = mid + 1;
+                } else {
+                    j = mid;
+                }
+            }
+            tail[i] = num;
+            if (i == size) {
+                size++;
+            }
+        }
+        
+        return size;
+    }
+}
diff --git a/Week 08/id_471/LeetCode_62_471.java b/Week 08/id_471/LeetCode_62_471.java
@@ -0,0 +1,14 @@
+class Solution {
+    public int uniquePaths(int m, int n) {
+        int dp[] = new int[n];
+        Arrays.fill(dp, 1);
+
+        for (int i = 1; i < m; i++) {
+            for (int j = 1; j < n; j++) {
+                dp[j] += dp[j-1];
+            }
+        }
+
+        return dp[n-1];
+    }
+}
diff --git a/Week 08/id_471/LeetCode_64_471.java b/Week 08/id_471/LeetCode_64_471.java
@@ -0,0 +1,19 @@
+class Solution {
+    public int minPathSum(int[][] grid) {
+        int m = grid.length;
+        int n = grid[0].length;
+        int dp[] = new int[n];
+
+        for (int i = 0; i < grid[0].length; i++) {
+            dp[i] = i == 0 ? grid[0][i] : dp[i - 1] + grid[0][i];
+        }
+
+        for (int i = 1; i < m; i++) {
+            dp[0] = dp[0] + grid[i][0];
+            for (int j = 1; j < n; j++) {
+                dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j];
+            }
+        }
+        return dp[n - 1];
+    }
+}
diff --git a/Week 08/id_471/LeetCode_91_471.java b/Week 08/id_471/LeetCode_91_471.java
@@ -0,0 +1,26 @@
+class Solution {
+    public int numDecodings(String s) {
+        if (s.length() == 0) {
+            return 0;
+        }
+        
+        int dp[] = new int[s.length() + 1];
+        dp[0] = 1;
+        dp[1] = s.charAt(0) == '0' ? 0 : 1;
+        
+        for (int i = 2; i <= s.length(); i++) {
+            int first = Integer.valueOf(s.substring(i - 1, i));
+            int second = Integer.valueOf(s.substring(i - 2, i));
+            
+            if (first >= 1 && first <= 9) {
+                dp[i] += dp[i - 1];
+            }
+            
+            if (second >= 10 && second <= 26) {
+                dp[i] += dp[i - 2];
+            }
+        }
+        
+        return dp[s.length()];
+    }
+}
