2022-07-05

[Zheaoli]

2022-07-05

[SaraadKun]

729. 我的日程安排表 I

class MyCalendar {

    TreeMap<Integer, Integer> map;

    public MyCalendar() {
        map = new TreeMap<>();
    }

     /*
     使用有序集合+二分查找来实现, 空间复杂度O(n), 总的时间复杂度O(mlogn) n为总的数据集大小,m为查询次数
     TreeMap存储区间,key为start,value为end
     插入时找到第一个小于start的区间[lStart, lEnd)以及第一个大于等于start的区间[rStart, rEnd)
     1.若start < lEnd || end > rStart,则返回false
     2.否则 start >= lEnd && end<=rStart 可以执行添加操作
        2.1.若start == lEnd,更新[lStart, lEnd)为[lStart, end); curKey = lStart
        2.2.否则新增区间[start, end); curKey = start
        2.3.检查若end == rStart,更新curKey的区间为[curKey, rEnd), 同时删除rStart
     若[lStart, lEnd)不存在,1.中操作不需判断start < lEnd; 跳过2.1步
     若[rStart, rEnd)不存在,1.中操作不需判断end > rStart; 跳过2.3步
     */
    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> lEntry = map.lowerEntry(start);
        Map.Entry<Integer, Integer> rEntry = map.ceilingEntry(start);
        if ((lEntry != null && lEntry.getValue() > start) || (rEntry != null && end > rEntry.getKey())) {
            return false;
        }
        int curKey = start;
        if (lEntry != null && lEntry.getValue() == start) {
            curKey = lEntry.getKey();
        } 
        map.put(curKey, end);
        if (rEntry != null && end == rEntry.getKey()) {
            map.put(curKey, rEntry.getValue());
            map.remove(rEntry.getKey());
        }
        return true;
    }
}

---

WeChat: Saraad

[SaraadKun]

1765. 地图中的最高点

class Solution {

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

    public int[][] highestPeak(int[][] isWater) {
        //找到所有水域点,加入队列,同时标记所有水域点高度为0,陆地点为-1(代表未访问)
        //BFS,每一轮循环标记的高度+1,直至循环结束
        int m = isWater.length, n = isWater[0].length;
        int[][] ans = new int[m][n];
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    ans[i][j] = 0;
                } else {
                    ans[i][j] = -1;
                }
            }
        }
        //BFS
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && ans[nx][ny] == -1) {
                        ans[nx][ny] = ans[x][y] + 1;
                        q.offer(new int[]{nx, ny});
                }
            }
        }
        return ans;
    }
}

---

WeChat: Saraad