什么网站下载素材做图的,ui一般用什么软件做,做视频网站要什么软件有哪些,企业网站建设需要多少钱将X减到0的最小操作数
1658. 将 x 减到 0 的最小操作数 - 力扣#xff08;LeetCode#xff09; 文章目录 将X减到0的最小操作数题目描述算法原理代码编写Java代码编写C代码编写 题目描述
给你一个整数数组 nums 和一个整数 x 。每一次操作时#xff0c;你应当移除数组 num…将X减到0的最小操作数
1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode 文章目录 将X减到0的最小操作数题目描述算法原理代码编写Java代码编写C代码编写 题目描述
给你一个整数数组 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 10^51 nums[i] 10^41 x 10^9 算法原理
这道题直接上手写代码还是有一定难度的于是正难则反我们可以使用以下的策略 转化找出最长的子数组的长度所有元素的和刚好等于 sum - x 转化问题求target sum - x,如果target 0,问题无解 sum一开始就遍历数组然后存入数组元素的总和 初始化左右指针left、right定义一个tmp存入right走过数组的和 在right 数组长度的时候一直循环 tmp target right tmp target left ,然后tmp的值也就与之需要--如果满足tmp target那就更新结果 注意最后结果的返回是需要数组长度 - ret 这里有一个细节问题 题目中已经有规定了 提示 1 nums.length 10^51 nums[i] 10^41 x 10^9 数组中的元素应该是 1,如果没有的话数组元素中出现了负数那么这道题的规律也就不复存在此时我们可能需要别的算法来解决。 代码编写
Java代码编写
class Solution {public int minOperations(int[] nums, int x) {int sum 0;// 存入nums所有的和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.length; right ){// tmp 也就是 right 指针遍历的和tmp nums[right]; // 进窗口while(tmp target) // 判断tmp - nums[left]; // 出窗口if(tmp target)ret Math.max(ret, right - left 1);}if(ret -1) return ret;else return nums.length - ret;}
}C代码编写
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;}
};
