写在前面

开个贴记录一下 刷题的过程，目前参照 leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～

已刷链接：

• 贪心算法：https://www.nowcoder.com/discuss/1051877
• 双指针：https://www.nowcoder.com/discuss/1057237
• 二分查找：https://www.nowcoder.com/discuss/1059986
• 排序：https://www.nowcoder.com/discuss/1063581
• 搜索：https://www.nowcoder.com/discuss/1069407
• 动态规划：https://www.nowcoder.com/discuss/1071676
• 分治法：https://www.nowcoder.com/discuss/1091335
• 链表：https://www.nowcoder.com/discuss/post/419235544456052736
• 树：https://www.nowcoder.com/discuss/post/424955068647997440
• 位运算：https://www.nowcoder.com/discuss/post/427247596613230592

数据结构介绍

二分图

No.1  Graph Bipartite?

题目链接：https://leetcode.com/problems/is-graph-bipartite/

解题思路：

利用队列和广度优先搜索，我们可以对未染色的节点进行染色，并且检查是否有颜色相同的 相邻节点存在。注意在代码中，我们用 0 表示未检查的节点，用 1 和 2 表示两种不同的颜色。

class Solution {
    public boolean isBipartite(int[][] graph) {
        int len = graph.length;
        int[] color = new int[len];
        Queue<Integer> que = new LinkedList<Integer>();
        for (int i = 0; i < len; i++) {
            if (color[i] == 0) {
                color[i] = 1;
                que.offer(i);
            }
            while(que.size() != 0) {
                int cur = que.poll();
                for (int j = 0; j < graph[cur].length; j++) {
                    int neighbor = graph[cur][j];
                    if (color[neighbor] == 0) {
                        color[neighbor] = color[cur] == 1 ? 2 : 1;
                        que.offer(neighbor);
                    } else if (color[neighbor] == color[cur]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

拓扑排序

No.1 Course Schedule II

题目链接：https://leetcode.com/problems/course-schedule-ii/

解题思路：

用 map 建立一个有向图，找到入度为 0 的点放入queue中进行遍历，每遍历一个点把他指向的点的入度-1，

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
        int[] indegree = new int[numCourses];
        int[] res = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            int src = prerequisite[1];
            int end = prerequisite[0];
            indegree[end]++;
            List<Integer> list = graph.getOrDefault(src,new ArrayList<Integer>());
            list.add(end);
            graph.put(src,list);
        }
        Queue<Integer> que = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                que.add(i);
            }
        }
        int i = 0;
        while(que.size() != 0) {
            int cur = que.poll();
            res[i++] = cur;
            if (graph.containsKey(cur)) {
                List<Integer> list = graph.get(cur);
                for(int temp : list) {
                    indegree[temp]--;
                    if (indegree[temp] == 0) {
                        que.offer(temp);
                    }
                }
            }
        }
        if (i == numCourses) {
            return res;
        }
        return new int[0];
    }
}