丽水微信网站建设报价,惠州seo整站优化,烟台网站建设平台,快速建立平台网站开发建站教程详解将x减到0的最小操作数
题目链接#xff1a;https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/ 题目解读
题目要求移除元素总和等于参数x#xff0c;这道题给我的第一感觉就是从数组的两边入手#xff0c;对数据进行加和删除#xff0c;但是这里有一…将x减到0的最小操作数
题目链接https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/ 题目解读
题目要求移除元素总和等于参数x这道题给我的第一感觉就是从数组的两边入手对数据进行加和删除但是这里有一个问题如果从数组左右两边进行操作那么就会两个变量这样导致可能出现的结果是很多的。所以这道题正确解法仍然是滑动窗口。
错误示例
我在第一次解决这道题目的时候单纯认为只要删除数组左右两边中比x小而比另一个数大的元素即可如果左右两边的数中较大的一个数大于x那么就直接删除较小的一个数。代码如下
class Solution {
public:int minOperations(vectorint nums, int x) {int left 0, right nums.size() - 1;int retnum 0;while(left right){int mini nums[left] nums[right] ? right : left;int maxi nums[left] nums[right] ? left : right;if(nums[mini] x){retnum -1;break;}if(nums[maxi] x){x - nums[maxi]; retnum;if(left maxi)left;else--right;}else if(nums[maxi] x){x - nums[mini]; retnum;if(left mini)left;else--right;}if(x 0) break;}return retnum;}
};
但是这么做是有问题毕竟这是一道中等难度的题目那问题出在哪里呢 如果只是片面按照上面的说法进行删除比如删除左右两边较大值后下一个数继续删除变为负数那么函数返回-1认为没有找到符合条件的组合可是正确的组合应该是删除那个较小的元素再向后删除正好可以是x减为0所以从思想上这个算法就是错误的。 正确解法
这道题从正面来解决着实难度很大当左右两边的元素都可以删除的时候并不能确定到底要删除哪边但是反过来想这道题就可以想到一个简单的解决思路这也是遇到很多滑动窗口的难题时可以解决的一个办法。具体思路如下 要是删除元素的总和等于x不就等于让剩下的连续数组的总和为sum整个元素的总和- x。所以可以设置两个指针left和right分别指向滑动窗口的起始和结束位置然后计算数组的长度题目要求返回最小操作数那么要求的就是滑动窗口的最大长度。代码如下 class Solution {
public:int minOperations(vectorint nums, int x) {int left 0, right 0;int target 0;for(auto e : nums){target e;}target - x;int sum 0;int retnum -1;while(right nums.size()){sum nums[right];while(sum target left right){sum - nums[left];}if(sum target){int comp right - left 1;retnum comp retnum ? comp : retnum;}right;}if(retnum -1) return retnum;elsereturn nums.size() - retnum;}
};
这里要注意一个特殊情况我犯的错误 如果你直接看了解题思路去写代码有可能会写成这样的代码在提交的时候会有一个测试用例过不去那么看似正确的逻辑到底是哪里出了问题 测试用例是这样的仔细观察就会发现x的值等于数组中所有元素的集合那为什么会导致执行错误呢
返回代码中while循环是让sumtarget的时候就可以进入循环然后先进行判断判断后减去left指向的值的大小然后再让left指针后移程序第一次进入while循环后sum不为0减去left指向元素的大小后为0可是right指针未刷新left大于了right所以会退出while循环导致永远不会刷新retnum的值最终返回-1
反思一下为什么会犯错我认为主要还是没有想到这个特殊情况其次就是对指针的移动先后顺序没有一个好的把握比如这种对属于移动后进行判断我认为不要揉在一起移动结束后进行判断更稳妥一些。
