力扣第 321 场周赛

比赛时间 2022-11-27。本场周赛国服共 1065 人 AK。

T1. 找出中枢整数（3 分）

解题思路

枚举。

时间复杂度：O(n)。

参考代码

class Solution {
    public int pivotInteger(int n) {
        for (int i = 1; i <= 1000; i++) {
            if ((1 + i) * i == (i + n) * (n - i + 1)) {
                return i;
            }
        }
        return -1;
    }
}

T2. 追加字符以获得子序列（4 分）

解题思路

双指针。

时间复杂度：O(|s| + |t|)。

参考代码

class Solution {
    public int appendCharacters(String s, String t) {
        int p = 0;
        int q = 0;
        while (p < s.length() && q < t.length()) {
            if (s.charAt(p) == t.charAt(q)) {
                p++;
                q++;
            } else {
                p++;
            }
        }
        return t.length() - q;
    }
}

T3. 从链表中移除节点（5 分）

解题思路

模拟。后往前枚举，丢弃小于当前最大值的数即可。

时间复杂度：O(n)。

参考代码

class Solution {
    public ListNode removeNodes(ListNode head) {
        int[] arr = toArray(head);

        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = arr.length - 1; i >= 0; i--) {
            if (stack.isEmpty() || stack.peek() <= arr[i]) {
                stack.push(arr[i]);
            }
        }
        int sz = stack.size();
        int[] nums = new int[sz];
        for (int i = 0; i < sz; i++) {
            nums[i] = stack.pop();
        }

        ListNode dummy = new ListNode(-1);
        ListNode head1 = dummy;
        for (int num : nums) {
            head1.next = new ListNode(num);
            head1 = head1.next;
        }
        return dummy.next;
    }

    private int[] toArray(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

T4. 统计中位数为 K 的子数组（6 分）

解题思路

贪心 + 前缀和。

• 设区间 [l,r] 内比 k 大的数有 a 个，比 k 小的数有 b 个；
• 当 0 <= b-a <= 1 时，区间满足要求（其中 l 取值范围为 [0, ki], r 取值范围为 [ki, n-1]）；
• 使用前缀和预处理，可在 时间复杂度 O(n^2) 内求出区间 [l,r] 是否符合要求；
• 注意到 l <= ki <= r，可使用 HashMap 预处理 r 的所有可能取值及频次进行优化；

时间复杂度：O(n)。

参考代码

class Solution {
    public int countSubarrays(int[] nums, int k) {
        int len = nums.length;
        int[] arr = new int[len];
        int kId = -1;
        for (int i = 0; i < len; i++) {
            if (nums[i] > k) {
                arr[i] = 1;
            } else if (nums[i] < k) {
                arr[i] = -1;
            } else {
                kId = i;
            }
        }

        int[] preSum = new int[len + 1];
        Map<Integer, Integer> cntMap = new HashMap<>();
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + arr[i];
            if (i >= kId) {
                cntMap.put(preSum[i + 1], cntMap.getOrDefault(preSum[i + 1], 0) + 1);
            }
        }

        int res = 0;
        for (int i = 0; i <= kId; i++) {
//            for (int j = kId; j < len; j++) {
//                int sum = preSum[j + 1] - preSum[i];
//                if (sum == 0 || sum == 1) {
//                    res++;
//                }
//            }
            res += cntMap.getOrDefault(preSum[i], 0);
            res += cntMap.getOrDefault(preSum[i] + 1, 0);
        }
        return res;
    }
}

（全文完）