LeetCode第51场双周赛题解

T1-将所有数字用字符替换

• 思路：模拟
• 字母的ASCII码可以直接与整数进行运算，用于获得字母表往后的某个字母

class Solution {
    public String replaceDigits(String s) {
        int n = s.length();
        char[] res = new char[n];
        for(int i = 0; i < n; i ++){
            if(i % 2 == 1) res[i] = shift(s.charAt(i - 1), s.charAt(i) - '0');
            else res[i] = s.charAt(i);
        }
        return new String(res);
    }

    char shift(char c, int x){
        return (char)(c + x);
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

T2-座位预约管理系统

• 思路：最小堆
• 考虑一个能满足以下条件的数据结构：
  1. 快速找最小元素并删除
  2. 插入元素
• 最小堆正好满足这两个条件

class SeatManager {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    public SeatManager(int n) {
        for(int i = 1; i <= n; i++){
            heap.offer(i);
        }
    }

    public int reserve() {
        return heap.poll();
    }

    public void unreserve(int x) {
        heap.offer(x);
    }
}

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(n)$

T3-减小和重新排列数组后的最大元素

• 思路：贪心
• 先对数组进行从小到大的排序（重新排列），然后强制使得第一个元素变成1，往后的每个元素，最大只能比前一个元素大1，最小只能与前一个元素相等，答案为处理后的数组最后一个元素

class Solution {
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        int n = arr.length;
        Arrays.sort(arr);
        arr[0] = 1;
        for(int i = 1; i < n; i++){
            arr[i] = Math.min(arr[i - 1] + 1, arr[i]);
        }
        return arr[n-1];
    }
}

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(1)$

T4-最近的房间

• 思路：平衡树（有序集合） + 离线思想
• 将所有房间按面积从大到小进行排序，将查询数组按面积从大到小进行排序，这样可以使得遍历到某个查询时，面积比查询大的房间都已经被考虑过了，还可以供后面的查询使用，整个房间数组只需要扫描一次
• 考虑一个数据结构存放所有已经考虑过的房间，且能快速找到集合中最接近某个数的值：由于最接近x包含了比x大、小、相等三种情况，所以需要快速找到小于x的最大数和大于x的最小数，可以用平衡树的ceil和floor方法在$O(logn)$的时间内满足这个要求
• 由于绝对值相同选最小的id，所以我们在两个最接近的数的情况下优先取小于x的数

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] qs) {
        int n = rooms.length, m = qs.length;
        int[] res = new int[m];
        Integer[] pos = new Integer[m];
        for(int i = 0; i < m; i++){
            pos[i] = i;
        }
        Arrays.sort(pos, (o1, o2) -> qs[o2][1] - qs[o1][1]);
        Arrays.sort(rooms, (o1, o2) -> o2[1] - o1[1]);
        int k = 0;
        TreeSet<Integer> set = new TreeSet<>();
        for(int x: pos){
            int id = qs[x][0], area = qs[x][1];
            while(k < n && rooms[k][1] >= area) {
                set.add(rooms[k++][0]);
            }
            if(set.size() == 0) res[x] = -1;
            else{
                Integer floor = set.floor(id);
                Integer ceil = set.ceiling(id);
                if(floor == null || ceil == null) res[x] = floor == null ? ceil : floor;
                else{
                    int a = Math.abs(floor - id), b = Math.abs(ceil - id);
                    res[x] = a <= b ? floor : ceil;
                }
            }
        }
        return res;
    }
}

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(n)$