矩阵
73.矩阵置零
思考：对于行和列分别用两个标记数组，遍历数组如果发现对应行列有0，则标记为true，再遍历一次将标记为true的行列元素全部置为0
记录：需要二刷
class Solution {public void setZeroes(int[][] matrix) {boolean[] row = new boolean[matrix.length];boolean[] col = new boolean[matrix[0].length];for(int i = 0;i < matrix.length;i++){for(int j = 0;j < matrix[0].length;j++){if(matrix[i][j] == 0){row[i] = true;col[j] = true;}}}for(int i = 0;i < matrix.length;i++){for(int j = 0;j < matrix[0].length;j++){if(row[i] || col[j]){matrix[i][j] = 0;}}}}
}
54.螺旋矩阵
思考：四个角就是四个边界值，框住，依次遍历
记录：需要二刷
class Solution {public List<Integer> spiralOrder(int[][] matrix) {int left = 0,right = matrix[0].length-1;int upper = 0,lower = matrix.length-1;List<Integer> res = new ArrayList<>();while(res.size() < matrix.length * matrix[0].length){if(upper <= lower){for(int i = left;i <= right;i++){res.add(matrix[upper][i]);}upper++;}if(left <= right){for(int i = upper;i <= lower;i++){res.add(matrix[i][right]);}right--;}if(upper <= lower){for(int i = right;i >= left;i--){res.add(matrix[lower][i]);}lower--;}if(left <= right){for(int i = lower;i >= upper;i--){res.add(matrix[i][left]);}left++;}}return res;}
}
48.旋转图像
思考：旋转90度，相当于先按对角线翻转，再依次行翻转，记住规律就行
记录：需要二刷
class Solution {public void rotate(int[][] matrix) {for(int i = 0;i < matrix.length;i++){for(int j = i;j < matrix[0].length;j++){int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}for(int[] num : matrix){reverse(num);}}void reverse(int[] num){int left = 0,right = num.length-1;while(left < right){int temp = num[left];num[left] = num[right];num[right] = temp;left++;right--;}}
}
240.搜索二维矩阵||
思考：跟二分查找的思路一样，要找到增加、减少的条件，二维把初始定位在右上角，这样向下就是增大，向左就是减少，就可以用二分查找了
记录：不需要二刷
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int row = 0,col = matrix[0].length-1;while(row <= matrix.length-1 && col >= 0){if(matrix[row][col] < target){row++;}else if(matrix[row][col] > target){col--;}else{return true;}}return false;}
}
图论
200.岛屿数量
思考：遇到一个小1就把它变成小0，并且把它四周的都感染成0，经典题，秒
记录：不需要二刷
class Solution {public int numIslands(char[][] grid) {int res = 0;for(int i = 0;i < grid.length;i++){for(int j = 0;j < grid[0].length;j++){if(grid[i][j] == '1'){dfs(grid,i,j);res++;}}}return res;}void dfs(char[][] grid,int i,int j){if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length){return;}if(grid[i][j] == '0'){return;}grid[i][j] = '0';dfs(grid,i+1,j);dfs(grid,i-1,j);dfs(grid,i,j+1);dfs(grid,i,j-1);}
}
994.腐烂的橘子
思考：标准BFS
- 首先遍历一遍矩阵，将所有腐烂的橘子的坐标放到队列里
- 然后遍历这个腐烂橘子队列，遍历的时候按照层序遍历，一边遍历一边检查它的四周如果是好橘子就把它变腐烂，然后把这个腐烂的橘子再加到队列里。注意这里方向dirs的用法
- 最后遍历完回过去检查是否还有好橘子，如果有证明这个橘子不会被腐烂，返回-1
- 如果没有，就返回res-1
记录：需要二刷
class Solution {public int orangesRotting(int[][] grid) {int res = 0;Queue<int[]> q = new LinkedList<>();for(int i = 0;i < grid.length;i++){for(int j = 0;j < grid[0].length;j++){if(grid[i][j] == 2){q.offer(new int[]{i,j});}}}int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};while(!q.isEmpty()){int size = q.size();for(int i = 0;i < size;i++){int[] cur = q.poll();for(int[] dir : dirs){int x = cur[0] + dir[0];int y = cur[1] + dir[1];if(x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 1){grid[x][y] = 2;q.offer(new int[]{x,y});}}}res++;}for(int i = 0;i < grid.length;i++){for(int j = 0;j < grid[0].length;j++){if(grid[i][j] == 1){return -1;}}}return res == 0 ? 0 : res-1;}
}
207.课程表
思考：题目本质是判断有没有循环依赖，即检查图结构是否有环
记录：需要二刷
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer>[] graph = buildGraph(numCourses,prerequisites);onPath = new boolean[numCourses];visited = new boolean[numCourses];for(int i = 0;i < numCourses;i++){traverse(graph,i);}return !hasCycle;}boolean[] onPath;boolean[] visited;boolean hasCycle = false;void traverse(List<Integer>[] graph,int s){if(hasCycle){return;}if(onPath[s]){hasCycle = true; //s在递归路径上，成环return;}if(visited[s]){return;}visited[s] = true;onPath[s] = true;for(int i : graph[s]){traverse(graph,i);}onPath[s] = false;}List<Integer>[] buildGraph(int numCourses,int[][] prerequisites){List<Integer>[] graph = new LinkedList[numCourses];for(int i = 0;i < numCourses;i++){graph[i] = new LinkedList<>();}for(int[] edge : prerequisites){int from = edge[1],to = edge[0];graph[from].add(to);}return graph;}}
208.实现Trie(前缀树)
思考：不会，背题解
- 结构：每个节点表示一个字符，从根节点到某一节点的路径构成一个字符串，会用isEnd标记某个节点是否完整单词的结尾
- 操作原理：插入（逐个字符遍历，为每个字符创建路径），查找（沿着字符路径走，检查能否完整匹配最后节点被标记为单词结尾），前缀检查（确认沿着路径走到前缀的最后一个字符）
记录：需要二刷
class Trie {//定义TrieNode内部类private class TrieNode{private TrieNode[] children; //子节点数组，每个索引对应一个字符private boolean isEnd; //标记是否是单词结尾public TrieNode(){children = new TrieNode[26];isEnd = false;}}private TrieNode root; //Trie的根节点public Trie() {root = new TrieNode();}public void insert(String word) {TrieNode node = root;for(char c : word.toCharArray()){int index = c - 'a'; //计算字符对应的索引if(node.children[index] == null){//该字符路径不存在，就创建新节点node.children[index] = new TrieNode();}node = node.children[index]; //移动到下一个节点}node.isEnd = true; //标记该节点为单词结尾}public boolean search(String word) {TrieNode node = searchPrefix(word);return node != null && node.isEnd;}public boolean startsWith(String prefix) {return searchPrefix(prefix) != null;}//查找前缀private TrieNode searchPrefix(String prefix){TrieNode node = root;for(char c : prefix.toCharArray()){int index = c - 'a';if(node.children[index] == null){return null; //路径不存在就返回null}node = node.children[index]; //继续向下找}return node; //返回找到的节点}
}