算法leetcode

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

字数统计: 2.9k字   |   阅读时长: 12分
,

摘要: 本文是 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 = 0 或 n1 - 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 = 0 或 s + 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