矩阵
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; //返回找到的节点
}
}