No.1 能够造成最大正方形的矩形数目
解题思路
保护最大正方形的边长并计数即可。
代码展现
class Solution { public int countGoodRectangles(int[][] rectangles) { int maxLen = 0, count = 0; for (int[] rec : rectangles) { int len = Math.min(rec[0], rec[1]); if (len > maxLen) { maxLen = len; count = 0; } if (len == maxLen) { count++; } } return count; }}No.2 同积元组
解题思路
用 Map 记录每一种乘积的因数列表。
代码展现
class Solution { public int tupleSameProduct(int[] nums) { Arrays.sort(nums); // map[i] 示意乘积为 i 的较小的因数的列表 // 比方 a * b == i 则 map[i].add(min(a, b)) Map<Integer, List<Integer>> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { int a = nums[i], b = nums[j]; int p = a * b; if (!map.containsKey(p)) { map.put(p, new ArrayList<>()); } map.get(p).add(a); // a < b } } // 有 len 对乘积为 i // 它们能形成 4 * len * (len - 1) 个元组 int count = 0; for (var entry : map.entrySet()) { int len = entry.getValue().size(); count += 4 * len * (len - 1); } return count; }}No.3 重新排列后的最大子矩阵
解题思路
枚举最大子矩阵的起始行，而后排序、统计即可。
代码展现
class Solution { public int largestSubmatrix(int[][] matrix) { Column[] cols = new Column[matrix[0].length]; for (int i = 0; i < matrix[0].length; i++) { int[] col = new int[matrix.length]; for (int j = 0; j < matrix.length; j++) { col[j] = matrix[j][i]; } cols[i] = new Column(col); } int res = 0; // 枚举最大子矩阵的起始行 i, 而后排序 for (int i = 0; i < matrix.length; i++) { final int idx = i; Arrays.sort(cols, (a, b) -> b.cont1[idx] - a.cont1[idx]); if (res < cols[0].cont1[idx] * cols.length) { // 一个优化点 res = Math.max(res, count(cols, idx)); } } return res; } // 统计以后场面下的最大子矩阵 private int count(Column[] cols, int startRow) { int res = 0; for (int endRow = startRow, endCol = cols.length - 1; endRow < cols[0].raw.length; endRow++) { while (endCol >= 0 && cols[endCol].raw[endRow] == 0) { endCol--; } res = Math.max(res, (endRow - startRow + 1) * (endCol + 1)); } return res; } // Column 类示意一列 // raw 示意这一列的原始值 // cont1[i] 示意 raw[i] 后有多少个间断的 1 class Column { int[] raw; int[] cont1; Column(int[] col) { raw = col; cont1 = new int[col.length]; cont1[col.length - 1] = col[col.length - 1]; for (int i = col.length - 2; i >= 0; i--) { cont1[i] = col[i]; if (col[i] == 1) { cont1[i] += cont1[i + 1]; } } } }}No.4 猫和老鼠II
解题思路
动静布局（记忆化搜寻）
尽管代码量比拟大，然而逻辑并不简单。实质上依然是枚举猫和老鼠的下一步怎么走，老鼠想要赢就要保障它走下一步之后，猫无论怎么走都赢不了。而后应用记忆化以提速。
代码展现
class Solution { int n, m; char[][] grid; int[][][][][] catMemo; // 记忆化 int[][][][][] mouseMemo; // 记忆化 int catJump, mouseJump; final int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } }; final int MaxRound = 100; // 8x8 的地图远不须要 1000 步 public boolean valid(int i, int j) { return i >= 0 && i < n && j >= 0 && j < m && grid[i][j] != '#'; } // 曾经走了 r 步，老鼠在 (mx, my) 猫在 (cx, cy) // 猫是否必胜 public int cat(int r, int mx, int my, int cx, int cy) { if (catMemo[r][mx][my][cx][cy] == -1) { if (mx == cx && my == cy) { return catMemo[r][mx][my][cx][cy] = 1; } if (grid[mx][my] == 'F') { return catMemo[r][mx][my][cx][cy] = 0; } if (grid[cx][cy] == 'F') { return catMemo[r][mx][my][cx][cy] = 1; } for (int[] d : dirs) { for (int jump = 0; jump <= catJump; jump++) { int x = cx + d[0] * jump; int y = cy + d[1] * jump; if (!valid(x, y)) { break; } if (mouse(r + 1, mx, my, x, y) == 0) { return catMemo[r][mx][my][cx][cy] = 1; } } } catMemo[r][mx][my][cx][cy] = 0; } return catMemo[r][mx][my][cx][cy]; } // 曾经走了 r 步，老鼠在 (mx, my) 猫在 (cx, cy) // 老鼠是否必胜 public int mouse(int r, int mx, int my, int cx, int cy) { if (r >= MaxRound) { return 0; } if (mouseMemo[r][mx][my][cx][cy] == -1) { if (mx == cx && my == cy) { return mouseMemo[r][mx][my][cx][cy] = 0; } if (grid[mx][my] == 'F') { return mouseMemo[r][mx][my][cx][cy] = 1; } if (grid[cx][cy] == 'F') { return mouseMemo[r][mx][my][cx][cy] = 0; } for (int[] d : dirs) { for (int jump = 0; jump <= mouseJump; jump++) { int x = mx + d[0] * jump; int y = my + d[1] * jump; if (!valid(x, y)) { break; } if (cat(r, x, y, cx, cy) == 0) { return mouseMemo[r][mx][my][cx][cy] = 1; } } } mouseMemo[r][mx][my][cx][cy] = 0; } return mouseMemo[r][mx][my][cx][cy]; } public boolean canMouseWin(String[] grid, int catJump, int mouseJump) { n = grid.length; m = grid[0].length(); this.grid = new char[n][m]; int mx = 0, my = 0, cx = 0, cy = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { this.grid[i][j] = grid[i].charAt(j); if (this.grid[i][j] == 'C') { cx = i; cy = j; } if (this.grid[i][j] == 'M') { mx = i; my = j; } } } this.catJump = catJump; this.mouseJump = mouseJump; catMemo = new int[MaxRound][n][m][n][m]; mouseMemo = new int[MaxRound][n][m][n][m]; // 初值 -1 示意未计算过 for (int r = 0; r < MaxRound; r++) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { for (int t = 0; t < n; t++) { for (int k = 0; k < m; k++) { catMemo[r][i][j][t][k] = -1; mouseMemo[r][i][j][t][k] = -1; } } } } } return mouse(0, mx, my, cx, cy) == 1; }}