个人网站备案下载站,网站怎样免费推广,企业建站流程,网络游戏下载平台顾得泉#xff1a;个人主页
个人专栏#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂#xff0c;年薪百万#xff01; 一、将X减到0的最小操作数
题目链接#xff1a;将 x 减到 0 的最小操作数
题目描述 给你一个整数数组 nums 和一个整数 x 。每一…
顾得泉个人主页
个人专栏《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂年薪百万 一、将X减到0的最小操作数
题目链接将 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 1051 nums[i] 1041 x 109
解法
算法思路: 题目要求的是数组「左端右端」两段连续的、和为×的最短数组信息量稍微多一些不易理清思路;我们可以转化成求数组内一段连续的、和为sum(nums) - x的最长数组。此时就是熟悉的滑动窗口问题了。
算法流程: a.转化问题:求target sum(nums) - ×。如果target 0问题无解; b.初始化左右指针l 0,r 0(滑动窗口区间表示为[lr)左右区间是否开闭很重要必须设定与代码一致)记录当前滑动窗口内数组和的变量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(vectorint 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 1050 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(vectorint f) {unordered_mapint, 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 * 104s 和 p 仅包含小写字母
解法
算法思路: 因为字符串p的异位词的长度一定与字符串p的长度相同所以我们可以在字符串s中构造一个长度为与字符串p的长度相同的滑动窗口并在滑动中维护窗口中每种字母的数量;当窗口中每种字母的数量与字符串p中每种字母的数量相同时则说明当前窗口为字符串p的异位词; 因此可以用两个大小为26的数组来模拟哈希表一个来保存s 中的子串每个字符出现的个数另一个来保存p中每一个字符出现的个数。这样就能判断两个串是否是异位词。
代码实现
class Solution
{
public:vectorint findAnagrams(string s, string p) {vectorint 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;}
}; 结语今日的刷题分享到这里就结束了希望本篇文章的分享会对大家的学习带来些许帮助如果大家有什么问题欢迎大家在评论区留言~~~
