LeetCode·1413.逐步求和得到正数的最小值·贪心
LeetCode 贪心 得到 求和 最小值 逐步 正数
2023-09-27 14:26:29 时间
链接:https://leetcode.cn/problems/minimum-value-to-get-positive-step-by-step-sum/solution/mn-by-xun-ge-v-9539/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目![](https://img-blog.csdnimg.cn/d14b4d2b4a114fcf988e5be6c32b14b3.png)
示例![](https://img-blog.csdnimg.cn/9a04f8d15dce4dcfb87a81bb7bbadf10.png)
思路
解题思路
贪心思路
根据题意直接模拟,定义初始正数startValue为 0 ,遍历数组求前缀和,当数组前缀和小于 1 时,补适当正数值,使得正好等于 1 ,继续遍历始终保持前缀和大于等于 1 ,那么补的正数值哪里来呢,就从 startValue ,补多少正数值 startValue 就扩多大
代码
int minStartValue(int* nums, int numsSize){
int min = 0;
int sum = 0;
for(int i = 0; i < numsSize; i++)
{
sum += nums[i];//前缀和
if(sum < 1)//小于1
{
min += 1 - sum;//补值
sum = 1;//始终满足题意,并且维持最小
}
}
return min == 0 ? 1 : min;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/minimum-value-to-get-positive-step-by-step-sum/solution/mn-by-xun-ge-v-9539/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- 贪心c++(结合LeetCode例题)
- LeetCode——Best Time to Buy and Sell Stock II
- LeetCode_贪心_二分搜索_中等_1802.有界数组中指定下标处的最大值
- LeetCode_贪心算法_中等_1785.构成特定和需要添加的最少元素
- LeetCode_双指针_简单_1332.删除回文子序列
- LeetCode_贪心算法_中等_846.一手顺子
- LeetCode_DFS_中等_386.字典序排数
- LeetCode_模拟_中等_498.对角线遍历
- LeetCode_二叉搜索树_简单_108.将有序数组转换为二叉搜索树
- LeetCode_动态规划_中等_152.乘积最大子数组
- LeetCode_并查集_中等_990.等式方程的可满足性
- LeetCode_二叉搜索树_简单_700.二叉搜索树中的搜索
- LeetCode·每日一题·1147. 段式回文·贪心
- LeetCode·每日一题·1812.判断国际象棋棋盘中一个格子的颜色·数学
- LeetCode·每日一题·769.最多能完成排序的块·贪心
- LeetCode·56.合并区间·贪心
- LeetCode·860.柠檬水找零·贪心
- LeetCode·455.分发饼干·贪心
- Leetcode 排序+优先队列+贪心
- LeetCode-575. 分糖果(Golang实现)
- [LeetCode] 548. Split Array with Equal Sum 分割数组成和相同的子数组
- [LeetCode] 341. Flatten Nested List Iterator 压平嵌套链表迭代器
- [LeetCode] 14. Longest Common Prefix 最长共同前缀