leetcode contest 321

前三题确实是太简单了，最后一题稍微有点难度。

6245. 找出中枢整数

给你一个正整数 n ，找出满足下述条件的 中枢整数 x ：

• 1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。

返回中枢整数 x 。如果不存在中枢整数，则返回 -1 。题目保证对于给定的输入，至多存在一个中枢整数。

示例 1：

输入：n = 8
输出：6
解释：6 是中枢整数，因为 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21 。

示例 2：

输入：n = 1
输出：1
解释：1 是中枢整数，因为 1 = 1 。

示例 3：

输入：n = 4
输出：-1
解释：可以证明不存在满足题目要求的整数。

提示：

• 1 <= n <= 1000

地址

https://leetcode.cn/contest/weekly-contest-321/problems/find-the-pivot-integer/

题意

直接遍历即可

思路

1. 直接遍历求出前 $i$ 项和与后 $n - i + 1$ 项的和，利用等差数列求和公式即可。
2. 复杂度分析：

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

代码

class Solution {
public:
    int pivotInteger(int n) {
        for (int i = 1; i <= n; i++) {
            int left = i * (i + 1) / 2;
            int right = (n - i + 1) * (i + n) / 2;
            if (left == right) {
                return i;
            }
        }
        return -1;
    }
};

6246. 追加字符以获得子序列

给你两个仅由小写英文字母组成的字符串 s 和 t 。

现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。

子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。

示例 1：

输入：s = "coaching", t = "coding"
输出：4
解释：向 s 末尾追加字符串 "ding" ，s = "coachingding" 。
现在，t 是 s ("coachingding") 的一个子序列。
可以证明向 s 末尾追加任何 3 个字符都无法使 t 成为 s 的一个子序列。

示例 2：

输入：s = "abcde", t = "a"
输出：0
解释：t 已经是 s ("abcde") 的一个子序列。

示例 3：

输入：s = "z", t = "abcde"
输出：5
解释：向 s 末尾追加字符串 "abcde" ，s = "zabcde" 。
现在，t 是 s ("zabcde") 的一个子序列。 
可以证明向 s 末尾追加任何 4 个字符都无法使 t 成为 s 的一个子序列。

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 仅由小写英文字母组成

地址

https://leetcode.cn/contest/weekly-contest-321/problems/append-characters-to-string-to-make-subsequence/

题意

双指针

思路

1. 典型的双指针，$i$ 指向 $s$，$j$ 指向 $t$，如果满足 $s[i] = t[j]$，此时向右移动 $j$，最终返回 $|t| - j$ 即可。即找到此时 $s$ 中为 $t$ 的子序列的最多数目。
2. 复杂度分析：

• 时间复杂度：时间复杂度为 $O(m + n)$，其中 $m,n$ 表示两个字符串的长度。
• 空间复杂度：空间复杂度为 $O(1)$。

代码

class Solution {
public:
    int appendCharacters(string s, string t) {
        int i = 0, j = 0;
        while (i < s.size() && j < t.size()) {
            if (s[i] == t[j]) {
                j++;
            }
            i++;
        } 
        return t.size() - j;
    }
};

6247. 从链表中移除节点

给你一个链表的头节点 head 。

对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。

返回修改后链表的头节点 head 。

示例 1：

输入：head = [5,2,13,3,8]
输出：[13,8]
解释：需要移除的节点是 5 ，2 和 3 。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。

示例 2：

输入：head = [1,1,1,1]
输出：[1,1,1,1]
解释：每个节点的值都是 1 ，所以没有需要移除的节点。

提示：

• 给定列表中的节点数目在范围 [1, 105] 内
• 1 <= Node.val <= 105

地址

https://leetcode.cn/contest/weekly-contest-321/problems/remove-nodes-from-linked-list/

题意

单调栈

思路

1. 不知道这个题目有啥意思，简单的一个单调栈就全部搞定。
2. 复杂度分析

• 时间复杂度：时间复杂度为 $O(n)$，$n$ 为给定的节点的数目。
• 空间复杂度：空间复杂度为 $O(n)$，$n$ 为给定的节点的数目。

代码

class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        vector<int> st;
        while(head) {
            while (st.size() > 0 && head->val > st.back()) {
                st.pop_back();
            }
            st.emplace_back(head->val);
            head = head->next;
        }
        ListNode *res = new ListNode(st[0]);
        ListNode *curr = res;
        for (int i = 1; i < st.size(); i++) {
            curr->next = new ListNode(st[i]);
            curr= curr->next;
        }
        return res;
    }
};

• 递归

  class Solution { public: ListNode* removeNodes(ListNode* head) { if (!head) { return nullptr; } ListNode *node = removeNodes(head->next); if (node && node->val > head->val) { return node; } else { head->next = node; return head; } } };

6248. 统计中位数为 K 的子数组

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。

统计并返回 num 中的 中位数 等于 k 的非空子数组的数目。

注意：

• 数组的中位数是按

  递增

  顺序排列后位于

  中间

  的那个元素，如果数组长度为偶数，则中位数是位于中间靠

  左

  的那个元素。

  • 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。

• 子数组是数组中的一个连续部分。

示例 1：

输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。

示例 2：

输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i], k <= n
• nums 中的整数互不相同

地址

https://leetcode.cn/contest/weekly-contest-321/problems/count-subarrays-with-median-k/

题意

滑动窗口

思路

1. 设 $i$ 指向连续子数组的左侧， $j$ 指向符合题目要求的连续子数组的右侧，则此时子数目的数目为 $j - i + 1$，子数组 $nums[i,\cdots,j]$ 中大于 $k$ 的数目为 $x$，小于 $k$ 的数目为 $y$，则分类讨论如下:

• 此时一定满足 $j - i + 1 = x + y + 1$；
• 如果满足 $k$ 为中位数，则此时一定满足:
  • 如果 $j - i + 1$ 为偶数，则此时一定满足 $y - x = 1$ 才能使得连续子数组 $nums[i,\cdots,j]$ 的中位数为 $k$, 此时 $y - x = 1$；
  • 如果 $j - i + 1$ 为奇数数，则此时一定满足 $x = y$，才能使得连续子数组 $nums[i,\cdots,j]$ 的中位数为 $k$, 此时 $y - x = 0$；

2. 我们依次记录所有 $i < index(k)$ 处当前大于 $k$ 的数目与小于 $k$ 的数目之差为 $diff$ 的索引个数 $cnt[diff]$。根据上述推论可以知道，加入我们当前遍历到索引 $j, j \ge index(k)$ 处，则，此时大于 $k$ 的数字个数为 $g[i]$，小于 $k$ 的数字个数为 $l[i]$，此时二者之差为 $diff = g[i] - l[i]$，

• 假设我们当前的使得大于 $k$ 的数目与小于 $k$ 的数目相等，此时我们只需在 $i < k$ 处找到符合条件的索引的 $i$ 的个数即可，此时我们只需要查询 $cnt[g[i] - l[i]]$ 即可。
• 假设我们当前的使得大于 $k$ 的数目与小于 $k$ 的数目之差为 $1$，此时我们只需在 $i < k$ 处找到符合条件的索引的 $i$ 的个数即可，此时我们只需要查询 $cnt[g[i] - l[i] - 1]$ 即可。
• 以 $i$ 为结尾的连续子数组中符合满足要求的子数组的个数即为 $cnt[g[i] - l[i]] + cnt[g[i] - l[i] - 1]$。

2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。
• 空间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。

代码

class Solution {
public:
    int countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int idx = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == k) {
                idx = i;
                break;
            }
        }
        unordered_map<int, int> cnt;
        cnt[0]++;
        int diff = 0;
        for (int i = 0; i < idx; i++) {
            if (nums[i] > k) {
                diff++;
            } else if (nums[i] < k) {
                diff--;
            }
            cnt[diff]++;
        }
        int res = 0;
        for (int i = idx; i < n; i++) {
            if (nums[i] > k) {
                diff++;
            } else if (nums[i] < k) {
                diff--;
            }            
            res += cnt[diff] + cnt[diff - 1];
        }
        return res;
    }
};

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://whistle-wind.com/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿