力扣第 296 场周赛

比赛时间 2022-06-05。本场周赛国服共 1455 人 AK。。

T1. 极大极小游戏（3 分）

解题思路

模拟。

时间复杂度：O(n)。因为 1 + 1/2 + 1/4 + 1/8 + ··· 渐近于 2。

参考代码

class Solution {
    public int minMaxGame(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }

        int[] newNums = new int[n / 2];
        for (int i = 0; i < n / 2; i++) {
            if (i % 2 == 0) {
                newNums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
            } else {
                newNums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
            }
        }
        return minMaxGame(newNums);
    }
}

T2. 划分数组使最大差为 K（4 分）

解题思路

贪心。排序后滑动窗口计数即可。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public int partitionArray(int[] nums, int k) {
        int len = nums.length;
        Arrays.sort(nums);

        int cnt = 0;
        int pre = nums[0];
        int idx = 0;
        while (idx < len) {
            while (idx < len && nums[idx] - pre <= k) {
                idx++;
            }
            cnt++;
            if (idx < len) {
                pre = nums[idx];
            }
        }
        return cnt;
    }
}

T3. 替换数组中的元素（5 分）

解题思路

HashMap 模拟更新，离线还原。

时间复杂度：O(n + m)。

参考代码

class Solution {
    public int[] arrayChange(int[] nums, int[][] operations) {
        int n = nums.length;

        // 预处理下标
        Map<Integer, List<Integer>> idxListMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            idxListMap.computeIfAbsent(nums[i], key -> new ArrayList<>()).add(i);
        }

        // 模拟
        for (int[] operation : operations) {
            int oldKey = operation[0];
            int newKey = operation[1];
            List<Integer> idxList = idxListMap.get(oldKey);
            idxListMap.remove(oldKey);
            idxListMap.put(newKey, idxList);
        }

        // 离线还原
        int[] res = new int[n];
        for (Map.Entry<Integer, List<Integer>> entry : idxListMap.entrySet()) {
            int key = entry.getKey();
            List<Integer> idxList = entry.getValue();
            for (int idx : idxList) {
                res[idx] = key;
            }
        }
        return res;
    }
}

T4. 设计一个文本编辑器（6 分）

解题思路

StringBuilder 暴力模拟。注意由于光标的存在，addText 操作时应该用 StringBuilder#insert() 而不是 StringBuilder#append()。

时间复杂度：库函数不讨论时间复杂度。

看了灵佬的直播，也可以用 双向链表、对顶栈(两个栈)、Splay 树 方法实现。时间复杂度：

• addText: O(|text|)
• deleteText: O(k)
• cursorLeft: O(k)
• cursorRight: O(k)

参考代码

class TextEditor {
    private final StringBuilder stringBuilder;
    // 光标
    private int cursor;

    public TextEditor() {
        this.stringBuilder = new StringBuilder();
        this.cursor = 0;
    }

    public void addText(String text) {
        stringBuilder.insert(cursor, text);
        // 光标移动
        cursor += text.length();
    }

    public int deleteText(int k) {
        // 可以删除的字符不会超过光标左侧长度
        int deleteLen = Math.min(k, cursor);
        stringBuilder.delete(cursor - deleteLen, cursor);
        // 光标移动
        cursor -= deleteLen;
        return deleteLen;
    }

    public String cursorLeft(int k) {
        // 光标移动
        cursor = Math.max(0, cursor - k);
        // 返回长度
        int echoLen = Math.min(10, cursor);
        return stringBuilder.substring(cursor - echoLen, cursor);
    }

    public String cursorRight(int k) {
        // 光标移动
        cursor = Math.min(stringBuilder.length(), cursor + k);
        // 返回长度
        int echoLen = Math.min(10, cursor);
        return stringBuilder.substring(cursor - echoLen, cursor);
    }
}

/**
 * Your TextEditor object will be instantiated and called as such:
 * TextEditor obj = new TextEditor();
 * obj.addText(text);
 * int param_2 = obj.deleteText(k);
 * String param_3 = obj.cursorLeft(k);
 * String param_4 = obj.cursorRight(k);
 */

（全文完）