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;
    }

过早优化是万恶之源＝ ＝

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int l = nums.length;
        int[] output = new int[l];
        int[] a = new int[l];
        int[] b = new int[l];
        for(int i=0; i<l; i++){
            a[i] = 1;
            b[i] = 1;
        }
        for(int i=1; i<l; i++){
            int j = l-i-1;
            a[i] *= nums[i-1] * a[i-1];
            b[j] *= nums[j+1] * b[j+1];
        }
        for(int i=0; i<l; i++) output[i] = a[i] * b[i];
        return output;
    }
}

优化：用一个变量代替数组

public class Solution {
public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    res[0] = 1;
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= right;
        right *= nums[i];
    }
    return res;
}

系列一

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

心得：编程语言随机应变＝ ＝

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int l = m + n - 1;
        int a = m-1;
        int b = n-1;
        int i=l;
        while(i>=0){
            if(a<0) nums1[i--] = nums2[b--];
            else if(b<0) nums1[i--] = nums1[a--];
            else if(nums1[a]>nums2[b]) nums1[i--] = nums1[a--];
            else nums1[i--] = nums2[b--];
        }
    }
}