算法leetcode

leetcode第242场周赛：前缀和优化 DP 专场

字数统计: 3.7k字   |   阅读时长: 16分
, ,

摘要: 本文是 leetcode 第 242 周赛的记录。主要涉及的算法包括双指针、值域二分、队列、动态规划、前缀和、博弈。

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

总览

这是 leetcode 第 242 场周赛，本场比赛的赞助公司是恒生，前 500 名可获得简历内推机会，前 600 名可获得恒生黑盒赛邀请：

本场比赛发挥不佳，C 和 D 都没做出来，最终成绩 1006/4306，不过 C 和 D 都涉及到动态规划的优化，确实比较难，通过的人不多，成绩如下：

本场比赛的亮点就是 C、D 题都是动态规划的优化，并且优化方法都与前缀和有关。其中 C 还有使用队列的方法。D 有博弈的背景，并且状态转移需要的信息需要预处理，之后依然需要优化。

各题的算法点以及参考文章如下：

A 题

给你一个二进制字符串 s 。如果字符串中由 1 组成的 最长 连续子字符串 严格长于 由 0 组成的 最长 连续子字符串，返回 true ；否则，返回 false 。

例如，s = “110100010” 中，由 1 组成的最长连续子字符串的长度是 2 ，由 0 组成的最长连续子字符串的长度是 3 。
注意，如果字符串中不存在 0 ，此时认为由 0 组成的最长连续子字符串的长度是 0 。字符串中不存在 1 的情况也适用此规则。

1
2
3
提示：
1 <= s.length <= 100
s[i] 不是 '0' 就是 '1'

示例 1：
输入：s = “1101”
输出：true
解释：
由 1 组成的最长连续子字符串的长度是 2：”1101”
由 0 组成的最长连续子字符串的长度是 1：”1101”
由 1 组成的子字符串更长，故返回 true 。

示例 2：
输入：s = “111000”
输出：false
解释：
由 1 组成的最长连续子字符串的长度是 3：”111000”
由 0 组成的最长连续子字符串的长度是 3：”111000”
由 1 组成的子字符串不比由 0 组成的子字符串长，故返回 false 。

示例 3：
输入：s = “110100010”
输出：false
解释：
由 1 组成的最长连续子字符串的长度是 2：”110100010”
由 0 组成的最长连续子字符串的长度是 3：”110100010”
由 1 组成的子字符串不比由 0 组成的子字符串长，故返回 false 。

算法: 单串单向双指针

对于一个字符串 s，求最长的连续字符 ch 的长度。这个需求可以通过单串单向双指针的算法求得。

关于单串单向双指针算法，可以参考 尺取法(单串单向双指针) 这篇文章。

对 ch=’0’ 和 ch=’1’ 个跑一遍，比较大小即可。

代码(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
class Solution {
public:
    bool checkZeroOnes(string s) {
        int l1 = sub(s, '1');
        int l0 = sub(s, '0');
        return l1 > l0;
    }

private:
    int sub(const string& s, char ch)
    {
        int n = s.size();
        int l = 0;
        while(l < n && s[l] != ch)
            ++l;
        int ans = 0;
        while(l < n)
        {
            int r = l;
            while(r < n && s[r] == ch)
                ++r;
            ans = max(ans, r - l);
            l = r;
            while(l < n && s[l] != ch)
                ++l;
        }
        return ans;
    }
};

B 题

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。
返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 1e7 ，且 hour 的 小数点后最多存在两位数字 。

1
2
3
4
5
6
提示：
n == dist.length
1 <= n <= 1e5
1 <= dist[i] <= 1e5
1 <= hour <= 1e9
hours 中，小数点后最多存在两位数字

示例 1：
输入：dist = [1,3,2], hour = 6
输出：1
解释：速度为 1 时：

  • 第 1 趟列车运行需要 1/1 = 1 小时。
  • 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
  • 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
  • 你将会恰好在第 6 小时到达。

示例 2：
输入：dist = [1,3,2], hour = 2.7
输出：3
解释：速度为 3 时：

  • 第 1 趟列车运行需要 1/3 = 0.33333 小时。
  • 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
  • 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
  • 你将会在第 2.66667 小时到达。

示例 3：
输入：dist = [1,3,2], hour = 1.9
输出：-1
解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。

算法: 值域二分

首先判断能否准时到达。由于所有 dist[i] 满足 1 <= dist[i] <= 1e5，因此每个 dist[i] 都可以在 1hour 时间完成，同时由于换乘车只能整点发车，因此 dist[0..n-2] 都至少需要 1 hour 完成。dist[n - 1] 是可以在 1hour 以内完成的，跟速度有关。

我们定义一个函数 check(dist, hour, v) ，以正整数速度 v 模拟换乘的流程，返回否准时到达。然后将题目保证的 v 的最大值 1e7 代入即可。

当车辆可以准时到达时，问题就是可以准时到达的最小正整数速度是多少。如果给定某个正整数速度 v，它可以准时到达，那么大于这个速度当然也可以准时到达，答案就在 [1, v] 中，如果它不可以准时到达，那么小于这个速度当然也不可以准时到达，答案就在 [v + 1, 1e7] 中

代码(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
class Solution {
public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int r = 1e7 + 1;
        int l = 1;
        if(!check(dist, hour, r))
            return -1;
        while(l < r)
        {
            double mid = (l + r) / 2;
            if(check(dist, hour, mid))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }

private:
    const double EPS = 1e-9;

    bool check(const vector<int>& dist, const double hour, int v)
    {
        int n = dist.size();
        double total = 0;
        for(int i = 0; i < n - 1; ++i)
            total += ceil(dist[i] / (double)v);
        total += dist[n - 1] / (double)v;
        return total < hour + EPS;
    }
};

C 题

给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为 ‘0’ 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：

i + minJump <= j <= min(i + maxJump, s.length - 1) 且
s[j] == ‘0’.
如果你可以到达 s 的下标 s.length - 1 处，请你返回 true ，否则返回 false 。

示例 1：
输入：s = “011010”, minJump = 2, maxJump = 3
输出：true
解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。

示例 2：
输入：s = “01101110”, minJump = 2, maxJump = 3
输出：false

1
2
3
4
5
6
提示：

2 <= s.length <= 1e5
s[i] 要么是 '0' ，要么是 '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length

算法1: 基础单串DP

1
2
3
4
5
6
7
8
9
10
11
12
13
状态定义
dp[i] := 从 0 能否到达 i, 1 为能到达，0 为不能到达

初始化
若 dp[0] == 1 

答案:
dp[n - 1]

状态转移
dp[i] = 1 dp[j] 中存在 1
      = 0 dp[j] 中不存在 1 或 i - minJump < 0
其中 j 属于 [min(i - maxJump, 0), i - minJump]

代码(C++)

注: $O(N^2)$ 超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        vector<int>dp(n, 0);
        dp[0] = 1;
        for(int i = 1; i < n; ++i)
        {
            if(s[i] == '1' || i - minJump < 0)
                continue;
            for(int j = max(0, i - maxJump); j <= i - minJump; ++j)
                if(dp[j] == 1)
                {
                    dp[i] = 1;
                    break;
                }
        }
        return dp[n - 1];
    }
};

算法2: 前缀和优化 DP

在状态转移时，要问 [max(i - maxJump, 0), i - minJump] 这个区间内中有无 dp[j] 的值为 1。

如果用遍历的方式，需要 O(N) 转移。可以用前缀和的方式，将查询改为问 dp[max(i - maxJump, 0) .. i - minJump] 中是否有 1，也就是 sum(dp[max(i - maxJump, 0) .. i - minJump]) 是否大于 0。

如果状态转移时维护一个 dp 数组的前缀和 sums，那么这步查询就可以 O(1) 完成，也就是 sums[i - minJump + 1] - sums[max(i - maxJump, 0)]。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        vector<int> dp(n);
        dp[0] = 1;
        vector<int> sums(n + 1);
        sums[1] = 1;
        for(int i = 1; i < n; ++i)
        {
            if(s[i] == '0' && (i - minJump >= 0))
                if(sums[i - minJump + 1] - sums[max(i - maxJump, 0)] > 0)
                    dp[i] = 1;
            sums[i + 1] = sums[i] + dp[i];
        }
        return dp[n - 1];
    }
};

算法3: 队列

从 0 开始向右走，走的过程中始终维护一个队列，保存从当前点走一步可以到达的 s[j] == 0 的点。且队列中的点始终保持从小到大的顺序，具体操作如下:

  • 另外再维护一个 r，表示当前访问过的最右边的点。如果当前点为 i，则更新完 i 可以到达的 s[j] == 0 的点后，将 r 更新为 i + maxJump

  • 从队头取出当前的 i 后，在 [(r + 1, i + minJump), min(i + maxJump, n - 1)] 范围内判断 s[j] 是否为零，若为零则将 j 压入队尾。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        queue<int> q;
        q.push(0);
        int r = 0;
        while(!q.empty())
        {
            int i = q.front();
            if(i == n - 1)
                return true;
            q.pop();
            for(int j = max(r + 1, i + minJump); j <= min(n - 1, i + maxJump); ++j)
            {
                if(s[j] == '0')
                    q.push(j);
                r = i + maxJump;
            }
        }
        return false;
    }
};

D 题

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手 。

总共有 n 个石子排成一行。轮到某个玩家的回合时，如果石子的数目 大于 1 ，他将执行以下操作：

选择一个整数 x > 1 ，并且 移除 最左边的 x 个石子。
将 移除 的石子价值之 和 累加到该玩家的分数中。
将一个 新的石子 放在最左边，且新石子的值为被移除石子值之和。
当只剩下 一个 石子时，游戏结束。

Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差，Bob 的目标是 最小化 分数差。

给你一个长度为 n 的整数数组 stones ，其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用 最优 策略的情况下，Alice 和 Bob 的 分数之差 。

1
2
3
4
5
提示：

n == stones.length
2 <= n <= 1e5
-1e4 <= stones[i] <= 1e4

示例 1：
输入：stones = [-1,2,-3,4,-5]
输出：5
解释：

  • Alice 移除最左边的 4 个石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。
  • Bob 移除最左边的 2 个石子，得分增加 2 + (-5) = -3 ，并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。
    两者分数之差为 2 - (-3) = 5 。

示例 2：
输入：stones = [7,-6,5,10,5,-2,-6]
输出：13
解释：

  • Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，并且将一个价值为 13 的石子放在最左边。stones = [13] 。
    两者分数之差为 13 - 0 = 13 。

示例 3：
输入：stones = [-10,-12]
输出：-22
解释：

  • Alice 只有一种操作，就是移除所有石子。得分增加 (-10) + (-12) = -22 ，并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。
    两者分数之差为 (-22) - 0 = -22 。

算法: 前缀和+博弈DP

对每个回合取左边的 x 个棋子，得到前 x 个棋子面值和 s 的价值，然后再放回一个棋子，价值为面值和 s。

以上过程可以用模拟的方式直接在 stones 上维护，并且在 stones 上做单串 DP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
状态定义
dp[i] := stones[i..n-1] 上, 先取的人的价值差的最大值
         其中 stones[i] 为上一轮新加入的石子，stongs[i+1..n-1]为原有石子

初始化
dp[n - 1] = 0
dp[n - 2] = sum(stones[0..n-2], stones[n-1])
dp[0..n-2] = INT_MIN / 2

答案
dp[0]

状态转移
dp[i] = max(sum(stones[0..i], stones[i+1..j]) - dp[j])
      = max(sum(stones[0..j]) - dp[j])
      其中 i + 1 <= j <= n - 1
      这里 stones[0..i] 为新加入的石子，stones[i+1..j] 为原有石子

在状态转移过程中，需要求 sum(stones[0..i])，可以预处理出 stones 的前缀和 sums，那么状态转移可以变成以下形式：

1
2
dp[i] = max(sums[j + 1] - dp[j])
i+1 <= j <= n-1

代码(C++)

注 O(N^2) 超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n = stones.size();
        vector<int> sums(n + 1);
        for(int i = 1; i <= n; ++i)
            sums[i] = sums[i - 1] + stones[i - 1];
        vector<int> dp(n, INT_MIN / 2);
        dp[n - 1] = 0;
        for(int i = n - 2; i >= 0; --i)
        {
            for(int j = i + 1; j < n; ++j)
                dp[i] = max(dp[i], sums[j + 1] - dp[j]);
        }
        return dp[0];
    }
};

优化

在推导 i 的过程中，维护一个 mx，表示 sums[j+1] - dp[j] 的最大值，i+1 <= j <= n-1，状态转移可以直接写为：

1
2
dp[i] = mx
mx = max(mx, sums[i + 1] - dp[i])

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n = stones.size();
        vector<int> sums(n + 1);
        for(int i = 1; i <= n; ++i)
            sums[i] = sums[i - 1] + stones[i - 1];
        vector<int> dp(n, INT_MIN / 2);
        dp[n - 1] = 0;
        int mx = sums[n] - dp[n - 1];
        for(int i = n - 2; i >= 0; --i)
        {
            dp[i] = mx;
            mx = max(mx, sums[i + 1] - dp[i]);
        }
        return dp[0];
    }
};
Share