leetcode第321场周赛:问题转换的思想

  |  

摘要: 本文是 leetcode 第 321 周赛的记录。主要涉及的算法包括数学、贪心、逆向思维、频数前缀和

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


总览

本周进行了 leetcode 第 321 场周赛,本场比赛由佳期投资赞助,前 20 名有奖品。

佳期投资是一家量化对冲私募基金,在上海,成立的十年左右,具体可以看以下官网:

1
https://www.jqinvestments.com/home

本场比赛的难度感觉不大,考察了数学、贪心、逆向思维、频数前缀和等算法点。但是第四题容易想复杂了,然后陷入没有头绪的困境。成绩如下:

本场的亮点是 D 题需要做一定的问题转换,在转换后会规约到已经解决过的基础问题,但是问题转换并不好想。

各个题目涉及到的知识点汇总如下:

往期参加比赛的记录如下:

【连载】leetcode周赛


A 题

2485. 找出中枢整数

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

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

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

提示:

1
1 <= n <= 1000

示例 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
解释:可以证明不存在满足题目要求的整数。

算法: 数学

由等差数列求和公式 $S_{n} = \frac{1}{2}n(a_{1} + a_{n})$。

从 1 到 x 的和为 $\frac{1}{2}x(1 + x)$,从 x 到 n 的和为 $\frac{1}{2}(n + 1 - x)(x + n)$。

两边相等:

得到:

我们要做的就是在 1 到 n 中找到 x 满足上面的公式即可。

代码(C++)

在比赛的时候,写的是二分,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int pivotInteger(int n) {
// 2 * x * x = n * n + n
int left = 1, right = n;
while(left < right)
{
int mid = (left + right) / 2;
if(2 * mid * mid < n * n + n)
left = mid + 1;
else
right = mid;
}
if(2 * left * left == n * n + n)
return left;
return -1;
}
};

也可以直接判断 $x = \sqrt{\frac{1}{2}n(n+1)}$ 是否为整数,代码如下:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int pivotInteger(int n) {
// 2 * x * x = n * n + n
int m = (n * n + n) / 2;
int x = sqrt(m);
if (x * x == m)
return x;
return -1;
}
};

B 题

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

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

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

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

提示:

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

示例 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
2
3
4
5
6
7
             i
s ------------------------------|
0 n

j
t ----------|
0 m

s 的长度为 n,t 的长度为 m。用双串单向双指针,同时从左到右遍历 s 和 t,如果 s[i] == t[j] 则 i, j 同时推进,否则只推进 i。

这样在 s 遍历完的时候,j 到 m 的距离就是还需要增加的字母。返回其长度即可。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int appendCharacters(string s, string t) {
int n = s.size();
int m = t.size();
int i = 0;
int j = 0;
while(i < n && j < m)
{
if(s[i] == t[j])
j++;
i++;
}
return m - j;

}
};

C 题

2487. 从链表中移除节点

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

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

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

提示:

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

示例 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: 平衡树

对于一个节点,它是否应该保留取决于后面有无大于它的数。假设当前节点的值为 x,要判断后面是否有大于 x 的节点,只要看后面所有元素的最大值是否大于 x 即可。

首先将所有数据建立一颗平衡树,其中节点值可以重复。从左到右遍历链表,每遍历到一个节点,其值为 x,查询当前平衡树的最大值是否大于 x,根据查询结果来决定是否删除当前节点。然后将当前节点值从平衡树中删掉,然后在遍历链表下一个节点。

代码(C++)

这是比赛时的代码,当时用的是平衡树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
setting = multiset<int>();
build_tree(head);
int cur_max = *(setting.rbegin());
while(head && head -> val < cur_max)
{
auto it = setting.find(head -> val);
setting.erase(it);
head = head -> next;
}
auto it = setting.find(cur_max);
setting.erase(it);
if(!setting.empty())
cur_max = *setting.rbegin();
ListNode *iter = head -> next;
ListNode *prev = head;
while(iter)
{
int cur = iter -> val;
if(cur < cur_max)
prev -> next = iter -> next;
else
prev = iter;
auto it = setting.find(cur);
setting.erase(it);
if(!setting.empty())
cur_max = *setting.rbegin();
iter = iter -> next;
}
return head;
}

multiset<int> setting;

void build_tree(ListNode* node)
{
while(node)
{
setting.insert(node -> val);
node = node -> next;
}
}
};

算法2: 逆向思维

平衡树的做法是比赛时候写的,事后发现不是最优的,因为遍历过程中要频繁查询和删除平衡树中的节点。

如果遍历方向从右向左的话,要维护链表节点右侧的最大值就不需要平衡树操作了,只需要记录一个变量就可以了。

我们首先将链表转为数组。然后从后往前遍历数组,过程中维护最大值,遇到不小于当前最大值的加入最终链表元素中,生成最终的链表。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
vector<int> nums;
ListNode *iter = head;
while(iter)
{
nums.push_back(iter -> val);
iter = iter -> next;
}
int n = nums.size();
ListNode *result = new ListNode(nums[n - 1]);
int cur_max = nums[n - 1];
for(int i = n - 2; i >= 0; --i)
{
if(nums[i] >= cur_max)
{
ListNode *tmp = result;
result = new ListNode(nums[i]);
result -> next = tmp;
cur_max = nums[i];
}
}
return result;
}
};

D 题

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

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

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

注意:

1
2
3
数组的中位数是按 递增 顺序排列后位于 中间 的那个元素,如果数组长度为偶数,则中位数是位于中间靠 左 的那个元素。
例如,[2,3,1,4] 的中位数是 2 ,[8,4,3,5,1] 的中位数是 4 。
子数组是数组中的一个连续部分。

提示:

1
2
3
4
n == nums.length
1 <= n <= 1e5
1 <= nums[i], k <= n
nums 中的整数互不相同

示例 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 的子数组。

算法: 问题转换、频数前缀和+哈希表

本题在比赛中没有做出来,事后研究了别人的题解之后,发现这是一个非常好的题。

问题需要一些转换,解决经过转换后的问题,用的算法还是非常基础的。但是难在问题转换这一步,这种问题转换的思想还是非常值得学习的。

记 k 在 nums 中的下标是 p, nums[p] = k,由于子区间需要包含 k,所有可能得子区间 [i, j] 需要满足 0 <= i <= p, p <= j <= n-1

由于我们的条件是区间的中位数是 k,也就是区间中大于 k 的个数 n1 与小于 k 的个数 n2 需要满足条件 n1 - n2 = 0n1 - n2 = 1

sums[i] 表示 nums[0..i-1] 中大于 k 的元素个数减去小于 k 的元素个数的差值。

这样 s = sums[p+1] - sums[i] 表示区间 [i, p] 中大于 k 的元素个数减去小于 k 的元素个数的差值。

t = sums[j + 1] - sums[p] 表示区间 [p, j] 中大于 k 的元素个数减去小于 k 的元素个数的差值。

根据前面的条件,s 与 t 应该满足 s + t = 0s + t = 1

如果我们预处理出 [p..n-1] 上所有 sums[j+1]-sums[p] 的值及其出现的次数,记录在哈希表 mapping 中,mapping[x] 表示 x 的出现次数。

那么我们只需要枚举 0 <= i <= p-1,然后通过前缀和求出 s,然后查询 mapping[-s]mapping[1-s] 更新到答案中,即可。

这种用哈希表维护前缀和,记录各个前缀和的值的出现次数的思路,还是有不少类似题目的,例如 lc560、lc1248 等。

另外通过问题转换的方式,将原问题变成频数前缀和可以解决的问题,这种思路也有类似题目可以参考,例如 lc1862、lc1177、lc1930 等。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
int countSubarrays(vector<int>& nums, int k) {
int n = nums.size();
int p = -1;
for(int i = 0; i < n; ++i)
{
if(nums[i] == k)
{
p = i;
break;
}
}
vector<int> sums(n + 1);
for(int i = 1; i <= n; ++i)
{
if(nums[i - 1] > k)
sums[i] = sums[i - 1] + 1;
else if(nums[i - 1] < k)
sums[i] = sums[i - 1] - 1;
else
sums[i] = sums[i - 1];
}
unordered_map<int, int> mapping;
for(int j = p; j < n; ++j)
{
mapping[sums[j+1] - sums[p]]++;
}
int ans = 0;
for(int i = 0; i <= p; ++i)
{
int s = sums[p + 1] - sums[i];
if(mapping.count(-s) > 0)
ans += mapping[-s];
if(mapping.count(1 - s) > 0)
ans += mapping[1 - s];
}
return ans;
}
};

Share