leetcode contest 321
leetcode contest 321
前三题确实是太简单了，最后一题稍微有点难度。
6245. 找出中枢整数
给你一个正整数 n ，找出满足下述条件的 中枢整数 x ：
1和x之间的所有元素之和等于x和n之间所有元素之和。
返回中枢整数 x 。如果不存在中枢整数，则返回 -1 。题目保证对于给定的输入，至多存在一个中枢整数。
示例 1：
1 | |
示例 2：
1 | |
示例 3：
1 | |
提示：
1 <= n <= 1000
地址
https://leetcode.cn/contest/weekly-contest-321/problems/find-the-pivot-integer/
题意
直接遍历即可
思路
- 直接遍历求出前 $i$ 项和与后 $n - i + 1$ 项的和，利用等差数列求和公式即可。
- 复杂度分析：
- 时间复杂度：$O(1)$。
- 空间复杂度：$O(1)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13class 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：
1 | |
示例 2：
1 | |
示例 3：
1 | |
提示：
1 <= s.length, t.length <= 105s和t仅由小写英文字母组成
地址
题意
双指针
思路
- 典型的双指针，$i$ 指向 $s$，$j$ 指向 $t$，如果满足 $s[i] = t[j]$，此时向右移动 $j$，最终返回 $|t| - j$ 即可。即找到此时 $s$ 中为 $t$ 的子序列的最多数目。
- 复杂度分析：
- 时间复杂度：时间复杂度为 $O(m + n)$，其中 $m,n$ 表示两个字符串的长度。
- 空间复杂度：空间复杂度为 $O(1)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13class 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：
1 | |
示例 2：
1 | |
提示：
- 给定列表中的节点数目在范围
[1, 105]内 1 <= Node.val <= 105
地址
https://leetcode.cn/contest/weekly-contest-321/problems/remove-nodes-from-linked-list/
题意
单调栈
思路
- 不知道这个题目有啥意思，简单的一个单调栈就全部搞定。
- 复杂度分析
- 时间复杂度：时间复杂度为 $O(n)$，$n$ 为给定的节点的数目。
- 空间复杂度：空间复杂度为 $O(n)$，$n$ 为给定的节点的数目。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class 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;
}
}; - 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class 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：
1 | |
示例 2：
1 | |
提示：
n == nums.length1 <= n <= 1051 <= nums[i], k <= nnums中的整数互不相同
地址
https://leetcode.cn/contest/weekly-contest-321/problems/count-subarrays-with-median-k/
题意
滑动窗口
思路
- 设 $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$；
- 我们依次记录所有 $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]$。
- 复杂度分析：
1 | |
欢迎关注和打赏，感谢支持！
- 关注我的博客: http://whistle-wind.com/
- 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
- 关注我的微信公众号: 公务程序猿
leetcode contest 321
http://example.com/2026/09/08/力扣周赛题解/83/