leetcode：数组(未完待续)
2016-05-30 本文已影响31人
袁一帆
Search in Rotated Sorted Array
def searchRotatedArray(arr,t):
l,r=0,len(arr)-1
while l<=r:
mid = (l+r)/2
if arr[mid] == t :return mid
if arr[l]<=arr[mid]:
if t<=arr[mid] and t>=arr[l]:r=mid-1
else:l=mid+1
else:
if t>=arr[mid] and t<=arr[r]:l=mid+1
else :r=mid-1
return -1
print searchRotatedArray([3,1],1)
Median of Two Sorted Arrays
Paste_Image.png
def findMedian(a,b):
l = len(a)+len(b)
if l&1:
return kth(a,b,l/2)
else:return (kth(a,b,l/2)+kth(a,b,l/2-1))/2.0
def kth(a,b,k):
if not a:return b[k]
if not b:return a[k]
ia,ib=len(a)//2,len(b)//2
ma,mb=a[ia],b[ib]
if ia+ib<k:
if ma>mb: return kth(a,b[ib+1:],k-ib-1)
else:return kth(a[ia+1:],b,k-ia-1)
else:
if ma>mb: return kth(a[:ia],b,k)
else:return kth(a,b[:ib],k)
print findMedian([1,4,6,8],[3,5,9,12])
# 使用字典，判断左右是否有有效长度
# 计算把连起来的长度，然后更新最左和最右的有效长度
class Solution(object):
def longestConsecutive(self, nums):
res,dic = 0,{}
for n in nums:
if n not in dic:
left = dic.get(n-1,0)
right = dic.get(n+1,0)
l = left+right+1
dic[n]=l
res = max(res,l)
dic[n-left]=l
dic[n+right]=l
return res
# 用字典记录每个数和目标的差值
class Solution(object):
def twoSum(self, nums, target):
if len(nums)<=1:return False
d= {}
for i in range(len(nums)):
if nums[i] in d:
return [d[nums[i]],i]
else:
d[target-nums[i]] =i
# 先排序，然后每次取一个数，这个数字左边部分用2个指针逼近
class Solution(object):
def threeSum(self, nums):
res = []
nums.sort()
for i in xrange(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:l +=1
elif s > 0:r -= 1
else:
res.append((nums[i], nums[l], nums[r]))
while l < r and nums[l] == nums[l+1]: l += 1
while l < r and nums[r] == nums[r-1]: r -= 1
l += 1; r -= 1
return res
# 和3sum思路差不多，就是多个与目标的差值判断，绝对值之差
class Solution(object):
def threeSumClosest(self, nums, target):
nums.sort()
result = nums[0]+nums[1]+nums[2]
for i in range(len(nums)-2):
j,k = i+1,len(nums)-1
while j<k:
sum = nums[i]+nums[j]+nums[k]
if sum == target:
return sum
if abs(sum-target)<abs(result-target):
result = sum
if sum <target:
j+=1
elif sum >target:
k-=1
return result
class Solution(object):
def removeElement(self, nums, val):
i,j=0,len(nums)-1
while i <= j:
if nums[i]!=val:i+=1
elif nums[j]==val:j-=1
else:nums[i],nums[j] = nums[j],nums[i]
return i
# 从后往前找到破坏递减序列的数j，再在后半段找到比j小的，交换位置，对后半段排序
class Solution(object):
def nextPermutation(self, nums):
if not nums:return None
i,j=len(nums)-1,-1
while i>0:
if nums[i-1]<nums[i]:
j=i-1
break
i-=1
for i in xrange(len(nums)-1,-1,-1):
if nums[i]>nums[j]:
nums[i],nums[j] = nums[j],nums[i]
nums[j+1:] = sorted(nums[j+1:])
return
