概述
day6
● 454.四数相加II
解题思路:
前面两个数组的元素遍历相加,把和变成一个字典的key,和的个数变成value。然后遍历后面两个数组的元素加和,如果后面的和是 1- key的话,就记录次数。这样就可以把时间复杂度从n^ 4 变成 n ^2 了
注意判断是否有key的时候:
应该是if i in dict比if i in dict.keys() 快,大概是.keys()返回列表了更复杂。具体python怎么实现的看不到
● 383. 赎金信
涉及到字母的时候就可以考虑使用ascii码去代表下标:ord(‘x’)-ord(‘a’)
由于ascii码是int类型,就可以使用list巧妙的代替dict巧妙的减小空间复杂度
class Solution(object):
def canConstruct(self, ransomNote, magazine):
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
lis_mag = [0 for i in range(26)]
for c in magazine:
lis_mag[ord(c)-ord('a')] += 1
for c in ransomNote:
lis_mag[ord(c)-ord('a')]-=1
if lis_mag[ord(c)-ord('a')] == -1:
return False
return True
● 15. 三数之和 (有点复杂)
使用双指针的揭发去解这道群题:先排序,再固定A,然后遍历BC。由于已经进行了排序操作,所以去重操作可以在添加结果的过程中比较ABC的前后元素来进行。
比较重要的是去重的操作:
首先A的去重操作:A要和前面的元素比较是否相等。这样就不会在结果的三元组之中去重。因为B可能紧挨着A然后他们的数值一样比如 -1 -1 2
然后是B和C的去重操作例如0 -1 -1 -1 -1 1 1 1 1
分别是左右指针的去重。左右指针如果和下一个元素的值相同就跳过。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# 先找出所有的三元组
res = []
nums.sort()
for i in range(len(nums)):
left = i+1
right = len(nums)-1
if nums[i]>0 :
break
# A去重操作
if nums[i] == nums[i-1] and i >=1:
continue
while left < right:
if nums[i]+nums[left]+nums[right] == 0:
res.append([nums[i],nums[left],nums[right]])
# 加进去之后B和C的去重操作
while left != right and nums[left] == nums[left+1]:
left+=1
while right != left and nums[right] ==nums[right-1]:
right-=1
left +=1
right -= 1
elif nums[i]+nums[left]+nums[right] < 0:
left += 1
else:
right -= 1
return res
● 18. 四数之和 (系列问题,值得深思)
和三数之和有社么不一样的地方吗?
第一点:
求和个数不同导致for循环的层数增加
第二点:
但是!!!!!!!!!!
剪不明白可以不剪啊老铁
剪枝的方法不一致:
原因在于原来的traget的值是0
现在的天arget的值是任意给出的
当对数组进行排序之后,我们可以发现的是如果target是0 , A大于taget,默认整个数组的值都是正数。正数的和一定是大于0的,所以会越加越大
但是如果target是负数的话剪枝操作不成立。原因是如果A大于target。A仍然有可能是负数,B和C仍然有可能是负数。所以A+B+C会让和小于A,所以如果A大于target,和仍然有可能等于target。所以不能剪枝
总结:
剪枝的条件是:
A大于taget,target>=0
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
res = []
for i in range(len(nums)):
if nums[i] > target and target >= 0:
break
if nums[i] == nums[i-1] and i >0:
continue
for j in range(i+1 , len(nums)):
two = nums[i] +nums[j]
if two > target and target >= 0:
break
if nums[j] == nums[j-1] and j > i+1:
continue
left = j +1
right = len(nums) -1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
res.append([nums[i] , nums[j] , nums[left] ,nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1
right -= 1
elif total> target:
right -= 1
elif total < target:
left += 1
return res
● 总结
最后
以上就是明理烤鸡为你收集整理的代码随想录刷题第6天 ● 454.四数相加II ● 383. 赎金信 ● 15. 三数之和 ● 18. 四数之和的全部内容,希望文章能够帮你解决代码随想录刷题第6天 ● 454.四数相加II ● 383. 赎金信 ● 15. 三数之和 ● 18. 四数之和所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复