第51场双周赛 (AK)

将所有数字用字符替换

class Solution {
    public String replaceDigits(String s) {
        int len = s.length();
        char[] chars = s.toCharArray();
        for (int i = 1; i < len; i += 2) {
            chars[i] = shift(chars[i - 1], chars[i]);
        }
        return String.valueOf(chars);
    }

    private static char shift (char c, int n) {
        if (c + n - '0' > 'z') return 'z';
        return (char) (c + n - '0');
    }
}

座位预约管理系统

//去元素时间复杂度O(n)
class SeatManager {
    boolean[] seats;
    int empty;
    public SeatManager(int n) {
        seats = new boolean[n];
        empty = n;
    }

    public int reserve() {
        for (int i = 0; i < seats.length; ++i) {
            if (!seats[i]){
                seats[i] = true;
                return i + 1;
            }
        }
        return -1;
    }

    public void unreserve(int seatNumber) {
        seats[seatNumber - 1] = false;
    }
}

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager obj = new SeatManager(n);
 * int param_1 = obj.reserve();
 * obj.unreserve(seatNumber);
 */

优先队列

class SeatManager {
    //以O(1)取出队列中权值最小的元素,再以O(logn)维护队列
    PriorityQueue<Integer> seats = new PriorityQueue<>();
    public SeatManager(int n) {
        for (int i = 1; i <= n; ++i) {
            seats.add(i);
        }
    }

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

    public void unreserve(int seatNumber) {
        seats.add(seatNumber);
    }
}

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

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

最近的房间

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        //先排序
        Arrays.sort(rooms, (o1, o2) -> o2[1] - o1[1]);
        int n = queries.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int absId = Integer.MAX_VALUE;
            int minId = -1;
            for (int j = 0; j < rooms.length; ++j) {
                if (rooms[j][1] < queries[i][1]) {
                    break;
                }
                int tmp = Math.abs(rooms[j][0] - queries[i][0]);
                if (absId == tmp) {
                    if (minId > rooms[j][0]) minId = rooms[j][0];
                } else if (absId > tmp){
                    absId = tmp;
                    minId = rooms[j][0];
                }
            }
            ans[i] = minId;
        }
        return ans;
    }
}

离线算法 & TreeSet

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int[][] q = new int[queries.length][3];
        for(int i = 0; i < q.length; ++i){
            q[i][0] = queries[i][0];
            q[i][1] = queries[i][1];
            q[i][2] = i; // 记录在queries中的原位置
        }
        // 排序
        Arrays.sort(q, (x, y) -> y[1] - x[1]);
        Arrays.sort(rooms, (x, y) -> y[1] - x[1]);

        TreeSet<Integer> set = new TreeSet<>();
        int idx = 0;
        int[] ans = new int[q.length];
        Arrays.fill(ans, -1);
        for (int i = 0; i < q.length; ++i) {
            while (idx < rooms.length && rooms[idx][1] >= q[i][1]) {
                set.add(rooms[idx][0]);
                idx += 1;
            }
            Integer a = set.floor(q[i][0]); // 返回此set中小于或等于给定元素的最大元素
            Integer b = set.ceiling(q[i][0]); // 返回此set中大于或等于给定元素的最小元素
            if (a == null && b == null){
                ans[q[i][2]] = -1;
            } else if (b == null || a == null){
                ans[q[i][2]] = (a == null) ? b : a;
            } else {
                ans[q[i][2]] = ((q[i][0]-a) <= (b-q[i][0])) ? a : b;
            }
        }
        return ans;
    }
}

TreeSet常用方法

LeetCode Weekly 238

K进制表示下的各位数字总和

class Solution {
    public int sumBase(int n, int k) {
        int ans = 0;
        while(n != 0){
            ans += n % k;
            n /= k;
        }
        return ans;
    }
}

— 以下两题为双指针法的两种题型: 前者两个指针一起移动,后者固定一个指针移动另一个指针。 —

最高频元素的频数

二分

能使用二分的依据:j往左走需要的次数严格单调递增。

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] sums = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }

        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int l = 1, r = i;
            while (l < r) {
                int mid = l + r >> 1;
                if ((i - mid + 1) * nums[i - 1] - (sums[i] - sums[mid - 1]) <= k) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            ans = Math.max(ans, i - r + 1);
        }
        return ans;
    }
}

双指针

能使用双指针的依据: i往后走,i对应的j一定单调往后走。

class Solution {
    public int maxFrequency(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int[] sums = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }

        int ans = 0;
        for (int i = 1, j = 1; i <= n; ++i) {
            while ((i - j + 1) * nums[i - 1] - (sums[i] - sums[j - 1]) > k) {
                ++j;
            }
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }
}

所有元音按顺序排布的最长子字符串

动态规划 + 哈希表

class Solution {
    public int longestBeautifulSubstring(String word) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();

        int n = word.length();
        int[] dp = new int[n];
        dp[0] = 1;
        int ans = 0;
        map.put(word.charAt(0), 1);
        for (int i = 1; i < n; ++i) {
            char tmp = word.charAt(i);
            if (tmp >= word.charAt(i - 1)) {
                dp[i] = dp[i - 1] + 1;
                map.put(tmp, 1);
                if (map.getOrDefault('a', 0) == 1 && map.getOrDefault('e', 0) == 1 && map.getOrDefault('i', 0) == 1 && map.getOrDefault('o',0) == 1 && map.getOrDefault('u',0) == 1){
                    ans = Math.max(ans, dp[i]);
                }
            }
            else {
                dp[i] = 1;
                map.clear();
                map.put(tmp, 1);
            }
        }
        return ans;
    }
}

注:执行时间较高

双指针

class Solution {
    public int longestBeautifulSubstring(String word) {
        int n = word.length();
        int ans = 0;
        String p = "aeiou";

        for (int i = 0; i < n; ++i) {
            if (word.charAt(i) != 'a') continue;
            int j = i, k = 0;
            while (j < n) {
                if (word.charAt(j) == p.charAt(k)) ++j;
                else {
                    if (k == 4) break;
                    if (word.charAt(j) == p.charAt(k + 1)) {
                        ++j; ++k;
                    } else break;
                }
                if (k == 4) ans = Math.max(ans, j - i); 
            }
            i = j - 1;
        }
        return ans;
    }
}

最高建筑高度🌟

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        auto&& r = restrictions;
        r.push_back({1,0}); //增加约束
        sort(r.begin(), r.end()); //排序
        if (r.back()[0] != n) {
            r.push_back({n, n - 1}); //增加约束
        }
        int m = r.size();

        //从左向右传递约束
        for (int i = 1; i < m; ++i) {
            r[i][1] = min(r[i][1], r[i - 1][1] + r[i][0] - r[i - 1][0]);
        }
        //从右向左传递约束
        for (int i = m - 2; i >= 0; --i) {
            r[i][1] = min(r[i][1], r[i + 1][1] + (r[i + 1][0] - r[i][0]));
        }

        int ans = 0;
        for (int i = 1; i < m; ++i) {
            //计算 r[i - 1][0] 和 r[i][0] 之间建筑的最大高度
            int best = (r[i - 1][1] + r[i][1] + r[i][0] - r[i - 1][0]) / 2;
            ans = max(ans, best);
        }
        return ans;
    }
};

LeetCode Weekly 237

判断句子是否为全字母句

class Solution {
    public boolean checkIfPangram(String sentence) {
        int ans = 0;
        for (int i = 0; i < sentence.length(); ++i) {
            ans |= (1 << (sentence.charAt(i) - 'a'));
        }
        return ans == (1 << 26) - 1;
    }
}

雪糕的最大数量

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int cnt = 0;
        Arrays.sort(costs);
        for (int cost : costs) {
            if (coins >= cost) {
                coins -= cost;
                ++cnt;
            }
            else break;
        }
        return cnt;
    }
}

单线程CPU🌟

排序 & 优先队列(小根堆)

class Solution {
    class Task {
        int id;
        int enqueueTime;
        int processingTime;

        public Task (int id, int enqueueTime, int processingTime) {
            this.id = id;
            this.enqueueTime = enqueueTime;
            this.processingTime = processingTime;
        }
    }
    public int[] getOrder(int[][] tasks) {
        int len = tasks.length;
        List<Task> taskList = new ArrayList<Task>();
        for (int i = 0; i < len; ++i) {
            taskList.add(new Task(i, tasks[i][0], tasks[i][1]));
        }
        //按入队时间排序
        Collections.sort(taskList, (t1, t2) -> t1.enqueueTime - t2.enqueueTime);
        //优先队列
        PriorityQueue<Task> minHeap = new PriorityQueue<Task>((t1, t2) -> {
            //短作业优先
            if (t1.processingTime != t2.processingTime) return t1.processingTime - t2.processingTime;
            //运行时间相等时按照id排序
            else return t1.id - t2.id;
        });

        long now = 0; //时间戳
        int[] ret = new int[len];
        int i = 0; //taskList坐标
        int j = 0; //ret坐标
        while (i < len) {
            //将所有开始时间小于等于当前时间戳的task放入优先队列中
            while (i < len && taskList.get(i).enqueueTime <= now) {
                minHeap.offer(taskList.get(i++));
            }
            //当堆中没有任务时,前移时间戳
            if (minHeap.isEmpty()) {
                now = (long) taskList.get(i).enqueueTime;
                //加入task进队列
                while (i < len && taskList.get(i).enqueueTime <= now) {
                    minHeap.offer(taskList.get(i++));
                }
            }
            //取出任务执行
            Task t = minHeap.poll();
            ret[j++] = t.id;
            now += (long) t.processingTime;
        }
        //此时所有taskList所有任务均已执行或加入队列中
        //清空队列剩余任务
        while (!minHeap.isEmpty()) {
            ret[j++] = minHeap.poll().id;
        }
        return ret;
    }
}

所有数对按位与结果的异或和

逐位确定结果

class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int ans = 0;
        //依次确定答案二进制表示中的每一位
        for (int k = 30; k >= 0; --k) {
            int cnt1 = 0;
            for (int num : arr1) {
                if ((num & (1 << k)) != 0) {
                    ++cnt1;
                }
            }
            int cnt2 = 0;
            for (int num : arr2) {
                if ((num & (1 << k)) != 0) {
                    ++cnt2;
                }
            }
            //当cnt1和cnt2均为奇数时,结果中k位为1
            //一个数与 0 进行异或运算,它的值不改变
            if ((cnt1 % 2 == 1) && (cnt2 % 2 == 1)) {
                ans |= (1 << k);
            }
        }
        return ans;
    }
}

利用与异或运算法则

class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int p1 = 0, p2 = 0;
        for (int i : arr1) {
            p1 ^= i;
        }
        for (int j : arr2) {
            p2 ^= j;
        }
        return p1 & p2;
    }
}

Try and fail, but don't fail to try.