算法小计

133. 克隆图 - 力扣（LeetCode）

复习复习

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return node;
        Deque<Node> queue = new ArrayDeque<>();
        Map<Node, Node> map = new HashMap<>();
        queue.offerFirst(node);
        map.put(node, new Node(node.val));
        while (!queue.isEmpty()) {
            Node cur = queue.pollLast();
            for (Node neighbor : cur.neighbors) {
                if (!map.containsKey(neighbor)) {
                    queue.offerFirst(neighbor);
                    map.put(neighbor, new Node(neighbor.val));
                }
                map.get(cur).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }
}
class Solution {
    Map<Node, Node> map = new HashMap<>();
    public Node cloneGraph(Node node) {
        if (node == null) return node;
        if (map.containsKey(node)) return map.get(node);
        Node cloneNode = new Node(node.val);
        map.put(node, cloneNode);
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

547. 省份数量 - 力扣（LeetCode）

初版，使用了HashMap来帮助建立图的模型

class Solution {
    public int findCircleNum(int[][] isConnected) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] visited = new int[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected[0].length; j++) {
                if (isConnected[i][j] == 1) {
                    List<Integer> listI = map.getOrDefault(i, new ArrayList<>());
                    List<Integer> listJ = map.getOrDefault(j, new ArrayList<>());
                    listI.add(j);
                    listJ.add(i);
                    map.put(i, listI);
                    map.put(j, listJ);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < isConnected.length; i++) {
            if (visited[i] == 0) {
                count++;
                dfs(map, visited, i);
            }
        }
        return count;

    }

    public void dfs(Map<Integer, List<Integer>> map, int[] visited, int cur) {
        if (visited[cur] == 1) return;
        visited[cur] = 1;
        List<Integer> neighbors = map.get(cur);
        for (Integer neighbor : neighbors) {
            dfs(map, visited, neighbor);
        }

    }
}

因为城市的唯一标识已知，且与数组下标有关，可以简化

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int[] visited = new int[isConnected.length];
        int count = 0;
        for (int i = 0; i < isConnected.length; i++) {
            if (visited[i] == 0) {
                count++;
                dfs(isConnected, visited, i);
            }
        }
        return count;

    }

    public void dfs(int[][] isConnected, int[] visited, int cur) {
        if (visited[cur] == 1) return;
        visited[cur] = 1;
        for (int i = 0; i < isConnected.length; i++) {
            if (isConnected[cur][i] == 1) {
                dfs(isConnected, visited, i);
            }
        }

    }
}

207. 课程表 - 力扣（LeetCode）

经典的拓扑遍历，需要好好记忆

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        Map<Integer, Set<Integer>> out = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            int ai = prerequisites[i][0];
            int bi = prerequisites[i][1];
            in[ai]++;
            Set<Integer> set = out.getOrDefault(bi, new HashSet<>());
            set.add(ai);
            out.put(bi, set);
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < in.length; i++) {
            if (in[i] == 0) {
                queue.add(i);
            }
        }
        if (queue.isEmpty()) return false;
        // queue中有多少课程，代表有多少课程是可以学习的
        int count = queue.size();
        while (!queue.isEmpty()) {
            int cur = queue.pollLast();
            // 这里要用getOrDefault，避免NULL
            for (int t : out.getOrDefault(cur, new HashSet<>())) {
                in[t]--;
                if (in[t] == 0) {
                    count++;
                    queue.offerFirst(t);
                }
            }
        }
        if (count == numCourses) return true;
        return false;
    }
}

797. 所有可能的路径 - 力扣（LeetCode）

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // 因为不存在环路，且该图是有向图，其实不需要visited，dfs本身的循环就防止了访问重复节点
        // int[] visited = new int[graph.length];
        path.add(0);
        // dfs(graph, visited, 0);
        dfs(graph, 0);
        return ans;

    }

    public void dfs(int[][] graph, int i) {
        if (i == graph.length - 1) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // if (visited[i] == 1) return;
        // visited[i] = 1;
        for (int t : graph[i]) {
            path.add(t);
            dfs(graph, t);
            path.remove(path.size() - 1);
        }

        // visited[i] = 0;

    }
}

785. 判断二分图 - 力扣（LeetCode）

这题好像是并查集的模板题，可以好好看一看

class Solution {
    int UNCOLORED = 0;
    int RED = 1;
    int GREEN = -1;
    int[] color;
    boolean vaild;
    public boolean isBipartite(int[][] graph) {
        color = new int[graph.length];
        vaild = true;
        for (int i = 0; i < graph.length && vaild; i++) {
            if (color[i] == UNCOLORED) {
                dfs(graph, RED, i);
            }
        }
        return vaild;
    }

    public void dfs(int[][] graph, int c, int cur) {
        color[cur] = c;
        int cNei = c == RED ? GREEN : RED;
        for (int t : graph[cur]) {
            if (color[t] == UNCOLORED) {
                dfs(graph, cNei, t);
                if (!vaild) return;
            } else if (color[t] != cNei) {
                vaild = false;
                return;
            }
        }
    }
}

项目小计

今天决定开始制作我的第一个大型业务项目了