华为技术一面 09.16 光产品线 1h
- 自我介绍
- 做了一道题
import java.util.Scanner;
/**
* @author Lei
* @create 2022-09-16 14:08
*/
public class Main {
// 小孙经过多年的奋斗，终于在家乡买一下了一大块地皮。然而糟心的是黑心的开发商在某些地皮上造成了极大的破坏，以至于不能在上面盖一砖一瓦。而作为强迫症患者的小孙，希望有一块正方形的地皮来造房子，请你帮助这个可怜人找到最大的正方形地皮。
// 输入
// 第一行为两个整数n,m表示这个土地的长宽。
// 接下来n行，每行m个整数，用空格隔开，0表示该块土地被破坏，1表示该块土地完好。
// 数据范围：1 <= n, m <= 1000
// 输出
// 一个整数，最大正方形的边长。
// 样例
// 输入样例
// 4 4
// 0 1 1 1
// 1 1 1 0
// 0 1 1 0
// 1 1 0 1
// 输出样例
// 2
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
int[][] map = new int[m][n];
boolean flag = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = scanner.nextInt();
if (map[i][j] == 1) {
flag = true;
}
}
}
if (!flag) {
System.out.println(0);
} else {
//这个是当前的一个前缀的二维矩阵
int[][] S = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + map[i - 1][j - 1];
}
}
int index = 1;
int max = -1;
while (index <= Math.min(m, n)) {
for (int j = index; j <= m; j++) {
for (int i = index; i <= n; i++) {
//哭死，就是这个没有用到，然后导致这个没有计算出来
int area = S[i][j] - S[i][j - index] - S[i - index][j] + S[i - index][j - index];
if (area == index * index) {
max = Math.max(max, index);
}
}
}
index++;
}
System.out.println(max);
}
}
}
优化：
import java.util.Scanner;
/**
* @author Lei
* @create 2022-09-16 14:08
*/
public class Main {
// 小孙经过多年的奋斗，终于在家乡买一下了一大块地皮。然而糟心的是黑心的开发商在某些地皮上造成了极大的破坏，以至于不能在上面盖一砖一瓦。而作为强迫症患者的小孙，希望有一块正方形的地皮来造房子，请你帮助这个可怜人找到最大的正方形地皮。
// 输入
// 第一行为两个整数n,m表示这个土地的长宽。
// 接下来n行，每行m个整数，用空格隔开，0表示该块土地被破坏，1表示该块土地完好。
// 数据范围：1 <= n, m <= 1000
// 输出
// 一个整数，最大正方形的边长。
// 样例
// 输入样例 1 复制
// 4 4
// 0 1 1 1
// 1 1 1 0
// 0 1 1 0
// 1 1 0 1
// 输出样例 1
// 2
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
int[][] map = new int[m][n];
boolean flag = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = scanner.nextInt();
if (map[i][j] == 1) {
flag = true;
}
}
}
if (!flag) {
System.out.println(0);
} else {
//这个是当前的一个前缀的二维矩阵
int[][] S = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + map[i - 1][j - 1];
}
}
//从最大开始进行查找，查询速度提高
int index = Math.min(m, n);
int max = -1;
boolean flagBreak = false;
while (index >= 1) {
ok:
for (int j = index; j <= m; j++) {
for (int i = index; i <= n; i++) {
int area = S[i][j] - S[i][j - index] - S[i - index][j] + S[i - index][j - index];
if (area == index * index) {
max = Math.max(max, index);
flagBreak = true;
break ok;
}
}
}
if (flagBreak) {
break;
}
index--;
}
System.out.println(max);
}
}
} 
再次总结，二维前缀和数组：
//获得前缀数组
int[][] S = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + map[i - 1][j - 1];
}
}
//得到固定长度的正方形的长度的面积
for (int j = index; j <= m; j++) {
for (int i = index; i <= n; i++) {
int area = S[i][j] - S[i][j - index] - S[i - index][j] + S[i - index][j - index];
if (area == index * index) {
max = Math.max(max, index);
}
}
}
//获取到任意的上下标的面积
//原数组的取值范围 row1 [0,m) col1 [0,n)
//原数组的取值范围 row2 [0,m) col2 [0,n)
//就是使用这个方法来计算这个这个矩阵和的时候呢，需要注意的就是他们的取值范围
public int sumRegion(int row1, int col1, int row2, int col2) {
//当前的计算方式很难的去理解，就是为啥需要这样来进行计算
return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
}
* 1：row1 [0,m) col1 [0,n)；row2 [0,m) col2 [0,n) * 2：row1和col1是左上下标，row2和col2是右下下标 * 3：右下坐标可以和左上下标可以重合，那么当前的值就是当前左上下标的值 * 4：右下坐标和左上下标如果不重合的话，进行框中的一个面积，这个面积是包含左上和
- 将一下自己最深刻的项目经历，自己做了那个部分
- 线程和进程的区别，以及线程的创建方式
- 内存泄露知道么
- 怎么规避内存泄漏
- 没有时间了，只是问了这么多，真的要好好复盘了
10.09：等了好久的主管面，终于也是进入了池子里
查看3道真题和解析