网站建设中出现的问问题,房地产网站推广,韶关企业网站建设公司,台州北京网站建设53. 最大子数组和
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组
是数组中的一个连续部分。
示例 1#xff1a;
**输入#xff1a;nums [-2,1,-3,4,-1,2,1,…53. 最大子数组和
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组
是数组中的一个连续部分。
示例 1
**输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6 。
类似于动态规划方法dp[i]表示以i结尾的元素的最大子数组和。状态转移方程 dp[i]max(dp[i-1] nums[i], nums[i]) dp[0]nums[0]
class Solution:def maxSubArray(self, nums: List[int]) - int:dp [0] * len(nums)dp[0] nums[0]result nums[0]for i in range(1, size):dp[i] max(dp[i-1]nums[i], nums[i])result max(result, dp[i])return resultdp[i]的计算和dp[i-1], nums[i]有关也可以把dp数组去掉使用pre、cur来代替predp[i-1], curdp[i]节省空间。
56. 合并区间
以数组 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].
先对原数组intervals按照每个pair的第一个元素按照升序排序遍历排序后的数组同时将一个元素加到结果数组res中当遍历到非第一个元素时比较res数组的最后一个区间的右边界和当前区间的左边界如果重合即res[-1][1] intervals[i][0], 进行区间合并将res中最后一个区间的右边界更新为当前元素的右边界如果不重合直接加入到结果数组中。
区间合并比如说intervals [[1,4], [2,3]], 完全包围 res[-1][1] max(intervals[i][1], res[-1][1])
class Solution:def merge(self, intervals: List[List[int]]) - List[List[int]]:intervals sorted(intervals, keylambda x: x[0])res [intervals[0]]for i in range(1, len(intervals)):if intervals[i][0] res[-1][1]:res[-1][1] max(intervals[i][1], res[-1][1])else:res.append(intervals[i])return res对于append来说可以把intervals[0]的操作和非重合操作合并起来合并后的代码
class Solution:def merge(self, intervals: List[List[int]]) - List[List[int]]:intervals.sort(key lambda x : x[0])merged []for i in intervals:# 数组为空 or 区间不重合if not merged or merged[-1][1] i[0]:merged.append(i)else:merged[-1][1] max(i[1], merged[-1][1])return merged
189. 轮转数组
给定一个整数数组 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]
利用python的数组切片切片后的数组直接拼接得到最终结果。 num[:] aaa, 实现数组的原地修改而不是直接赋值—导致nums的地址改变。
class Solution:def rotate(self, nums: List[int], k: int) - None:Do not return anything, modify nums in-place instead.k k % len(nums)nums[:] nums[-k:] nums[:-k]想办法通过数学运算推导出每个元素的最终位置通过建立一个映射关系遍历一次数组直接得到最终答案。
首先要考虑k和N的关系k有可能大于N这个时候要对k k % N去除非必要操作。 (i k) % N arr_nums[(i k) % N] nums[i] 使用一个辅助数组最后将辅助数组的顺序赋值给nums实现原地修改。
另一种方法通过多次翻转实现。
reverse(nums) 7 6 5 4 3 2 1reverse(nums[:k %N]) 5 6 7 4 3 2 1reverse(nums[k %N:]) 5 6 7 1 2 3 4
238. 除自身以外数组的乘积
给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法且在 O(_n_) 时间复杂度内完成此题。
示例 1:
输入: nums [1,2,3,4] 输出: [24,12,8,6]
不能使用除法如果可以使用除法我们可以计算一个乘积同时结合当前元素是否为0特判。另一种思路双层循环result[i] ply[0:i] * ply[i1: ], 即按照本身定义计算但是时间复杂度比较高。为了进行优化可以使用另外的数组存储lply[i] , rply[i1:]. class Solution:def productExceptSelf(self, nums: List[int]) - List[int]:nlen(nums)L,R,ans[0]*n,[0]*n,[0]*nL[0]1for i in range(1,n):L[i]L[i-1]*nums[i-1] #i左边的乘积R[n-1]1for i in reversed(range(n-1)):R[i]R[i1]*nums[i1] #i右边的乘积for i in range(n):ans[i]L[i]*R[i]return ansclass Solution:def productExceptSelf(self, nums: List[int]) - List[int]:res [1] * len(nums)for i in range(1, len(nums)):res[i] res[i - 1] * nums[i - 1]suf 1for i in range(len(nums) - 1, -1, -1):res[i] * sufsuf * nums[i] return res41. 缺失的第一个正数
给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1
**输入nums [1,2,0] 输出3 解释范围 [1,2] 中的数字都在数组中。
一种思路for循环遍历 1~N1判断是否在数组中如果不再返回即可。另一种思路置换法理解为将数组排序后理论上 i 下 值为 i1即nums[i]应该出现在下标i1上最后依次遍历找到第一个不符合关系的元素。
class Solution: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[i], nums[nums[i] - 1] 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
