本文共 11205 字，大约阅读时间需要 37 分钟。

来看下Leetcode中Tag为的题目

斐波那列序列及其变种

• ：爬山问题,Easy

  dp[i] = dp[i-1]+dp[i-2]

• ：爬山问题，需要支付cost[i]费用,Easy

class Solution(object):    def minCostClimbingStairs(self, cost):        """        :type cost: List[int]        :rtype: int        """        if len(cost)==2:            return max(cost[0],cost[1])        dp=[cost[0],cost[1]]        cost.append(0)        idx = 2        while(idx

• ：最大和子数组,Easy

  dp[i] = max(dp[i-1]+nums,nums)

• ：最大乘子数组,Medium

  关键在于负数的处理

  记录当前乘积的最大值和最小值（因为乘上一个负数就会变成正的）

class Solution(object):    def maxProduct(self, nums):        """        :type nums: List[int]        :rtype: int        """        if nums == []: return 0        ret,maxValue,minValue = nums[0],nums[0],nums[0]        for i in range(1,len(nums)):            a = maxValue*nums[i]            b = minValue*nums[i]            maxValue = max(a,b,nums[i])            minValue = min(a,b,nums[i])            ret = max(ret,maxValue)        return ret

• ：求nums[i:j]的和, Easy

  ∑jk=inums[k]=∑jnums[k]−∑inums[k] ∑ k = i j n u m s [ k ] = ∑ j n u m s [ k ] − ∑ i n u m s [ k ]

  $\sum_{k=i}^jnums[k] = \sum^j nums[k] - \sum^i nums[k]$

class NumArray(object):    def __init__(self, nums):        self.Nums=[0]        for i in range(len(nums)):            self.Nums.append(self.Nums[i]+nums[i])    def sumRange(self, i, j):        return self.Nums[j+1]-self.Nums[i]

• Medium

class NumMatrix(object):    def __init__(self, matrix):        """        :type matrix: List[List[int]]        """        self.sumNum = [[matrix[i][j] for j in range(len(matrix[0]))] for i in range(len(matrix))]        for i in range(len(matrix)):            for j in range(len(matrix[0])):                if i>0:                    self.sumNum[i][j] += self.sumNum[i-1][j]                if j>0:                    self.sumNum[i][j] += self.sumNum[i][j-1]                if i>0 and j>0:                    self.sumNum[i][j] -= self.sumNum[i-1][j-1]    def sumRegion(self, row1, col1, row2, col2):        """        :type row1: int        :type col1: int        :type row2: int        :type col2: int        :rtype: int        """        ret = self.sumNum[row2][col2]        if row1>0:            ret -= self.sumNum[row1-1][col2]        if col1>0:            ret -= self.sumNum[row2][col1-1]        if row1>0 and col1>0:            ret += self.sumNum[row1-1][col1-1]        return ret

• ：统计从0到n二进制中的1的个数，Medium

  dp[i] = dp[i&(i-1)]+1

class Solution(object):    def countBits(self, num):        """        :type num: int        :rtype: List[int]        """        ret=[0 for i in range(num+1)]        for i in range(1,num+1):            ret[i]=ret[i&(i-1)]+1        return ret

• ：求一个字符串中回文子字符串的总个数，Medium

  判断s[i:j+1]是否是回文等价于判断s[i+1:j] 和 s[i][j]的情况

class Solution(object):    def countSubstrings(self, s):        """        :type s: str        :rtype: int        """        if s=='': return 0        size = len(s)        dp = [[0 for i in range(size)] for j in range(size)]        ret = 0        for i in range(size):            dp[i][i]=1            for j in range(i):                if s[i]==s[j]:                    if dp[i-1][j+1] or j==i-1:                        dp[i][j] = 1            ret += sum(dp[i])        return ret

• :Medium

  dp[x] = max(dp[x - 1], dp[x - 2] + cnt[x] * x)

import collectionsclass Solution(object):    def deleteAndEarn(self, nums):        """        :type nums: List[int]        :rtype: int        """        cnt = collections.Counter(nums)        maxn = max(nums + [0])        dp = [0] * (maxn + 10)        for x in range(1, maxn + 1):            dp[x] = max(dp[x - 1], dp[x - 2] + cnt[x] * x)        return dp[maxn]

• ：判断能够组成等差数列数组的个数，Medium

  初始化dp = [0]*size

  如果nums[i]-nums[i-1]==nums[i-1]-nums[i-2] 则dp[i] = dp[i-1]+1

  把最后的dp结果求和

class Solution(object):    def numberOfArithmeticSlices(self, A):        """        :type A: List[int]        :rtype: int        """        if A == []: return 0        dp = [0]*len(A)        ans = 0        for i in range(2,len(A)):            if A[i]-A[i-1] == A[i-1]-A[i-2]:                dp[i] = dp[i-1]+1            ans+=dp[i]        return ans

• ：
  返回数组A的等差子序列切片个数，Hard

  dp[x][delta] = dp[y][delta]+1

import collectionsclass Solution(object):    def numberOfArithmeticSlices(self, A):        """        :type A: List[int]        :rtype: int        """        dp = [collections.defaultdict(int) for i in range(len(A))]        ans = 0        for i in range(len(A)):            for j in range(i):                delta = A[i]-A[j]                dp[i][delta]+=1                if delta in dp[j]:                    dp[i][delta]+=dp[j][delta]                    ans+=dp[j][delta]        return ans

• ：求word1 和 word2所需最少的删次数能够成为两个相同的字符串，Medium

  if i==0 or j==0: dp[i][j] = i+j

  if word1[i-1] == word2[j-1] : dp[i][j] = dp[i-1][j-1]

  else

  dp[i][j] =min(dp[i][j-1],dp[i-1][j])+1

class Solution(object):    def minDistance(self, word1, word2):        """        :type word1: str        :type word2: str        :rtype: int        """        l1,l2 = len(word1),len(word2)        dp = [[0 for i in range(l2+1)] for j in range(l1+1)]        for i in range(l1+1):            for j in range(l2+1):                if i==0 or j==0:                    dp[i][j] = i+j                elif word1[i-1] == word2[j-1]:                    dp[i][j] = dp[i-1][j-1]                else:                    dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1        return dp[l1][l2]

• ：删除字符的代价是被删字符ASCII之和，求最小代价。Medium

class Solution(object):    def minimumDeleteSum(self, s1, s2):        """        :type s1: str        :type s2: str        :rtype: int        """        l1,l2 = len(s1),len(s2)        dp = [[0 for i in range(l2+1)] for j in range(l1+1)]        for i in range(1,l1+1):            dp[i][0]+=ord(s1[i-1])+dp[i-1][0]        for j in range(1,l2+1):            dp[0][j]+=ord(s2[j-1])+dp[0][j-1]        for i in range(1,l1+1):            for j in range(1,l2+1):                if s1[i-1]==s2[j-1]:                    dp[i][j] = dp[i-1][j-1]                else:                    dp[i][j] =min(dp[i-1][j]+ord(s1[i-1]),dp[i][j-1]+ord(s2[j-1]))        return dp[l1][l2]

• ：求从word1到word2所需最少的增／删／改次数，Hard

  ret[i+1][j+1]=min(ret[i][j],ret[i][j+1],ret[i+1][j])+1

class Solution(object):    def minDistance(self, word1, word2):        """        :type word1: str        :type word2: str        :rtype: int        """        n1=len(word1);n2=len(word2)        tmp=[0 for i in range(n2+1)]        ret=[tmp[:] for i in range(n1+1)]        for i in range(n1+1):            ret[i][0]=i        for j in range(n2+1):            ret[0][j]=j        for i in range(n1):            for j in range(n2):                if word1[i]==word2[j]:                    ret[i+1][j+1]=ret[i][j]                else:                    ret[i+1][j+1]=min(ret[i][j],ret[i][j+1],ret[i+1][j])+1        return ret[n1][n2]

• 给定一组数对，我们定义当且仅当b < c时，(c, d)可以链在(a, b)之后。求可以组成的最长数对链的长度。Medium
  思路：对第二个元素排序，一趟遍历

class Solution(object):    def findLongestChain(self, pairs):        """        :type pairs: List[List[int]]        :rtype: int        """        pairs.sort(key = lambda x: x[1])        last = [-0x7FFFFFFF, -0x7FFFFFFF]        ans = 0        for p in pairs:            if p[0] > last[1]:                ans += 1                last = p        return ans

• 给定给一个正整数n，将其分解成至少两个正整数的和，使这些整数的积最大化。返回可以得到的最大乘积。Medium
  dp[i]表示整数i拆分可以得到的最大乘积，则dp[i]只与dp[i - 2], dp[i - 3]两个状态有关

class Solution(object):    def integerBreak(self, n):        """        :type n: int        :rtype: int        """        if n<=3: return n-1        dp = [0]*(n+1)        dp[2] = 2        dp[3] = 3        for i in range(4,n+1):            dp[i] = max(3*dp[i-3],2*dp[i-2])        return dp[n]

• ：计算[0,$10^n$)没有重复数字的个数

  n = 1: 10

  n = 2: 10+9*9

  n = 3: 10+9*9+

  C19C19C18 C 9 1 C 9 1 C 8 1

  $C_9^1C_9^1C_8^1$

class Solution(object):    def countNumbersWithUniqueDigits(self, n):        """        :type n: int        :rtype: int        """        dp=[1]        for i in range(1,n+1):            if i==1:                dp.append(10)            else:                tmp=9                flag=9                j=i-1                while(j>0):                    tmp=tmp*flag                    flag=flag-1                    j=j-1                dp.append(dp[-1]+tmp)        return dp[-1]

• ：初始’A’，只能进行全复制、全粘贴操作，求得到n个A所需要的最少次数，Medium

  dp[i] = min(dp[i],dp[k]+i/k])

class Solution(object):    def minSteps(self, n):        """        :type n: int        :rtype: int        """        if n <=1:            return 0        dp = [0 for i in range(n+1)]        for i in range(2,n+1):            dp[i]=i            for k in range(2,i/2+1):                if i%k==0:                    dp[i]=min(dp[i],dp[k]+i/k)        return dp[-1]

• ：判断字符串A是否是字符串B的子序列（不一定连续），Medium

  这题长得不像dp - - ，搞两个指针即可

class Solution(object):    def isSubsequence(self, s, t):        """        :type s: str        :type t: str        :rtype: bool        """        pos_s = 0        pos_t = 0        while(pos_s

• ！！！：求nums增加正负号使得结果等于S的个数

class Solution(object):    def findTargetSumWays(self, nums, S):        if nums == []: return 0        dics = {nums[0]:1,-nums[0]:1} if nums[0] else {
  0:2}        for i in range(1,len(nums)):            tmp = {}            for d in dics:                tmp[d+nums[i]] = tmp.get(d+nums[i],0)+dics.get(d,0)                tmp[d-nums[i]] = tmp.get(d-nums[i],0)+dics.get(d,0)            dics = tmp        return dics.get(S,0)

• ：给一个字符串和单词列表，判断字符串能不能由这些单词组成，Medium

思路是用数组dp，dp[i] 表示 字符串 s[:i+1] 能否由单词列表中的单词组成

那么可以得到 dp[i] = dp[j] and (s[j:i+1] in wordlist) for j in j in range(i)

class Solution(object):    def wordBreak(self, s, wordDict):        """        :type s: str        :type wordDict: List[str]        :rtype: bool        """        worddict = {}        for word in wordDict:            worddict[word] = True        dp = [True]+[False for i in s]        for i in range(len(s)):            for j in range(i+1):                if s[j:i+1] in worddict and dp[j]==True:                    dp[i+1] = True                    break        return dp[-1]

• ：返回由[1,2,…,n]组成的所有二叉搜索树的列表，Medium.

思路：先确定root，在递归获取root.left和root.right

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def generateTrees(self, n):        """        :type n: int        :rtype: List[TreeNode]        """        arrays = [i for i in range(1,n+1)]        return self.dp(arrays)    def dp(self,arrays):        if len(arrays) == 1:            return [TreeNode(arrays[0])]        ret = []        for k in range(len(arrays)):            num = arrays[k]            l = arrays[0:k]            r = arrays[k+1:]            left = self.dp(l)            right = self.dp(r)            if left == []:                for j in range(len(right)):                    Node = TreeNode(num)                    Node.right = right[j]                    ret.append(Node)            if right == []:                for i in range(len(left)):                    Node = TreeNode(num)                    Node.left = left[i]                    ret.append(Node)            for i in range(len(left)):                for j in range(len(right)):                    Node = TreeNode(num)                    Node.left = left[i]                    Node.right = right[j]                    ret.append(Node)        return ret

转载地址：http://hfqmi.baihongyu.com/