上岸算法
任何只教知识的课程都是耍流氓
我们直击上岸
关注我们，第一时间获得大厂面试真题讲解
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;
}
}
杭州上岸算法网络科技有限公司
上岸算法网络科技有限公司是一家致力于用高质量，高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量，高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟，用最高效，经济，合理的方式帮助更多学生快速找到梦寐以求的工作。
创作新主题