文章目录
- 引言
- 复习
- 新作
- 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
- 看着上周写的执念,我忽然间释怀了,想告诉自己,美团没排序上,还是挂了,志愿结束了。不过这都不算什么,我还有机会,继续在面试就是了,加油!