数据结构与算法-数组题
2017-12-12 本文已影响53人
sylvainwang
1. 3-sums -leetcode 15
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
给一个整数数组，找出3个数，和为0
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
note:做法自然是base于2-sum，遍历数组的每一个数为target，寻找其他数的和为该数的负数 -target
关键在于时间复杂度的优化，复杂度O(n^2)
优化点1: 优先对数组排序，这样碰到某一个target，只用对其后的数组求该-target的2sum，同时能保证最后返回的三元组一定有序
优化点2：结果用set()来存，这样添加结果时候要用.add()方法，将结果三元组保存为tuple (target, -target-i, i) ，
而不能是list [target, -target -i, i] (python里list是unhashable，不能加到set中，最终结果map成list
优化点3: 最外层遍历数组的时候，已经算过的target存入字典中，下次碰到不再计算，否则会卡case 322/323，一个全是[0,0,0,0...]的case
如果miss掉优化点1和2会卡3个case，miss掉优化3会卡最后2个case
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums or len(nums)<3:
return []
nums.sort()
res = set()
d_key = {} # already as target,consider only once
for i in range(len(nums)):
target = nums[i]
d = {}
if target in d_key:
continue
for j in nums[i+1:]:
if -target - j in d:
res.add((target,-target-j,j))
else:
d[j] = 1
d_key[target] = 1
return [list(i) for i in res] # map(list,res)
解法2：双指针方法
leetcode讨论区看到的，和快排的while比较像
即遍历当前列表，到第i位置处，当前位置处的值为target=nums[i]
左指针在下一位lp = nums[i+1]，右指针在最右边nums[len(nums)-1]
比如[-1,-1,0,1,2,4] 定位到第一个-1, left = -1, right =2 是一个解，之后左右指针各往里移动一位，0,1又是一个解，所以返回两个解
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums or len(nums) < 3 :
return []
nums.sort()
res = set()
for i in range(len(nums)-2):
if i >=1 and nums[i] == nums[i-1]: # 和使用d={}存已经计算过的元素一样
continue
target = nums[i]
lp = i+1
rp = len(nums)-1
s = target + nums[lp] + nums[rp]
while lp < rp :
s = target + nums[lp] + nums[rp]
if s < 0 : # s < 0 means lp go right
lp += 1
elif s > 0 :
rp -= 1
else:
res.add((target,nums[lp],nums[rp]))
lp += 1
rp -= 1
while lp < rp and nums[lp ] == nums[lp -1]: # 碰到重复元素的话继续往前
lp += 1
while lp < rp and nums[rp] == nums[rp+1]:
rp -= 1
return [list(i) for i in res]
3. 3-Sums closest
题目描述：在一个数组中找到3个数，要求3个数的和与目标target最接近
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
class Solution:
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums or len(nums) < 3 :
return []
nums.sort()
res = set()
closest = nums[0]+ nums[1] + nums[2]
max_error = abs(nums[0]+ nums[1] + nums[2] - target)
for i in range(len(nums)-2):
if i >=1 and nums[i] == nums[i-1]:
continue
base = nums[i]
lp = i+1
rp = len(nums)-1
s = base + nums[lp] + nums[rp]
while lp < rp :
s = base + nums[lp] + nums[rp]
if abs(s - target) < max_error:
max_error = abs(s - target)
closest = s
if s < target : # s < target means lp go right
lp += 1
elif s > target :
rp -= 1
else:
return target
return closest
4. 4SUMs
和3SUMS 类似，给定数组和target，求4个数的和等于target的数组
可以看做3SUMS的扩展，遍历数组，用target - i 当做3SUM问题的target
上面的3sum是求和为0的3sum，如果改为和为target的，只需加一个参数，然后双指针移动的时候，考虑s与target的相对大小
s < target: lp += 1
s > target: rp += 1
56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
对重合的区间进行merge
首先把二维数组根据第一个元素进行排序：
python里sorted(nums,key=lambda i: i[0])即按照第一个元素排序
本题定义了数据结果，interval由start和end组成，因此sorted(inter,key=lambda i: i.start)
比较两个区间a,b的方法是，如果第一个区间的end元素比第二个区间的start还要小，那两个都保留到结果里，
否则，新区间变为[ min(a[0],b[0]), max(a[1],b[1])]
这里要注意，遍历原来的数组时，每个区间要和之前合并好的区间里最后那个比
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
if not intervals:
return []
intervals = sorted(intervals, key=lambda i: i.start)
out = [intervals[0]] # result list
for i in range(1,len(intervals)):
a = intervals[i] # compare this index and last element of result list
b = out[-1]
if b.end < a.start:
out.append(a)
else:
# out[-1] = Interval(min(a.start,b.start),max(a.end,b.end))
# 这里最好直接更改out[-1]的end元素，不要再创建一个对象，否则效率太低
out[-1].end = max(a.end,b.end)
return out
57. Insert Interval
第57道，插入区间，插入完和前后的区间merge，可以用和上面完全一样的函数，只是输入变成
intervals = intervals + [newinterval]
AC, beat 80%
剑指offer36 数组中的逆序对
在数组中，两个元素，如果前面一个大于后面那个的数字，则形成一个逆序对，输入一个数组，求出所有这个数组中逆序对的总数。
代码基本和归并排序一样，需要计数的地方在cc += len(left) - i 里
left 和 right 都为排序好的升序数组，要merge到一起，当前指针为i,j
如果left[i] <= right[j]: 没有问题，不构成逆序对
如果left[i] > right[j]: 此时merge时要插入right[j]的值，可见right[j]小于left[i]
则right[j]小于 left[ i:] left从i到最后的所有元素。
因此要加 len(left) - i 个逆序对
def reversePair(lst):
global cc
if len(lst) <=1:
return lst
else:
middle = len(lst)//2
left = lst[:middle]
right = lst[middle:]
merge_sort(left)
merge_sort(right)
i,j,k = 0,0,0
while i < len(left) and j< len(right):
if left[i] <= right[j]:
lst[k] = left[i]
i = i + 1
else:
lst[k] = right[j]
cc += len(left) - i # <- 此处为和归并排序唯一区别
# print(len(left) -i)
j = j + 1
k = k + 1
while i < len(left):
lst[k] = left[i]
i += 1
k += 1
while j < len(right):
lst[k] = right[j]
j += 1
k += 1
return lst
if __name__ == '__main__':
lst = [[1,2,3,4,7,6,5],[6,5,4,3,2,1],[1,2,3,4,5,6],[1],[1,2],[2,1],[1,2,1,2,1],[1,7,4,5,3,8,2]]
for i in lst:
cc = 0
reversePair(i)
print(cc)
