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

  |  

摘要:

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


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

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

题目1

1658. 将 x 减到 0 的最小操作数

给你一个整数数组 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

2516. 每种字符至少取 K 个

给你一个由字符 ‘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