网站模版 优帮云,南昌网站制作,网站建设单位是什么,网页制作教程 赵丰年13、最大子数组和
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组 是数组中的一个连续部分。
示例 1#xff1a;
输入#xff1a;nums [-2,1,-3,4,-1,2,1,-5,…13、最大子数组和
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。
示例 1
输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 。
示例 2
输入nums [1]
输出1
示例 3
输入nums [5,4,-1,7,8]
输出23
提示
1 nums.length 105-104 nums[i] 104
思路解答
状态定义定义一个状态dp[i]表示以第i个元素结尾的子数组的最大和。状态转移方程状态转移方程为dp[i] max(nums[i], dp[i-1] nums[i])即要么以第i个元素结尾的子数组最大和是第i个元素本身要么是第i个元素加上以第i-1个元素结尾的子数组的最大和。初始状态初始状态为dp[0] nums[0]即以第一个元素结尾的子数组的最大和就是第一个元素本身。遍历数组从第二个元素开始遍历整个数组根据状态转移方程更新dp数组。返回结果最终返回dp数组中的最大值即为最大子数组的和。
def maxSubArray(self, nums: list[int]) - int:if not nums:return 0dp [0] * len(nums)dp[0] nums[0]max_sum nums[0]for i in range(1, len(nums)):dp[i] max(nums[i], dp[i - 1] nums[i])max_sum max(max_sum, dp[i])return max_sum
14、合并区间
以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
示例 1
输入intervals [[1,3],[2,6],[8,10],[15,18]]
输出[[1,6],[8,10],[15,18]]
解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2
输入intervals [[1,4],[4,5]]
输出[[1,5]]
解释区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示
1 intervals.length 104intervals[i].length 20 starti endi 104
思路解答
排序首先对所有区间按照起始位置进行排序。合并区间然后从第二个区间开始逐个判断当前区间和前一个区间是否重叠如果重叠则合并否则将前一个区间加入结果数组。返回结果最终返回合并后的区间数组。
def merge(self, intervals: list[list[int]]) - list[list[int]]:if not intervals:return []intervals.sort(keylambda x: x[0])merged [intervals[0]]for i in range(1, len(intervals)):if intervals[i][0] merged[-1][1]:merged[-1][1] max(merged[-1][1], intervals[i][1])else:merged.append(intervals[i])return merged
15、轮转数组
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
示例 1:
输入: nums [1,2,3,4,5,6,7], k 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入nums [-1,-100,3,99], k 2
输出[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示
1 nums.length 105-231 nums[i] 231 - 10 k 105
思路解答
整体翻转将整个数组翻转这样原数组的后k个元素会变到数组的前面。前部翻转翻转前k个元素将原数组的后k个元素翻转回来此时前k个元素已经在正确位置上。后部翻转翻转剩余的n-k个元素将原数组的前n-k个元素翻转回来此时整个数组就完成了向右旋转k个位置的操作。
def rotate(self, nums: list[int], k: int) - None:n len(nums)k k % n # 处理k大于数组长度的情况def reverse(arr, start, end):while start end:arr[start], arr[end] arr[end], arr[start]start 1end - 1reverse(nums, 0, n - 1)reverse(nums, 0, k - 1)reverse(nums, k, n - 1)
16、除自身以外数组的乘积
给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法**且在 O(*n*) 时间复杂度内完成此题。
示例 1:
输入: nums [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums [-1,1,0,-3,3]
输出: [0,0,9,0,0]
提示
2 nums.length 105-30 nums[i] 30保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
思路解答
左右乘积法我们可以通过一次遍历来计算每个元素左侧所有元素的乘积并将结果存储在结果数组中。然后再进行一次反向遍历计算每个元素右侧所有元素的乘积并将其与之前计算的左侧乘积相乘得到最终结果。
def productExceptSelf(self, nums: list[int]) - list[int]:n len(nums)answer [1] * n# 计算每个元素左侧所有元素的乘积left_product 1for i in range(n):answer[i] * left_productleft_product * nums[i]# 计算每个元素右侧所有元素的乘积并与左侧乘积相乘right_product 1for i in range(n - 1, -1, -1):answer[i] * right_productright_product * nums[i]return answer
17、缺失的第一个正数
给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1
输入nums [1,2,0]
输出3
示例 2
输入nums [3,4,-1,1]
输出2
示例 3
输入nums [7,8,9,11,12]
输出1
提示
1 nums.length 5 * 105-231 nums[i] 231 - 1
思路解答
将数组调整为哈希表遍历数组将每个正整数 nums[i] 调整到正确的位置 nums[nums[i]-1] 上。例如如果 nums[i] 3将 3 调整到索引 2 的位置上。再次遍历找出第一个缺失的正整数再次遍历数组找出第一个不在正确位置上的正整数其索引加1即为缺失的最小正整数。
def firstMissingPositive(self, nums: list[int]) - int:n len(nums)# 将每个正整数调整到正确的位置上for i in range(n):while 1 nums[i] n and nums[nums[i] - 1] ! nums[i]:nums[nums[i] - 1], nums[i] nums[i], nums[nums[i] - 1]# 再次遍历找出第一个缺失的正整数for i in range(n):if nums[i] ! i 1:return i 1return n 1
