算法刷题记录-图(LeetCode)

994. Rotting Oranges

思路 BFS

以腐烂的橘子作为起始点，使用BFS逐级向外拓展，并时刻使用cnt记录良好的橘子的数量。

代码

class Solution {
public:
    int directions[4][2] = {{0,  1},
                            {0,  -1},
                            {1,  0},
                            {-1, 0}};

    int orangesRotting(vector<vector<int>> &grid) {
        int cnt = 0;
        deque<vector<int>> deque1;
        int m=(int)grid.size();
        int n=(int)grid[0].size();
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    cnt++;
                } else if (grid[i][j] == 2) {
                    deque1.push_back({i, j, 0});
                }
            }
        }
        if (cnt==0){
            return 0;
        }
        while (!deque1.empty()) {
            auto curr = deque1.back();
            deque1.pop_back();
            int time=curr[2];
            for (auto d:directions) {
                int x=curr[0]+d[0];
                int y=curr[1]+d[1];
                if (x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){
                    cnt--;
                    deque1.push_front({x,y,time+1});
                    grid[x][y]=2;
                    if (cnt==0){
                        return time+1;
                    }
                }
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

1020. Number of Enclaves

思路 DFS

首先对边缘使用dfs算法将所有的1变为0，然后统计剩余的1的数量即可。本算法存在优化空间，其实只要第一次清除完边缘，剩下每次碰到1，+1即可。

代码

class Solution {
    static final int[][] DIRECTIONS={{1,0},{-1,0},{0,1},{0,-1}};
    int curr_cnt=0;
    public int numEnclaves(int[][] grid) {
        clearEdges(grid);
        int ans=0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j <grid[0].length ; j++) {
                if (grid[i][j]==1){
                    curr_cnt=0;
                    dfsCounting(grid,i,j);
                    ans+=curr_cnt;
                }
            }
        }
        return ans;
    }
    public void clearEdges(int[][] grid){
        for (int i = 0; i < grid[0].length; i++) {
            if (grid[0][i]==1){
                dfsClear(grid,0,i);
            }
            if (grid[grid.length-1][i]==1){
                dfsClear(grid,grid.length-1,i);
            }
        }
        for (int i = 1; i < grid.length-1; i++) {
            if (grid[i][0]==1){
                dfsClear(grid,i,0);
            }
            if (grid[i][grid[0].length-1]==1){
                dfsClear(grid,i,grid[0].length-1);
            }
        }
    }
    public void dfsClear(int[][] grid,int r,int c){
        if (r>=grid.length||c>=grid[0].length||r<0||c<0||grid[r][c]==0){
            return ;
        }
        grid[r][c]=0;
        for (var d:DIRECTIONS){
            dfsClear(grid,r+d[0],c+d[1]);
        }
    }
    public void dfsCounting(int[][] grid,int r,int c){
        if (r>=grid.length||c>=grid[0].length||r<0||c<0||grid[r][c]==0){
            return ;
        }
        grid[r][c]=0;
        curr_cnt++;
        for (var d:DIRECTIONS){
            dfsCounting(grid,r+d[0],c+d[1]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

1034. Coloring A Border

思路 DFS

代码

class Solution {
    ArrayList<int[]> arrs=new ArrayList<>();
    int ROWS;
    int COLUMNS;
    int[][] grid;
    int[][] DIRECTIONS={{0,1},{0,-1},{1,0},{-1,0}};
    boolean[][] visited;
    public int[][] colorBorder(int[][] _grid, int row, int col, int color) {
        grid=_grid;
        ROWS=grid.length;
        COLUMNS=grid[0].length;
        visited=new boolean[ROWS][COLUMNS];
        dfs(row,col,grid[row][col]);
        for(var coordinate:arrs){
            grid[coordinate[0]][coordinate[1]]=color;
        }
        return grid;
    }
    public void dfs(int r,int c,int color){
        if (r<0||c<0||r>=ROWS||c>=COLUMNS||grid[r][c]!=color||visited[r][c]){
            return;
        }
        visited[r][c]=true;
        if (check(r,c)){
            arrs.add(new int[]{r,c});
        }
        for(var direction:DIRECTIONS){
            dfs(r+direction[0],c+direction[1],color);
        }
    }
    public boolean check(int r,int c){
        int orig_color=grid[r][c];
        if (r==0||r==ROWS-1||c==0||c==COLUMNS-1){
            return true;
        }
        for (var direction:DIRECTIONS){
            int adjacent_r=r+direction[0];
            int adjacent_c=c+direction[1];
            if (orig_color!=grid[adjacent_r][adjacent_c]){
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

*1042. Flower Planting With No Adjacent

思路1 BFS

使用BFS对图进行遍历，但是时间复杂度高

代码1 BFS

class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        int[] ans=new int[n];
        ArrayList<Integer>[] adjacent=new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adjacent[i]=new ArrayList<>();
        }
        for(var pair:paths){
            adjacent[pair[0]-1].add(pair[1]-1);
            adjacent[pair[1]-1].add(pair[0]-1);
        }
        HashSet<Integer> nodes=new HashSet<>();
        for (int i = 0; i < n; i++) {
            nodes.add(i);
        }
        Deque<Integer> deque=new LinkedList<>();
        while (!nodes.isEmpty()){
            int curr=nodes.iterator().next();
            nodes.remove(curr);
            deque.offerLast(curr);
            while (!deque.isEmpty()){
                var currNode=deque.pollFirst();
                if (ans[currNode]==0){
                    int[] usable=new int[5];
                    for(var node:adjacent[currNode]){
                        usable[ans[node]]++;
                        if (ans[node]==0){
                            deque.offerLast(node);
                        }
                    }
                    for (int i = 1; i <=4 ; i++) {
                        if (usable[i]==0){
                            ans[currNode]=i;
                            break;
                        }
                    }
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

思路2 试色法

问题相当于用 4 种颜色给图中的每个节点染色，要求相邻节点颜色不同。而「所有花园最多有 3 条路径可以进入或离开」，这相当于图中每个点的度数至多为 3，那么只要选一个和邻居不同的颜色即可。

代码

    public int[] gardenNoAdj(int n, int[][] paths) {
        List<Integer> g[] = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : paths) {
            int x = e[0] - 1, y = e[1] - 1; // 编号改从 0 开始
            g[x].add(y);
            g[y].add(x); // 建图
        }
        var color = new int[n];
        for (int i = 0; i < n; ++i) {
            var used = new boolean[5];
            for (var j : g[i])
                used[color[j]] = true;
            while (used[++color[i]]);
        }
        return color;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1222. Queens That Can Attack the King

思路 Hash+DFS

对8个方向依次遍历，只要存在可以攻击的棋子即立即返回。

代码

class Solution {
    public static class Coordinate{
        public int x;
        public int y;

        @Override
        public boolean equals(Object obj) {
            if (this==obj){
                return true;
            }
            if (obj!=null&&getClass()!=obj.getClass()){
                return false;
            }
            Coordinate other=(Coordinate) obj;
            return other.x==x&&other.y==y;
        }

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x,y);
        }
    }
    List<List<Integer>> ans=new ArrayList<>();
    HashSet<Coordinate> queens=new HashSet<>();
    public List<List<Integer>> queensAttacktheKing(int[][] _queens, int[] king) {
        for(var q:_queens){
            queens.add(new Coordinate(q[0],q[1]));
        }
        findOneDirection(king,1,1);
        findOneDirection(king,1,-1);
        findOneDirection(king,-1,1);
        findOneDirection(king,0,-1);
        findOneDirection(king,-1,0);
        findOneDirection(king,0,1);
        findOneDirection(king,1,0);
        findOneDirection(king,-1,-1);
        return ans;
    }
    public void findOneDirection(int[] king ,int r,int c){
        int curr_r=king[0]+r;
        int curr_c=king[1]+c;
        while (true){
            if (curr_r<0||curr_r>=8||curr_c<0||curr_c>=8){
                return;
            }
            if (queens.contains(new Coordinate(curr_r,curr_c))){
                ans.add(List.of(curr_r,curr_c));
                return;
            }
            curr_r+=r;
            curr_c+=c;
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

2596. Check Knight Tour Configuration

思路 DFS

对于起始点，每次对八个方向进行判断查看是否有可行的下一个点。如果遍历完成则返回true。

代码

class Solution {
public:
    int directions[8][2]={{2,1},{2,-1},{-2,-1},{-2,1},{1,2},{1,-2},{-1,2},{-1,-2}};
    int target;
    int n;
    bool flag=false;
    vector<vector<int>> grid;
    bool checkValidGrid(vector<vector<int>>& _grid) {
        grid=_grid;
        n=grid.size();
        if (grid[0][0]!=0){
            return false;
        }
        target=n*n;
        findGoal(1,0,0);
        return flag;
    }
    void findGoal(int curr,int r,int c){
        if (flag){
            return;
        }
        if (curr==target){
            flag= true;
            return;
        }
        for (auto p:directions) {
            int r_next=p[0]+r;
            int c_next=p[1]+c;
            if (r_next>=0&&r_next<n&&c_next>=0&&c_next<n&&grid[r_next][c_next]==curr){
                findGoal(curr+1,r_next,c_next);
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34