本文主要是介绍【C++二分查找 前缀和】1658. 将 x 减到 0 的最小操作数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
本文涉及的基础知识点
C++二分查找
C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
LeetCode1658. 将 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
二分查找
n = nums.length
枚举右边删除了i1( ∈ \in ∈[0,n])个元素,令其和为x1,则在前缀和中查找是否存在preSum[i2]=x-x1,由于nums的元素都是正数,所以最多一个解。
同时左边和右边删除的部分,不能有重复元素,即:i1+i2<=n。
代码
核心代码
class Solution {public:int minOperations(vector<int>& nums, int x) {const int N = nums.size();vector<int> preSum(1);for (const auto& n : nums) {preSum.emplace_back(n + preSum.back());}int ret = N + 1;for (int i = 0; i <= N; i++) {const int x1 = preSum.back() - preSum[N - i];auto it = std::equal_range(preSum.begin(), preSum.end(), x - x1);if (it.first == it.second) { continue; }ret = min(ret, (int)(it.first- preSum.begin() + i));}return ret > N ? -1 : ret;}};
单元测试
vector<int> nums;int x;TEST_METHOD(TestMethod11){nums = { 1, 1, 4, 2, 3 }, x = 5;auto res = Solution().minOperations(nums, x);AssertEx(2, res);}TEST_METHOD(TestMethod12){nums = { 5,6,7,8,9 }, x = 4;auto res = Solution().minOperations(nums, x);AssertEx(-1, res);}TEST_METHOD(TestMethod13){nums = { 3,2,20,1,1,3 }, x = 10;auto res = Solution().minOperations(nums, x);AssertEx(5, res);}
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
这篇关于【C++二分查找 前缀和】1658. 将 x 减到 0 的最小操作数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!