凡科网做网站,黄山网络推广哪家好,阜城网站建设代理,wordpress实现用户中心本节博客主要是讲的我解“将x减到0的最小操作数”这道题的思路历程#xff0c;从最开始的想法到代码提交的详细记录#xff0c;有需要借鉴即可。 目录 1.题目2.代码示例3.细节3.1left越界3.2特殊情况 4.总结 1.题目
题目链接#xff1a;LINK 看题目意思是就是给你一个数X从最开始的想法到代码提交的详细记录有需要借鉴即可。 目录 1.题目2.代码示例3.细节3.1left越界3.2特殊情况 4.总结 1.题目
题目链接LINK 看题目意思是就是给你一个数X让你拿着数组中的最左边或者最右边的数字与这个数字抵消(相减)直到X为0或者找不到如果可以抵消掉记录拿这个数组中最少的一个数字个数而且用数组中的值的时候必须用两头的。
这个暴力求解…都不知道下一次是用左边的数字还是右边的数字…基本暴力解法就想不到了。
这里我们老师讲的说要用到转换思想——“正难则反” 什么意思呢 其实对于这个题目来说整个数组可以分为三块即下图 说白了就让我们找left right这两块中最小的数字个数 那可以等效于让我们找 该数组总数字个数 - mind最大数字个数
顺着前面“滑动窗口”的代码思路 大体就可以写出下面代码
2.代码示例
class Solution {
public:int minOperations(vectorint nums, int x) {int ALsum 0;int n nums.size();for(size_t i 0;in;i){ALsumnums[i];}long long target ALsum - x;//中间的目标值满足目标值就进行更新结果int ret -1;//代表两边的长度取最小值int len 0;//代表left和right之间的长度取最大值long long sum 0;//代表中间区间的和//处理特殊情况if (sum target){return n;}for(int right 0,left 0; right n; right){//进窗口sumnums[right];//出窗口while(sum target left right){sum-nums[left];left;}//更新结果if(sum target){len max(len,right - left 1);}}return ret len 0 ? -1 : n - len;}
};这个题做完之后感觉还是有一两个坑的下面进行展示
3.细节
3.1left越界
这个问题呢也可以说是X 整个数组之和即target小于0导致了left会不断右移的情况
class Solution {
public:int minOperations(vectorint nums, int x) {int ALsum 0;int n nums.size();for(size_t i 0;in;i){ALsumnums[i];}int target ALsum - x;//中间的目标值满足目标值就进行更新结果int ret -1;//代表两边的长度取最小值int len 0;//代表left和right之间的长度取最大值int sum 0;//代表中间区间的和for(int right 0,left 0; right n; right){//进窗口sumnums[right];//出窗口while(sum target){sum-nums[left];left;}//更新结果if(sum target){len max(len,right - left 1);}}return ret len 0 ? -1 : n - len;}
};这个主要是越界问题是left越界了。
3.2特殊情况 class Solution {
public:int minOperations(vectorint nums, int x) {int ALsum 0;int n nums.size();for(size_t i 0;in;i){ALsumnums[i];}int target ALsum - x;//中间的目标值满足目标值就进行更新结果int ret -1;//代表两边的长度取最小值int len 0;//代表left和right之间的长度取最大值int sum 0;//代表中间区间的和for(int right 0,left 0; right n; right){//进窗口sumnums[right];//出窗口while(sum target left right){sum-nums[left];left;}//更新结果if(sum target){len max(len,right - left 1);}}return ret len 0 ? -1 : n - len;}
};这个是出了什么问题呢就是这是一种数组里的数字全部都与X相消才行特殊情况吧算是需要特别处理一下。 我写的这个代码刚好默认是mid组至少有一个数字的用我写的代码肯定是找不到的所以需要特殊判断一下。
4.总结
感觉这个题关键是刚上来的转换思想很关键(怪不得是中等题目)其次是想到滑动窗口这俩细节问题的话可以通过调试调出来。 EOF
