algorithm007-class02 · xuguangyi · May 22, 2020 · May 22, 2020 · May 22, 2020 · May 22, 2020
diff --git a/Week_06/G20200343040254/lc_221_maximalSquare.java b/Week_06/G20200343040254/lc_221_maximalSquare.java
@@ -0,0 +1,55 @@
+package week06;
+
+public class lc_221_maximalSquare {
+	public int maximalSquare_01(char[][] matrix) {
+
+		if (matrix == null || matrix.length == 0)
+			return 0;
+		if (matrix[0] == null || matrix[0].length == 0)
+			return 0;
+
+		int N = matrix.length;
+		int M = matrix[0].length;
+		int[][] dp = new int[N + 1][M + 1];
+
+		int max = 0;
+		for (int i = 1; i <= N; i++) {
+			for (int j = 1; j <= M; 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;
+					max = Math.max(max, dp[i][j]);
+				}
+			}
+		}
+		return max * max;
+
+	}
+
+	public int maximalSquare(char[][] matrix) {
+
+		if (matrix == null || matrix.length == 0)
+			return 0;
+		if (matrix[0] == null || matrix[0].length == 0)
+			return 0;
+
+		int N = matrix.length;
+		int M = matrix[0].length;
+		int[][] dp = new int[N][M];
+		int max = 0;
+		for (int i = 0; i < N; i++) {
+			for (int j = 0; j < M; j++) {
+				if (matrix[i][j] == '1') {
+					if (i == 0 || j == 0) {
+						dp[i][j] = 1;
+					} else {
+						// dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1
+						dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i - 1][j - 1]), dp[i][j - 1]) + 1;
+					}
+
+					max = Math.max(max, dp[i][j]);
+				}
+			}
+		}
+		return max * max;
+	}
+}
diff --git a/Week_06/G20200343040254/lc_621_leastInterval.java b/Week_06/G20200343040254/lc_621_leastInterval.java
@@ -0,0 +1,104 @@
+package week06;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.PriorityQueue;
+
+public class lc_621_leastInterval {
+	public static int leastInterval_01(char[] tasks, int n) {
+
+		int[] tts = new int[26];
+
+		for (char c : tasks) {
+			tts[c - 'A']++;
+		}
+
+		Arrays.parallelSort(tts);
+
+		int time = 0;
+
+		while (tts[25] > 0) {
+
+			int i = 0;
+			while (i <= n) {
+				if (tts[25] == 0) {
+					break;
+				}
+
+				if (i < 26 && tts[25 - i] > 0) {
+					tts[25 - i]--;
+				}
+				time++;
+				i++;
+			}
+			Arrays.parallelSort(tts);
+		}
+		return time;
+	}
+
+	public static int leastInterval_02(char[] tasks, int n) {
+
+		int[] tts = new int[26];
+		for (char c : tasks) {
+			tts[c - 'A']++;
+		}
+
+		PriorityQueue<Integer> heap = new PriorityQueue<Integer>(26, Collections.reverseOrder());
+
+		for (int i : tts) {
+			if (i > 0)
+				heap.add(i);
+		}
+
+		int time = 0;
+		while (!heap.isEmpty()) {
+			int i = 0;
+			List<Integer> l = new ArrayList<Integer>();
+			while (i <= n) {
+				if (!heap.isEmpty()) {
+					if (heap.peek() > 1) {
+						l.add(heap.poll() - 1);
+					} else {
+						heap.poll();
+					}
+				}
+
+				time++;
+
+				if (heap.isEmpty() && l.size() == 0) {
+					break;
+				}
+				i++;
+			}
+
+			for (Integer t : l) {
+				heap.add(t);
+			}
+		}
+		return time;
+	}
+
+	public static int leastInterval_03(char[] tasks, int n) {
+		int[] tts = new int[26];
+		for (char c : tasks) {
+			tts[c - 'A']++;
+		}
+
+		Arrays.parallelSort(tts);
+
+		int max = tts[25] - 1, idle_slots = max * n;
+
+		for (int i = 24; i > 0 && tts[i] > 0; i--) {
+			idle_slots -= Math.min(tts[i], max);
+		}
+		return idle_slots > 0 ? idle_slots + tasks.length : tasks.length;
+	}
+
+	public static void main(String[] args) {
+		char[] chs = new char[] { 'A', 'A', 'A', 'B', 'B', 'B' };
+		int i = leastInterval_03(chs, 2);
+		System.out.println(i);
+	}
+}
diff --git a/Week_06/G20200343040254/lc_62_uniquePaths.java b/Week_06/G20200343040254/lc_62_uniquePaths.java
@@ -0,0 +1,55 @@
+package week06;
+
+import java.util.Arrays;
+
+public class lc_62_uniquePaths {
+
+	public static int uniquePaths_01(int m, int n) {
+		int[][] dp = new int[m][n];
+		for (int i = 0; i < m; i++)
+			dp[i][0] = 1;
+
+		for (int i = 0; i < n; i++) {
+			dp[0][i] = 1;
+		}
+
+		for (int i = 1; i < m; i++) {
+			for (int j = 1; j < n; j++) {
+				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
+			}
+		}
+
+		return dp[m - 1][n - 1];
+	}
+
+	public static void main(String[] args) {
+		uniquePaths_01(3, 2);
+	}
+
+	public static int uniquePaths_02(int m, int n) {
+		int[] c = new int[n];
+		Arrays.fill(c, 1);
+
+		for (int i = 1; i < m; i++) {
+			for (int j = 1; j < n; j++) {
+				c[j] += c[j - 1];
+			}
+		}
+		return c[n - 1];
+	}
+
+	public static int uniquePaths_03(int m, int n) {
+//		long result = 1;
+//	     for(int i=0;i<Math.min(m-1,n-1);i++)
+//	         result = result*(m+n-2-i)/(i+1); 
+//	     return (int)result;
+//		
+		long r = 1;
+
+		int c = Math.min(m - 1, n - 1);
+		for (int i = 0; i < c; i++) {
+			r =r* (m + n - 2 - i) / (i + 1);
+		}
+		return (int) r;
+	}
+}
diff --git a/Week_06/G20200343040254/lc_63_uniquePathsWithObstacles.java b/Week_06/G20200343040254/lc_63_uniquePathsWithObstacles.java
@@ -0,0 +1,22 @@
+package week06;
+
+public class lc_63_uniquePathsWithObstacles {
+	public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
+
+		int width = obstacleGrid[0].length;
+		int[] dp = new int[width];
+		dp[0] = 1;
+
+		for (int[] row : obstacleGrid) {
+			for (int i = 0; i < width; i++) {
+				if (row[i] == 1) {
+					dp[i] = 0;
+				} else if (i > 0) {
+					dp[i] += dp[i - 1];
+				}
+			}
+		}
+
+		return dp[width -1];
+	}
+}
diff --git a/Week_06/G20200343040254/lc_92_numDecodings.java b/Week_06/G20200343040254/lc_92_numDecodings.java
@@ -0,0 +1,104 @@
+package week06;
+
+public class lc_92_numDecodings {
+
+	public int numDecodings_01(String s) {
+
+		if (s == null || s.length() == 0)
+			return 0;
+
+		char[] chs = s.toCharArray();
+		int dp[] = new int[chs.length + 1];
+
+		dp[0] = 1;
+		dp[1] = chs[0] == '0' ? 0 : 1;
+
+		if (chs.length <= 1)
+			return dp[1];
+
+		for (int i = 2; i <= chs.length; i++) {
+
+			int n = (chs[i - 2] - '0') * 10 + (chs[i - 1] - '0');
+
+			if (chs[i - 1] == '0' && chs[i - 2] == '0') {
+				return 0;
+			} else if (chs[i - 2] == '0') {
+				dp[i] = dp[i - 1];
+			} else if (chs[i - 1] == '0') {
+				if (n > 26)
+					return 0;
+				dp[i] = dp[i - 2];
+			} else if (n > 26) {
+				dp[i] = dp[i - 1];
+			} else {
+				dp[i] = dp[i - 1] + dp[i - 2];
+			}
+		}
+
+		return dp[dp.length - 1];
+
+	}
+
+	public int numDecodings_02(String s) {
+
+		/**
+		 * if（chs[i] == 0） dp[i] = 0; if (chs[i] + chs[i+1] <=26) { dp[i] = dp[i+1] +
+		 * dp[i+2]; } else dp[i] = dp[i+1];
+		 */
+
+		if (s == null || s.length() == 0)
+			return 0;
+
+		char[] chs = s.toCharArray();
+		int len = chs.length;
+		int dp[] = new int[len + 1];
+
+		dp[len] = 1;
+		dp[len - 1] = chs[len - 1] == '0' ? 0 : 1;
+
+		for (int i = len - 2; i >= 0; i--) {
+			if (chs[i] == '0') {
+				dp[i] = 0;
+				continue;
+			}
+
+			if ((chs[i] - '0') * 10 + (chs[i + 1] - '0') <= 26) {
+				dp[i] = dp[i + 1] + dp[i + 2];
+			} else {
+				dp[i] = dp[i + 1];
+			}
+		}
+
+		return dp[0];
+	}
+
+	public int numDecodings_03(String s) {
+
+		if (s == null || s.length() == 0)
+			return 0;
+
+		char[] chs = s.toCharArray();
+		int len = chs.length;
+
+		int x = 1, ans;
+		ans = chs[len - 1] == '0' ? 0 : 1;
+
+		for (int i = len - 2; i >= 0; i--) {
+
+			if (chs[i] == '0') {
+				x = ans;
+				ans = 0;
+				continue;
+			}
+
+			if ((chs[i] - '0') * 10 + (chs[i + 1] - '0') <= 26) {
+				ans += x;
+				x = ans - x;
+			} else {
+				x = ans;
+			}
+		}
+
+		return ans;
+	}
+}
diff --git a/Week_07/G20200343040254/lc_22_generateParenthesis.java b/Week_07/G20200343040254/lc_22_generateParenthesis.java
@@ -0,0 +1,27 @@
+package week07;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class lc_22_generateParenthesis {
+
+	private void helper(String s, int l, int r, int n, List<String> result) {
+		if (l == n && r == n) {
+			result.add(s);
+		}
+
+		if (l < n) {
+			helper(s + "(", l + 1, r, n, result);
+		}
+
+		if (r < n && r < l) {
+			helper(s + ")", l, r + 1, n, result);
+		}
+	}
+
+	public List<String> generateParenthesis(int n) {
+		List<String> result = new ArrayList<String>();
+		helper("", 0, 0, n, result);
+		return result;
+	}
+}