leetcode：数组(未完待续)

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])

Longest Consecutive Sequence

# 使用字典，判断左右是否有有效长度
# 计算把连起来的长度，然后更新最左和最右的有效长度
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

Two Sum

# 用字典记录每个数和目标的差值
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

3Sum

# 先排序，然后每次取一个数，这个数字左边部分用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 Closest

# 和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

4Sum

Remove Element

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

Next Permutation

# 从后往前找到破坏递减序列的数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