algorithm007-class02 · Luren3 · Apr 19, 2020 · Apr 26, 2020 · May 10, 2020 · May 17, 2020
diff --git a/.DS_Store b/.DS_Store
diff --git a/.idea/$CACHE_FILE$ b/.idea/$CACHE_FILE$
diff --git a/.idea/.gitignore b/.idea/.gitignore
diff --git a/.idea/algorithm007-class02.iml b/.idea/algorithm007-class02.iml
diff --git a/.idea/checkstyle-idea.xml b/.idea/checkstyle-idea.xml
diff --git a/.idea/codeStyles/Project.xml b/.idea/codeStyles/Project.xml
diff --git a/.idea/dictionaries b/.idea/dictionaries
diff --git a/.idea/encodings.xml b/.idea/encodings.xml
diff --git a/.idea/misc.xml b/.idea/misc.xml
diff --git a/.idea/modules.xml b/.idea/modules.xml
diff --git a/.idea/vcs.xml b/.idea/vcs.xml
diff --git a/Week_01/.DS_Store b/Week_01/.DS_Store
diff --git a/Week_03/.DS_Store b/Week_03/.DS_Store
diff --git a/Week_04/.DS_Store b/Week_04/.DS_Store
diff --git a/Week_06/.DS_Store b/Week_06/.DS_Store
diff --git a/Week_06/G20200343040202/LeetCode_221_0202.java b/Week_06/G20200343040202/LeetCode_221_0202.java
@@ -0,0 +1,16 @@
+class Solution {
+    public int maximalSquare(char[][] matrix) {
+        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
+        int[][] dp = new int[rows + 1][cols + 1];
+        int maxsqlen = 0;
+        for (int i = 1; i <= rows; i++) {
+            for (int j = 1; j <= cols; j++) {
+                if (matrix[i-1][j-1] == '1'){
+                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
+                    maxsqlen = Math.max(maxsqlen, dp[i][j]);
+                }
+            }
+        }
+        return maxsqlen * maxsqlen;
+    }
+}
diff --git a/Week_06/G20200343040202/LeetCode_621_0202.java b/Week_06/G20200343040202/LeetCode_621_0202.java
@@ -0,0 +1,56 @@
+class Solution {
+    public int[][] imageSmoother(int[][] M) {
+        int r = M.length;
+        int c = M[0].length;
+        int[][] res = new int[r][c];
+        for(int i = 0; i < r;i++){
+            for(int j = 0;j < c;j++){
+                res[i][j] = add(M,i,j,r,c);
+            }
+        }
+        return res;
+    }
+
+    private int add(int[][] M,int i,int j,int m ,int n){
+        int res = 0;
+        int num = 0;
+        if(i-1>=0){
+            res += M[i-1][j];
+            num++;
+        }
+        if(i+1 < m){
+            res += M[i+1][j];
+            num++;
+        }
+        if(j-1 >= 0){
+            res += M[i][j-1];
+            num++;
+        }
+        if(j+1 < n){
+            res += M[i][j+1];
+            num++;
+        }
+
+        if(i+1 < m &&j-1 >=0){
+            res += M[i+1][j-1];
+            num++;
+        }
+        if(i-1>=0&&j-1>=0){
+            res += M[i-1][j-1];
+            num++;
+        }
+        if(i-1>=0&&j+1<n){
+            res += M[i-1][j+1];
+            num++;
+        }
+
+        if(j+1 < n && i+1 < m){
+            res += M[i+1][j+1];
+            num++;
+        }
+        res += M[i][j];
+        num++;
+        res /=num;
+        return res;
+    }
+}
diff --git a/Week_06/G20200343040202/LeetCode_647_0202.java b/Week_06/G20200343040202/LeetCode_647_0202.java
@@ -0,0 +1,15 @@
+class Solution {
+    public int countSubstrings(String s) {
+        int res = 0;
+        boolean dp[][] = new boolean[s.length()][s.length()];
+        for (int j = 0; j < s.length(); j++) {
+            for (int i = j; i >= 0; i--) {
+                if (s.charAt(i) == s.charAt(j) && ((j - i < 2) || dp[i + 1][j - 1])) {
+                    dp[i][j] = true;
+                    res++;
+                }
+            }
+        }
+        return res;
+    }
+}
diff --git a/Week_06/G20200343040202/LeetCode_64_0202.java b/Week_06/G20200343040202/LeetCode_64_0202.java
@@ -0,0 +1,20 @@
+class Solution {
+    public int minPathSum(int[][] grid) {
+
+        int dp[][] = new int[grid.length][grid[0].length];
+        dp[0][0] = grid[0][0];
+
+        for (int i = 1; i < grid.length; i++) {
+            dp[i][0] = grid[i][0] + dp[i - 1][0];
+        }
+        for (int i = 1; i < grid[0].length; i++) {
+            dp[0][i] = grid[0][i] + dp[0][i - 1];
+        }
+        for (int i = 1; i < grid.length; i++) {
+            for (int j = 1; j < grid[0].length; j++) {
+                dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
+            }
+        }
+        return dp[grid.length - 1][grid[0].length - 1];
+    }
+}
diff --git a/Week_06/G20200343040202/LeetCode_76_0202.java b/Week_06/G20200343040202/LeetCode_76_0202.java
@@ -0,0 +1,49 @@
+class Solution {
+    public String minWindow(String s, String t) {
+        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
+            return "";
+        }
+
+        int[] needs = new int[128];
+        int[] window = new int[128];
+
+        for (int i = 0; i < t.length(); i++) {
+            needs[t.charAt(i)]++;
+        }
+
+        int left = 0;
+        int right = 0;
+
+        String res = "";
+
+        int count = 0;
+
+        int minLength = s.length() + 1;
+
+        while (right < s.length()) {
+            char ch = s.charAt(right);
+            window[ch]++;
+            if (needs[ch] > 0 && needs[ch] >= window[ch]) {
+                count++;
+            }
+
+            while (count == t.length()) {
+                ch = s.charAt(left);
+                if (needs[ch] > 0 && needs[ch] >= window[ch]) {
+                    count--;
+                }
+                if (right - left + 1 < minLength) {
+                    minLength = right - left + 1;
+                    res = s.substring(left, right + 1);
+
+                }
+                window[ch]--;
+                left++;
+
+            }
+            right++;
+
+        }
+        return res;
+    }
+}