哪家公司网站建设好,口碑营销网站,服务注册中心有哪些,太原网站制作策划文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
前缀和
二【题目难度】
简单
三【题目编号】
1413.逐步求和得到正数的最小值
四【题目描述】… 文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
前缀和
二【题目难度】
简单
三【题目编号】
1413.逐步求和得到正数的最小值
四【题目描述】
给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。你需要从左到右遍历 nums 数组并将 startValue 依次累加上 nums 数组中的值。请你在确保累加和始终大于等于 1 的前提下选出一个最小的 正数 作为 startValue 。
五【题目示例】 示例 1 输入nums [-3,2,-3,4,2]输出5解释如果你选择 startValue 4在第三次累加时和小于 1 。 累加求和 startValue 4 | startValue 5 | nums (4 -3 ) 1 | (5 -3 ) 2 | -3 (1 2 ) 3 | (2 2 ) 4 | 2 (3 -3 ) 0 | (4 -3 ) 1 | -3 (0 4 ) 4 | (1 4 ) 5 | 4 (4 2 ) 6 | (5 2 ) 7 | 2 示例 2 输入nums [1,2]输出1解释最小的 startValue 需要是正数。 示例 3 输入nums [1,-2,-3]输出5
六【题目提示】
1 nums.length 100-100 nums[i] 100
七【解题思路】
本题的核心思想是确保数组每一位的累加和都要大于等于1所以我们直接对数组求和在求和的过程中记录整个数组中每一位的最小累加和因为只有获取到最小值最后才能根据其计算出“抵消值”以确保数组每一位的累加和都要大于等于1其实是贪心算法的思想所以对于最后计算出的最小累加和有两种情况 小于1说明需要“抵消值”来确保数组每一位的累加和都要大于等于1故返回“-最小累加和1”大于等于1说明不需要“抵消值”来确保数组每一位的累加和都要大于等于1因为原本数组每一位的累加和都已经大于等于1了故根据题意直接返回1 最后返回结果即可具体细节可以参考下面的代码
八【时间频度】
时间复杂度 O ( n ) O(n) O(n) n n n为传入的数组的长度空间复杂度 O ( 1 ) O(1) O(1)
九【代码实现】
Java语言版
class Solution {public int minStartValue(int[] nums) {// 记录总和int sum 0;// 记录最小总和int min_sum 0;// 找出最小总和for (int i 0; i nums.length; i) {sum nums[i];min_sum Math.min(sum, min_sum);}// 如果最小总和小于1需要抵消负数使其总和大于等于1否则直接返回1return min_sum 1 ? -min_sum 1 : 1;}
}Python语言版
class Solution:def minStartValue(self, nums: List[int]) - int:# 记录总和total_sum 0# 记录最小总和min_sum 0# 找出最小总和for i in range(0, len(nums)):total_sum nums[i]min_sum min(total_sum, min_sum)# 如果最小总和小于1需要抵消负数使其总和大于等于1否则直接返回1if min_sum 1:return -min_sum 1else:return 1C语言版
int minStartValue(int* nums, int numsSize)
{// 记录总和int sum 0;// 记录最小总和int minSum 0;// 找出最小总和for (int i 0; i numsSize; i){sum nums[i];if (sum minSum){minSum sum;}}// 如果最小总和小于1需要抵消负数使其总和大于等于1否则直接返回1return minSum 1 ? -minSum 1 : 1;
}十【提交结果】 Java语言版 Python语言版 C语言版
