图论

由 笔尖 发布

785. 判断二分图

给定一个无向图graph,当这个图为二分图时返回true。如果我们能将一个图的节点集合分割成两个独立的子集A和B,并使图中的每一条边的两个节点一个来自A集合,一个来自B集合,我们就将这个图称为二分图。通过染色法,对遍历到的节点依次染色,如果能够交叉,则为二分图。

image-20200923211123380

class Solution {
private:
    int *colors;

    bool dfs(int i, int color, vector<vector<int>> &graph) {
        colors[i] = color;
        for (int next:graph[i]) {
            if (colors[next] == -1 && !dfs(next, 1 - color, graph))
                return false;
            else if (colors[next] == color)
                return false;
        }
        return true;
    }

public:
    bool isBipartite(vector<vector<int>> &graph) {
        int n = graph.size();
        colors = new int[n];
        for (int i = 0; i < n; ++i) {
            colors[i] = -1;
        }
        for (int i = 0; i < n; ++i) {
            if (colors[i] == -1 && !dfs(i, 0, graph))
                return false;
        }
        return true;
    }
};

695. 岛屿的最大面积

class Solution {
    private int res = 0;
    private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int maxAreaOfIsland(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1)
                    res = Math.max(res, bfs(i, j, grid));
            }
        }
        return res;
    }

    private int bfs(int i, int j, int[][] grid) {
        Queue<Map.Entry<Integer, Integer>> queue = new LinkedList<>();
        grid[i][j] = 0;
        queue.add(new AbstractMap.SimpleEntry<>(i, j));
        int tmp = 0;
        while (!queue.isEmpty()) {
            Map.Entry<Integer, Integer> cur = queue.poll();
            tmp++;
            for (int k = 0; k < 4; k++) {
                int ni = cur.getKey() + dirs[k][0];
                int nj = cur.getValue() + dirs[k][1];
                if (ni >= 0 && ni < grid.length && nj >= 0 && nj < grid[0].length && grid[ni][nj] == 1) {
                    grid[ni][nj] = 0;
                    queue.add(new AbstractMap.SimpleEntry<>(ni, nj));
                }
            }
        }
        return tmp;
    }
}

1034. 边框着色

class Solution {
    private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
        int m = grid.length;
        int n = grid[0].length;
        boolean visited[][] = new boolean[m][n];
        int need = grid[r0][c0];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r0, c0});
        visited[r0][c0] = true;
        while ((!queue.isEmpty())) {
            int[] cur = queue.poll();
            int curi = cur[0];
            int curj = cur[1];
            for (int i = 0; i < 4; i++) {
                int ni = curi + dirs[i][0];
                int nj = curj + dirs[i][1];
                if (ni < 0 || ni >= m || nj < 0 || nj >= n)
                    grid[curi][curj] = color;
                else if (grid[ni][nj] != need && visited[ni][nj] == false)
                    grid[curi][curj] = color;
                else if (grid[ni][nj] == need && visited[ni][nj] == false) {
                    visited[ni][nj] = true;
                    queue.add(new int[]{ni, nj});
                }
            }
        }
        return grid;
    }
}

529. 扫雷游戏

827. 最大人工岛

1091. 二进制矩阵中的最短路径

752. 打开转盘锁

//BFS
class Solution {
    public int openLock(String[] deadends, String target) {
        HashSet<String> deads = new HashSet<>();
        HashMap<String, Integer> visited = new HashMap<>();
        for (String tmp : deadends)
            deads.add(tmp);
        if (deads.contains("0000"))
            return -1;
        if (target.equals("0000"))
            return 0;
        Queue<String> queue = new LinkedList<>();
        queue.add("0000");
        visited.put("0000", 0);
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            int step = visited.get(cur);
            step++;
            ArrayList<String> list = new ArrayList<>();
            for (int i = 0; i < 4; i++) {
                char[] chars = cur.toCharArray();
                chars[i] = Character.forDigit(((chars[i] - '0' + 1) % 10), 10);
                list.add(new String(chars));
                chars[i] = Character.forDigit(((chars[i] - '0' + 8) % 10), 10);
                list.add(new String(chars));
            }
            for (String next : list) {
                if (next.equals(target))
                    return step;
                if (!deads.contains(next) && !visited.containsKey(next)) {
                    queue.add(next);
                    visited.put(next, step);
                }
            }
        }
        return -1;
    }
}
//双向BFS,由于每次都会扩展8个新状态,所以队列容易变得庞大,不仅队列空间呈指数级增长,时间也会很长。改进双向BFS后,由于每次都是选择队列较短的一方,因此队列空间增长减缓,相应的时间消耗也会缩短。
class Solution {
    public int openLock(String[] deadends, String target) {
        HashSet<String> deads = new HashSet<>();
        for (String tmp : deadends)
            deads.add(tmp);
        if (deads.contains("0000")) return -1;
        if (target.equals("0000")) return 0;
        HashMap<String, Integer> visited1 = new HashMap<>();
        HashMap<String, Integer> visited2 = new HashMap<>();
        Queue<String> queue1 = new LinkedList<>();
        Queue<String> queue2 = new LinkedList<>();
        queue1.add("0000");
        visited1.put("0000", 0);
        queue2.add(target);
        visited2.put(target, 0);

        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            if (queue1.size() > queue2.size()) {
                Queue<String> tmp = queue1;
                queue1 = queue2;
                queue2 = tmp;
                HashMap<String, Integer> tmp2 = visited1;
                visited1 = visited2;
                visited2 = tmp2;
            }
            String cur = queue1.poll();
            int step = visited1.get(cur) + 1;
            ArrayList<String> list = new ArrayList<>();
            for (int i = 0; i < 4; i++) {
                char[] chars = cur.toCharArray();
                chars[i] = Character.forDigit(((chars[i] - '0' + 1) % 10), 10);
                list.add(new String(chars));
                chars[i] = Character.forDigit(((chars[i] - '0' + 8) % 10), 10);
                list.add(new String(chars));
            }
            for (String next : list) {
                if (deads.contains(next) || visited1.containsKey(next))
                    continue;
                if (visited2.containsKey(next))
                    return visited2.get(next) + step;
                queue1.add(next);
                visited1.put(next, step);
            }
        }
        return -1;
    }
}

暂无评论

发表评论