基本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