顾得泉:个人主页
个人专栏:《Linux操作系统》??《C/C++》??《LeedCode刷题》
键盘敲烂,年薪百万!
题目链接:将 x 减到 0 的最小操作数
???????给你一个整数数组?nums
?和一个整数?x
?。每一次操作时,你应当移除数组?nums
?最左边或最右边的元素,然后从?x
?中减去该元素的值。请注意,需要?修改?数组以供接下来的操作使用。
???????如果可以将?x
?恰好?减到?0
?,返回?最小操作数?;否则,返回?-1
?。
示例 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
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109
算法思路:
???????题目要求的是数组「左端+右端」两段连续的、和为×的最短数组,信息量稍微多一些,不易理清思路;我们可以转化成求数组内一段连续的、和为sum(nums) - x的最长数组。此时,就是熟悉的滑动窗口问题了。
算法流程:
?????a.转化问题:求target = sum(nums) - ×。如果target < 0,问题无解;
?????b.初始化左右指针l = 0,r = 0(滑动窗口区间表示为[l,r),左右区间是否开闭很重要,必须设定与代码一致),记录当前滑动窗口内数组和的变量sum = 0,记录当前满足条件数组的最大区间长度maxLen = -1;
?????c. 当r小于等于数组长度时,一直循环:
? ? ? ? ?i.如果sum < target,右移右指针,直至变量和大于等于target,或右指针已经移到头;
? ? ? ? ?ii.如果sum > target,右移左指针,直至变量和小于等于target,或左指针已经移到头;
? ? ? ? ?ii.如果经过前两步的左右移动使得sum == target,维护满足条件数组的最大长度,并让下个元素进入窗口;
??????d.循环结束后,如果maxLen的值有意义,则计算结果返回;否则,返回-1。
class Solution
{
public:
int minOperations(vector<int>& nums, int x)
{
int sum = 0;
for(int a : nums) sum += a;
int target = sum - x;
if(target < 0)
return -1;
int ret = -1;
for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
{
tmp += nums[right];
while(tmp > target)
tmp -= nums[left++];
if(tmp == target)
ret = max(ret, right - left + 1);
}
if(ret == -1)
return ret;
else return
nums.size() - ret;
}
};
题目链接:水果成篮
???????你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组?fruits
?表示,其中?fruits[i]
?是第?i
?棵树上的水果?种类?。
???????你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
给你一个整数数组?fruits
?,返回你可以收集的水果的?最大?数目。
示例 1:
输入:fruits = [1,2,1] 输出:3 解释:可以采摘全部 3 棵树。
示例 2:
输入:fruits = [0,1,2,2] 输出:3 解释:可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。
示例 3:
输入:fruits = [1,2,3,2,2] 输出:4 解释:可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。
示例 4:
输入:fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出:5 解释:可以采摘 [1,2,1,1,2] 这五棵树。
提示:
1 <= fruits.length <= 105
0 <= fruits[i] < fruits.length
算法思路:
???????研究的对象是一段连续的区间,可以使用「滑动窗口」思想来解决问题。让滑动窗口满足:窗口内水果的种类只有两种。
做法∶
???????右端水果进入窗口的时候,用哈希表统计这个水果的频次。这个水果进来后,判断哈希表的大小;如果大小超过2:说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口,直到哈希表的大小小于等于2,然后更新结果;如果没有超过2,说明当前窗口内水果的种类不超过两种,直接更新结果ret。
算法流程:
?????a.初始化哈希表hash来统计窗口内水果的种类和数量;
?????b.初始化变量:左右指针left =0, right =0,记录结果的变量ret= 0;c. 当right小于数组大小的时候,一直执行下列循环:
? ? ? ? ?i.将当前水果放入哈希表中;
? ? ? ? ?ii.判断当前水果进来后,哈希表的大小:
???????如果超过2;将左侧元素滑出窗口,并且在哈希表中将该元素的频次减一;
???????如果这个元素的频次减一之后变成了0,就把该元素从哈希表中删除;。重复上述两个过程,直到哈希表中的大小不超过2;
? ? ? ? ?iii.更新结果ret;
? ? ? ? ?iv. right++,让下一个元素进入窗口;d.循环结束后,ret存的就是最终结果。
class Solution
{
public:
int totalFruit(vector<int>& f)
{
unordered_map<int, int> hash;
int ret = 0;
for(int left = 0, right = 0; right < f.size(); right++)
{
hash[f[right]]++; // 进窗?
while(hash.size() > 2)
{
hash[f[left]]--;
if(hash[f[left]] == 0)
hash.erase(f[left]);
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
题目链接:找到字符串中所有字母异位词
???????给定两个字符串?s
?和?p
,找到?s
?中所有?p
?的?异位词?的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
???????异位词?指由相同字母重排列形成的字符串(包括相同的字符串)
示例?1:
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
?示例 2:
输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s
?和?p
?仅包含小写字母算法思路:
???????因为字符串p的异位词的长度一定与字符串p的长度相同,所以我们可以在字符串s中构造一个长度为与字符串p的长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量;当窗口中每种字母的数量与字符串p中每种字母的数量相同时,则说明当前窗口为字符串p的异位词;
???????因此可以用两个大小为26的数组来模拟哈希表,一个来保存s 中的子串每个字符出现的个数,另一个来保存p中每一个字符出现的个数。这样就能判断两个串是否是异位词。
class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ret;
int hash1[26] = { 0 };
for(auto ch : p) hash1[ch - 'a']++;
int hash2[26] = { 0 };
int m = p.size();
for(int left = 0, right = 0, count = 0; right < s.size(); right++)
{
char in = s[right];
if(++hash2[in - 'a'] <= hash1[in - 'a'])
count++;
if(right - left + 1 > m)
{
char out = s[left++];
if(hash2[out - 'a']-- <= hash1[out - 'a'])
count--;
}
if(count == m)
ret.push_back(left);
}
return ret;
}
};
结语:今日的刷题分享到这里就结束了,希望本篇文章的分享会对大家的学习带来些许帮助,如果大家有什么问题,欢迎大家在评论区留言~~~?