729. 我的日程安排表 I / 剑指 Offer II 106. 二分图

729. 我的日程安排表 I【中等题】【每日一题】

思路：【TreeMap】

学习TreeMap的使用，两种方式。
详见代码注释。

代码1：

class MyCalendar {
    

    TreeMap<Integer,Integer> treeMap;

    public MyCalendar() {
    
        treeMap = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
    
        //第一个大于等于 start 的区间
        Map.Entry<Integer,Integer> ceilingEntry = treeMap.ceilingEntry(start);
        //第一个小于等于 start 的区间
        Map.Entry<Integer,Integer> floorEntry = treeMap.floorEntry(start);
        
        //如果 floorEntry 为 null 或者 floorEntry 对应的值(表示区间右端点) 小于等于 start
        // 且 同时 ceilingEntry为 null 或者 ceilingEntry 对应的键(表示区间左端点) 大于等于 end
        // 那么说明当前这段日程区间 可以插入到treeMap表示的日历中，且不会导致重复预订
        if((floorEntry == null || floorEntry.getValue() <= start)
            && (ceilingEntry == null || end <= ceilingEntry.getKey())){
    
                treeMap.put(start,end);
                return true;
        }
        //如果不满足上述条件 那么不能将日常添加到日历中，返回false
        return false;
    }
}

/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */

代码2：

class MyCalendar {
    

    TreeMap<Integer,Integer> map;

    public MyCalendar() {
    
        //初始化TreeMap，map中key为区间左端点（包含），value为区间右端点（不包含）
        map = new TreeMap<>();
        //在map中添加整个区间的大边界
        //最左侧为-1
        map.put(-1,-1);
        //最右侧为1000000001
        map.put(1000000001,1000000001);
    }

    public boolean book(int start, int end) {
    
        //求map中 要插入区间左端点 start 左右两侧的值，分别设为left 和right，left表示比start小的区间左端点 right表示比start大的区间左端点
        Integer left = map.floorKey(start),right = map.ceilingKey(start);
        //如果right值小于end 表示比start大的区间左端点比end小 这时插入[start,end)一定会造成区间重叠，返回false 
        //如果left对应的区间右端点值比start大 也会造成区间重叠 返回false
        if (right < end || map.get(left) > start){
    
            return false;
        }
        //排除上述情况 区间不会重叠，则将日程成功插入
        map.put(start,end);
        return true;
    }
}

/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */

---

剑指 Offer II 106. 二分图【中等题】

思路：【DFS】

读懂题目很重要，题目中对二分图的定义是：
将一个图的所有节点分为两个独立的子集A和B，并使图中每一条边的两个节点一个来自集合A，一个来自集合B。

那么我们可以借用染色的概念来对无向图进行尝试二分，初始时图中的所有节点均为无色状态，从任一节点出发，遍历图中所有节点，如果节点未染色，则将其染为红色，
然后遍历这个节点的所有邻接点，如果邻接点未被染色，则将其染为绿色，并对这个邻接点的所有邻接点进行搜索，未染色则染为红色；如果邻接点已被染色，且与当前节点颜色相同，那么说明染色失败，函数返回false。
详细过程可以看注释。思路及代码参考自官方题解。

代码：

class Solution {
    
    //定义color数组，用来标记无向图中每个节点的颜色
    static int[] color;
    //定义标志位valid，用于表示当前状态是否有效
    static boolean valid;
    //定义静态变量用于标记节点颜色
    static final int UNCOLORED = 0;
    static final int RED = 1;
    static final int GREEN = 2;

    public boolean isBipartite(int[][] graph) {
    
        int n = graph.length;
        //初始化valid为true，表示起始状态有效
        valid = true;
        //初始化颜色数组color
        color = new int[n];
        //color赋初值为 无色 UNCOLORED
        Arrays.fill(color,UNCOLORED);
        //遍历无向图中每个有效节点
        for (int i = 0; i < n && valid; i++) {
    
            //如果当前节点未上色，则调用dfs函数将其染为红色
            if (color[i] == UNCOLORED){
    
                dfs(i,RED,graph);
            }
        }
        //返回无向图遍历完成后节点的有效状态
        return valid;
    }
    public void dfs(int node,int c,int[][] graph){
    
        //将当前节点node染为指定颜色c
        color[node] = c;
        //记录当前节点邻接点的目标颜色cNei，如果c为红色，则cNei为绿色，如果c为绿色，则cNei为红色
        int cNei = c == RED ? GREEN : RED;
        //遍历当前节点的每一个邻接点neighbor
        for (int neighbor : graph[node]) {
    
            //如果邻接点无色，则将邻接点染色，即节点为红，则将邻节点染为绿色，节点为绿，则将邻接点染为红色
            if (color[neighbor] == UNCOLORED){
    
                //将邻接点染为cNei颜色
                dfs(neighbor,cNei,graph);
                //如果染完后，发现valid为false，那么染色函数直接返回，不用继续染下一个邻接点了
                if (!valid){
    
                    return;
                }
            }else if (color[neighbor] != cNei){
    
                //如果邻接点的颜色已染色，且其颜色不是将要染成的颜色(就是与当前节点颜色相同)
                //那么将valid标记为false，表示染色失败。染色函数返回
                valid = false;
                return;
            }
        }
    }
}