算法leetcode

力扣1658-将x减到0的最小操作数

字数统计: 1.3k字   |   阅读时长: 5分
,

摘要:

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

各位好，今天我们来看一个单串单向双指针的问题。本题的特点是随着窗口左端点 left 变大，合法的窗口右端点 right 也会变大，这样的话我们从小到大枚举 left，然后线性推进 right 到合法的最大位置，然后更新答案。

本题在最近的一次周赛中 leetcode第325场周赛 有一个基本一样的问题，后面我们也会提到，也就是题目2，可以对比着看。

题目1

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

提示：

1
2
3
1 <= nums.length <= 1e5
1 <= nums[i] <= 1e4
1 <= x <= 1e9

示例 1：
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：
输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

算法: 单串单向双指针

前缀和后缀的和加起来必须为 x，相当于滑动窗口的和加起来必须为 s - x，其中 s 为数组整体的和。

因此为了求合法的前缀和后缀长度和的最小值，可以先求合法的滑动窗口的最大长度，然后用数组总长度减去最大窗口长度就是我们要求的答案了。

我们记 t = s - x，对于每个窗口左端点 left，由于 nums 中都是正数，因此可以线性地推进 right，直至窗口的和大于等于 t。

对于一个 left，right 停止推进的时候，如果窗口的和恰好等于 t，则此时 left 可以贡献一个可能的答案，更新其最大值。

从小到大枚举完 left 即可得到合法窗口的最大长度。

代码 (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:
    int minOperations(vector<int>& nums, int x) {
        int s = accumulate(nums.begin(), nums.end(), 0);
        int t = s - x;
        int n = nums.size();
        int cur_sum = 0;
        // 对每个 left，找最大可能得 right
        int right = 0;
        int max_w = -1;
        for(int left = 0; left < n; ++left)
        {
            while(right < n && cur_sum < t)
                cur_sum += nums[right++];
            if(cur_sum == t)
                max_w = max(max_w, right - left);
            cur_sum -= nums[left];
        }
        if(max_w == -1)
            return -1;
        return n - max_w;
    }
};

题目2

给你一个由字符 ‘a’、’b’、’c’ 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。

提示：

1
2
3
1 <= s.length <= 1e5
s 仅由字母 'a'、'b'、'c' 组成
0 <= k <= s.length

示例 1：
输入：s = “aabaaaacaabc”, k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 ‘a’ 、一个字符 ‘b’ 。
从 s 的右侧取五个字符，现在共取到四个字符 ‘a’ 、两个字符 ‘b’ 和两个字符 ‘c’ 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。

示例 2：
输入：s = “a”, k = 1
输出：-1
解释：无法取到一个字符 ‘b’ 或者 ‘c’，所以返回 -1 。

算法: 单串单向双指针

与前面的问题一样，首先将前缀和后缀对 a, b, c 三个字符数量的限制，转换为滑动窗口中对 a, b, c 三个字符数量的限制。

合法窗口对 a, b, c 三个字符都有数量限制，因此对每一个 left，都有一个最大的 right 对应以 left 开头的最大的合法窗口，因此用每个 left 对应的最大合法窗口更新一次答案即可。

同时当 left 变大时，对应最大合法窗口的右端点 right 也是变大的，因此 right 可以随着 left 同步变大。

代码 (Python)

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
class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        cnts = [0, 0, 0]
        for ch in s:
            cnts[ord(ch) - ord('a')] += 1
        for cnt in cnts:
            if cnt < k:
                return -1

        def _check(_cnts, ch):
            """
            新增字符 ch 后，窗口是否合法
            """
            for i in range(3):
                if cnts[i] - _cnts[i] < k:
                    return False
                if ord(ch) - ord('a') == i and cnts[i] - _cnts[i] < k + 1:
                    return False
            return True

        max_length = -1
        n = len(s)
        cur_cnts = [0, 0, 0]
        right = 0
        for left in range(n):
            while(right < n and _check(cur_cnts, s[right])):
                cur_cnts[ord(s[right]) - ord('a')] += 1
                right += 1
            max_length = max(max_length, right - left)
            cur_cnts[ord(s[left]) - ord('a')] -= 1

        if max_length == -1:
            return -1
        return n - max_length
Share