秋招突击——算法练习——9/4——73-矩阵置零、54-螺旋矩阵、48-旋转图像、240-搜索二维矩阵II
文章目录
- 引言
- 复习
- 新作
- 73-矩阵置零
- 个人实现
- 54-螺旋矩阵
- 个人实现
- 参考实现
- 48-旋转图像
- 个人实现
- 参考实现
- 240-搜索二维矩阵II
- 个人实现
- 参考实现
- 总结
引言
- 秋招开展的不是很顺利，还是要继续准备，继续刷算法！不断完善自己，希望能够找到一份好工作！
复习
新作
73-矩阵置零
个人实现
- 这个题目，没有做到进阶，使用了一个list来保存所有为零的节点，然后逐个遍历，将所在的行和列都置为0，具体如下
class Solution {
public void setZeroes(int[][] matrix) {
List<int[]> list = new ArrayList<>();
for(int i = 0;i < matrix.length;i ++){
for(int j = 0;j < matrix[0].length;j ++){
if(matrix[i][j] == 0){
list.add(new int[]{i,j});
System.out.println("1:: " + i + " " + j);
}
}
}
int row = matrix.length;
int col = matrix[0].length;
System.out.println(row + " " + col);
// 遍历每一个点，并将对应所在行和列置位零
for(int[] point : list){
int x = point[0];
int y = point[1];
for(int i = 0;i < col;i ++){
matrix[x][i] = 0;
}
for(int i = 0;i < row;i ++){
matrix[i][y] = 0;
}
}
}
}
54-螺旋矩阵
- 题目链接
个人实现
思路分析
- 像这种题目就很像数学题，找规律就就行了！
- 弄一个对应的boolean的矩阵，然后遇到不能访问的节点，直接左转，所以需要定义左转方向的具体实现，具体如下。
- 本质上，还是模仿了DFS的遍历过程，在遍历节点那里卡了一下！
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int[][] DIRECTIONS = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
int row = matrix.length;
int col = matrix[0].length;
boolean[][] visited = new boolean[row][col];
// 遍历每一个点
List<Integer> list = new ArrayList<>();
int curDir = 0;
int curX = 0;
int curY = 0;
for (int i = 0; i < col * row; i++) {
visited[curX][curY] = true;
list.add(matrix[curX][curY]);
// 判定下一个方向的各自是否可以访问
// 这里要判定一下尝试的次数，如果尝试了四次，就直接推出对应循环
int nextX = 0;
int nextY = 0;
for (int j = 0; j < 4; j++) {
nextX = curX + DIRECTIONS[curDir % 4][0];
nextY = curY + DIRECTIONS[curDir % 4][1];
if (nextX < 0 || nextX >= row || nextY < 0
|| nextY >= col || visited[nextX][nextY]) {
curDir++;
} else {
curX = nextX;
curY = nextY;
break;
}
}
}
return list;
}
}
参考实现
- 这里参考了Krahets的思路，设定四个边界，每一次都是遍历对应行或者列
- 感觉写起来会比较费劲呀!可能不是我想出来，所以写起来比较费劲，但是空间复杂度，确实是最好！
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
if(matrix.length == 0) return new ArrayList<>();
int row = matrix.length;
int col = matrix[0].length;
// 逐个遍历对应的元素
int t = 0;
int b = row - 1;
int l = 0;
int r = col - 1;
List<Integer> list = new ArrayList<>();
while(true){
for(int i = l;i <= r;i ++) list.add(matrix[t][i]);
if(++ t > b) break;
for(int i = t;i <= b;i ++) list.add(matrix[i][r]);
if(l > --r) break;
for(int i = r;i >= l;i --) list.add(matrix[b][i]);
if(t > --b) break;
for(int i = b;i >= t;i --) list.add(matrix[i][l]);
if(++ l > r) break;
}
return list;
}
}
48-旋转图像
- 题目链接
个人实现
思路分析
- 这个题目跟上面一个题目一样，但是要求原地旋转图像，还是得找映射关系！
- 这里只找到一个旋转关系，也就是需要一个辅助的矩阵，具体实现如下
- 每一行，旋转90度，到对应的矩阵即可
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int[][] helpMatrix = new int[n][n];
for(int i = 0;i < n;i ++){
int[] row = matrix[i];
for(int j = 0;j < n; j ++){
helpMatrix[j][n - i - 1] = row[j];
}
}
for(int i = 0;i < n;i ++){
for(int j = 0;j < n ;j ++){
matrix[i][j] = helpMatrix[i][j];
}
}
}
}
参考实现
- 这里是按照单点进行旋转实现的，比较难得就是怎么推导出这个基本的关系，找几个样例，然后直接推出来，然后再找几个样例做一个测试就行了
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for(int i = 0;i < n / 2;i ++){
for(int j = 0;j < (n + 1) / 2;j ++){
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j -1][i] = matrix[n - i -1][n - j -1];
matrix[n - i -1][n - j -1] = matrix[j][n - i -1];
matrix[j][n - i -1] = temp;
}
}
}
}
总结
- 说实话，这里还是挺容易犯错的，有可能会存在多个解的情况，我一开始就选了一组特殊解求解，结果求反了，应该同时弄一个一般解和特殊解，同时计算。
240-搜索二维矩阵II
题目链接
个人实现
思路分析
- 这个应该先匹配最大值和最小值，确定哪些可行的行，然后再比较剩余的列，确定是在那些列，然后在逐个比较对应的元素！
具体实现如下
class Solution {
public boolean searchMatrix(int[][] matrix, int tar) {
int m = matrix.length;
int n = matrix[0].length;
List<Integer> rows = new ArrayList<>();
List<Integer> cols = new ArrayList<>();
for(int i = m - 1;i >= 0;i --){
// 这里确定一个最大值和最小值，在决定是否要进行判定
if(tar >= matrix[i][0] && tar <= matrix[i][n - 1])
rows.add(i);
}
//遍历对应的列
if(rows.isEmpty()) return false;
for(int i = n - 1;i >= 0;i --){
// 这里确定一个最大值和最小值，在决定是否要进行判定
if(tar >= matrix[rows.get(rows.size() - 1)][i] && tar <= matrix[rows.get(0)][i])
cols.add(i);
}
// 二层循环遍历
for(int i :rows){
for(int j :cols)
if(matrix[i][j] == tar) return true;
}
return false;
}
}
总结
- 大概就是先遍历行，然后在遍历对应的列，找到最优的值。
- 这个代码写得太差了，有序的话，找目标值，不应该想到是使用二分查找吗?咋个这里还用上了遍历，真的使绝了！
参考实现
参考链接
- 这里将他看作是二叉树，然后采用二叉树的思路去做，还是二叉搜索树，然后直接找就行了！
class Solution {
public boolean searchMatrix(int[][] nums, int tar) {
int i = nums[0].length - 1;
int j = 0;
while(i >= 0 && j < nums.length){
System.out.println(nums[j][i] + " : " + j + " , "+ i);
if(nums[j][i] < tar) j ++;
else if(nums[j][i] > tar) i --;
else return true;
}
return false;
}
}
总结
- 这个关系给我整的有点懵，真的尴尬，画了半天，才发现是字符写错了！
总结
- 一有震动都想去看看，是不是有offer了，但是没啥反应，还是啥都没有，排序，排序！不过决定不了什么，就像今天游泳一样，想象周边得水流一点一点冲刷，冲刷，冲刷掉我的所有杂念，现在能够做的并不多，只能尽我所能去面试，准备面试，其他的，决定不了！
9/10
- 看着上周写的执念，我忽然间释怀了，想告诉自己，美团没排序上，还是挂了，志愿结束了。不过这都不算什么，我还有机会，继续在面试就是了，加油！