广州做网站怎么样,培训机构的网站建设,桂林最新情况最新数据,网站开发计什么科目1.学习
2.数组
2.1第53题-最大子数组和
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组 是数组中的一个连续部分。
心得#xff1a;一直在纠结这个连续的事情请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。
心得一直在纠结这个连续的事情最后发现根本没必要管因为如果前一个数与当前数相加小于当前数前面的部分就会直接被舍弃如果相加大于当前数则会一直叠加。
class Solution(object):def maxSubArray(self, nums)::type nums: List[int]:rtype: intdp copy.deepcopy(nums)max_ dp[0]for i in range(1,len(nums)):dp[i] max(dp[i-1]nums[i], dp[i])if max_ dp[i]:max_ dp[i]return max_ 时间和内存占用太多根本没必要再生成一个dp数组直接用nums数组更新就行。
class Solution(object):def maxSubArray(self, nums)::type nums: List[int]:rtype: int# dp copy.deepcopy(nums)max_ nums[0]for i in range(1,len(nums)):nums[i] max(nums[i-1]nums[i], nums[i])if max_ nums[i]:max_ nums[i]return max_ 2.2第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].示例 2
输入intervals [[1,4],[4,5]]
输出[[1,5]]
解释区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution(object):def merge(self, intervals)::type intervals: List[List[int]]:rtype: List[List[int]]new_int []a []intervals.sort()for i in range(1,len(intervals)):# 前一个end大于后一个startif intervals[i-1][1] intervals[i][0]:# 前一个end小于后一个endif intervals[i-1][1] intervals[i][1]:intervals[i] [intervals[i-1][0], intervals[i][1]]else:intervals[i] intervals[i-1]elif intervals[i-1][1] intervals[i][0]:intervals[i] [intervals[i-1][0], intervals[i][1]]else:new_int.append(intervals[i-1])new_int.append(intervals[-1])return new_int 2.3第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]
class Solution(object):def rotate(self, nums, k)::type nums: List[int]:type k: int:rtype: None Do not return anything, modify nums in-place instead.# if k 0:# return numsnums1 copy.deepcopy(nums)k k % len(nums)start len(nums)-k# nums2 []# nums1 nums[:start]# nums2 nums[start:]for i in range(len(nums)):if i k:nums[i] nums[starti]else:nums[i] nums1[i-k] 感觉不用深拷贝整个数组
class Solution(object):def rotate(self, nums, k)::type nums: List[int]:type k: int:rtype: None Do not return anything, modify nums in-place instead.k k % len(nums)start len(nums)-knums1 nums[:start]nums2 nums[start:]for i in range(len(nums2)):nums[i] nums2[i]for j in range(len(nums1)):nums[jk] nums1[j] 看了答案发现我最早想出的方法就是最简单的答案nums[:]nums[start:]nums[:start]但是发现一直不能修改nums的值看了答案发现nums忘记加[:]了吐了。
class Solution(object):def rotate(self, nums, k)::type nums: List[int]:type k: int:rtype: None Do not return anything, modify nums in-place instead.k k % len(nums)start len(nums)-knums[:] nums[start:] nums[:start] 2.4除自身以外数组的乘积
给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums [1,2,3,4]
输出: [24,12,8,6]
先用最简单的遍历法果然超时。
class Solution(object):def productExceptSelf(self, nums)::type nums: List[int]:rtype: List[int]len_ len(nums)answer [1]*len_for i in range(len_):for j in range(len_):if j ! i:answer[i] answer[i]*nums[j]return answer 然后把数组分为i点的前半部分和后半部分相乘来计算这样的话减少很多重复计算的时间。
class Solution(object):def productExceptSelf(self, nums)::type nums: List[int]:rtype: List[int]# 可以把乘积分为前半部分和后半部分len_ len(nums)answer [1]*len_forward [1]*len_back [1]*len_for i in range(1,len_):forward[i] forward[i-1]*nums[i-1]for j in reversed(range(len_-1)):back[j] back[j1]*nums[j1]for k in range(len_):answer[k] forward[k]*back[k]return answer 看了答案知道了左边的乘积其实可以动态的变化
class Solution(object):def productExceptSelf(self, nums)::type nums: List[int]:rtype: List[int]# 可以把乘积分为前半部分和后半部分len_ len(nums)answer [1]*len_back 1for i in range(1,len_):answer[i] answer[i-1]*nums[i-1]for j in reversed(range(len_)):answer[j] answer[j]*backback back * nums[j]return answer 2.5第41题-缺失的第一个正数
给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1
输入nums [1,2,0]
输出3
用最朴素的方法来寻找不出所料超时。
class Solution(object):def firstMissingPositive(self, nums)::type nums: List[int]:rtype: intfor i in range(len(nums)-1):j 0while j len(nums)-1-i:if nums[j] nums[j1]:temp nums[j]nums[j] nums[j1]nums[j1] tempj j 1# print(nums)if nums[-1] 0:return 1index_1 0for j in range(len(nums)):if nums[j] 0:if nums[j] ! 1:return 1else:index_1 jbreaka 1# print(index_1)for k in range(index_11,len(nums)):a a 1if nums[k] a:continueelif nums[k] a-1:a a - 1continueelse:return areturn a 1 看了解析知道当nums长度为N时正数的数目肯定在[1,N]范围内这时候就可以用哈希表来查找内存占用多但速度快。把nums中的数都放在哈希表中然后遍历[1,N]如果有哈希表中不存在则返回i若都存在则返回i1。
class Solution(object):def firstMissingPositive(self, nums)::type nums: List[int]:rtype: inthash_table set(nums)n len(nums)a 0for i in range(1,n1):if i in hash_table:a icontinueelse:return ireturn a 1
