BabbleDay's Blog

基本DP O(mn)

def uniquePaths(self, m, n):
        record = []
        record.append([1]*n)
        for i in range(1,m):
            temp = [1]
            for j in range(1,n):
                temp.append(record[-1][j]+temp[-1])
            record.append(temp)
        return record[m-1][n-1]

优化：O(m+n) 二项式系数

递归超时，因为中间部分的格子到目标的路径每次都重新算了一遍，树状重复＝ ＝

def uniquePaths(self, m, n):

        def isValid(x,y):
            return (x<m and x>=0 and y<n and y>=0)
        
        def goNext(x,y):
            if x==m-1 and y==n-1:
                return 1
            if isValid(x,y):
                return goNext(x+1,y) + goNext(x,y+1)
            else:
                return 0
        
        return goNext(0,0)

默认递增，一旦递减就返回

def findMin(self, nums):
        rtn = nums[0]
        for i in range(len(nums)-1):
            if nums[i+1]<rtn:
                return nums[i+1]
        return rtn

优化至O(logN)

最基本DP

def maxSubArray(self, nums):
        output = [nums[0]]
        for i in range(1,len(nums)):
            output.append( max(output[i-1]+nums[i],nums[i]) )
        return max(output)

优化：用变量代替数组

def maxSubArray(self, nums):
        t, rtn = nums[0], nums[0]
        for i in range(1, len(nums)):
            t = max(t+nums[i], nums[i])
            rtn = max(rtn, t)
        return rtn

二分插入

def searchInsert(self, nums, target):
        l, r, i = 0, len(nums)-1, 0
        while l<r:
            i = (l+r)/2
            if nums[i]<target:
                if l==i:
                    i += 1
                l = i
            elif nums[i]>target:
                r = i
            else:
                return i
        if nums[i]<target:
            return i+1
        return i

关注插入点 Most Voted Solution

public int searchInsert(int[] A, int target) {
        int low = 0, high = A.length-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(A[mid] == target) return mid;
            else if(A[mid] > target) high = mid-1;
            else low = mid+1;
        }
        return low;
    }

系列一

def maxProfit(self, prices):
        rtn = 0
        if len(prices)!=0:
            buy = prices[0]
            for i in range( len(prices) ):
                buy = min(buy, prices[i])
                rtn = max(rtn, prices[i]-buy)
        return rtn

系列二：正常考虑单调

def maxProfit(self, prices):
        buy, sell, rtn = -1, -1, 0
        for i in range(len(prices)-1):
            if buy==-1 and prices[i+1]>prices[i]:
                buy = prices[i]
            if buy!=-1 and prices[i+1]<prices[i]:
                sell = prices[i]
                rtn += sell - buy
                buy = -1
        if buy!=-1:
            rtn += prices[-1] - buy
        return rtn

而实际上。。。若今天比昨天高，那就昨买今卖就好了＝ ＝

def maxProfit(self, prices):
        rtn = 0
        for i in range(1,len(prices)):
            if prices[i]>prices[i-1]:
               rtn += prices[i] - prices[i-1]
        return rtn

心得：特殊情况还是单独处理，可以简化思路，代码正确实现后，再考虑合并特殊情况

def summaryRanges(self, nums):
        rtn = []
        if len(nums) == 0:
            return rtn
        if len(nums) == 1:
            rtn.append(str(nums[0]))
            return rtn

        i = 0
        while(i<len(nums)):
            start = nums[i]
            end = nums[i]
            while(i+1<len(nums) and end+1 == nums[i+1]):
                end = nums[i+1]
                i += 1

            if start==end:
                rtn.append(str(start))
            else:
                rtn.append(str(start)+"->"+str(end))
            i += 1
        
        return rtn

方法一 insert执行效率低

    def rotate(self, nums, k):
        for _ in range(k):
            nums.insert(0,nums[-1])
            del(nums[-1])
        return

方法二 list赋值

def rotate(self, nums, k):
        k = k % len(nums)
        nums[:] = nums[-k:] + nums[:-k] 

心得：思考要完整。。。

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {boolean}
    def containsNearbyDuplicate(self, nums, k):
        dict = {}
        for i in range(len(nums)):
            if(nums[i] in dict):
                if(i-dict[nums[i]]<=k):
                    return True
            dict[nums[i]] = i
        return False

注意这里的输入是行的Index，不是行数

通过记录上一行

class Solution:
    # @param {integer} rowIndex
    # @return {integer[]}
    def getRow(self, rowIndex):
        rtn, prev = [1], [1,1]
        for k in range(rowIndex+1):
            rtn = [1] * (k+1)
            if k>1:
                for j in range(1,k):
                    rtn[j] = prev[j-1] + prev[j]
                prev = rtn
        return rtn

在一行内解决

观察

1 3 3 1

S1: 尾部加一  1 3 3 1 1

S2: 从倒数第二个到正数第二个，每个数变成当前数与其左边的数之和

1 3 3 4 1

1 3 6 4 1

1 4 6 4 1

class Solution:
    # @param {integer} numRows
    # @return {integer[][]}
    def generate(self, numRows):
        if numRows == 0:
            return []
        if numRows == 1:
            return [[1]]
        rtn = [[1],[1,1]]
        for i in range(2,numRows):
            temp = [1]
            for j in range(1, i):
                temp.append(rtn[i-1][j-1]+rtn[i-1][j])
            temp.append(1)
            rtn.append(temp)
        return rtn

归并边界 Most Voted Solution

class Solution:
# @return a list of lists of integers
def generate(self, numRows):
    lists = []
    for i in range(numRows):
        lists.append([1]*(i+1))
        if i>1 :
            for j in range(1,i):
                lists[i][j]=lists[i-1][j-1]+lists[i-1][j]
    return lists