Python3刷题系列（六）

# leetcode-70:
''' 斐波那契数列问题：一共n阶台阶，倒数第一步时，无视前面怎么走，有两种走法：
    1.走一步
    2.走两步
两种走法的走法种数相加就是n阶台阶的情况下的所有种数，即：f(n)=f(n-1)+f(n-2)'''
class Solution:  # 战胜78.16%
    def climbStairs(self, n: int) -> int:
        count = [1, 2]
        for i in range(2, n):
            count.append(count[i-1] + count[i-2])
        return count[n-1]

class Solution:  # 战胜78.16%
    def climbStairs(self, n: int) -> int:
        count = [1, 1]
        for i in range(2, n+1):  # 与上面解法一致，区别仅在于列表index不同
            count.append(count[i-1] + count[i-2])
        return count[n]

# 递归解法：不出意料超时了
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n-1) + self.climbStairs(n-2)

# leetcode-17: 递归
# 列表形式: O(3^n)的时间复杂度，n=len(digits)
class Solution:  # 战胜了81.75%
    def letterCombinations(self, digits: str) -> list:
        l = len(digits)
        letters = [' ', '*', 'abc', 'def', 'ghi','jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

        if l == 1:  # 当递归到digits只有一个数字时，这是一个递归的终结者
            return list(letters[int(digits)])
        elif l == 0:
            return []
        res = []
        for i in list(letters[int(digits[0])]):
            # for j in self.letterCombinations(digits[1:]):                
            #     res.append(i + j)
            res.extend([i+j for j in self.letterCombinations(digits[1:])])
        return res

class Solution:  # 字典形式：算法与上面一致，战胜了81.75%
    def letterCombinations(self, digits: str) -> List[str]:
        num_str = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
        if len(digits) == 0:
            return []
        if len(digits) == 1:  # 当递归到digits只有一个数字时，这是一个递归的终结者
            return list(num_str[digits[0]])
        res = []
        res_after = self.letterCombinations(digits[1:])
        for i in num_str[digits[0]]:
          res.extend([i+j for j in res_after])
        return res

# 非递归形式：时间复杂度与递归形式一样,战胜了81.75%
class Solution:
    def letterCombinations(self, digits: str) -> list:
        if not digits:
            return []
        num_str = {"2":"abc","3":"def","4":"ghi","5":"jkl",
                   "6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
        res = [i for i in num_str[digits[0]]]
        for i in digits[1:]:
            res = [m+n for m in res for n in num_str[i]]
        return res

# leetcode-46:
# 递归(回溯法）：战胜了72.70%
class Solution:
    def __init__(self):
        self.res = []  # 定义类中的全局变量res，
    
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.permutation_recursion([], nums)
        return self.res
       
    def permutation_recursion(self, result, nums):  # 真正的功能实现函数，在此函数中定义res不容易在外部调用
        if (len(nums)==0):
            self.res.append(result)
        for i in range(len(nums)):
            self.permutation_recursion(result+[nums[i]], nums[0:i]+nums[i+1:])  # nums[0:i]+nums[i+1:] = nums - nums[i]

# 非递归方式：战胜了92.28%
class Solution:
  def permute(self, nums: List[int]) -> List[List[int]]:
      perms = [[]]   
      for n in nums:
          new_perms = []
          for perm in perms:
              for i in range(len(perm)+1):   
                  new_perms.append(perm[:i] + [n] + perm[i:])   # insert n
          perms = new_perms
      return perms

# leetcode-131：
# 递归(回溯法): 战胜了55.15%
class Solution(object):
    def partition(self, s):
        self.isPalindrome = lambda s : s == s[::-1]
        res = []
        self.helper(s, res, [])
        return res
        
    def helper(self, s, res, path):
        if not s:
            res.append(path)
            return
        for i in range(1, len(s) + 1):
            if self.isPalindrome(s[:i]):
                self.helper(s[i:], res, path + [s[:i]])

# 递归：战胜了26.86%
def partition(self, s: str) -> List[List[str]]:
        if len(s)==1:return [[s]]
        array=[]
        for i in range(1,len(s)+1):
            s_sub,item = s[0:i],[]
            if s_sub == s_sub[::-1]:
                item.append(s_sub)
                if s_sub != s:
                    item2 = self.partition(s[i:len(s)+1])
                    if len(item2):
                        for j in item2:
                            if len(''.join(item + j)) == len(s):
                                array.append(item + j)
                else:
                    array.append(item)
        return array

# leetcode-132：
# 动态规划：战胜了81.88%
class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        dp = [i - 1 for i in range(0, n + 1)] # dp[i]: the minimum cuts needed for s[:i]
        for i in range(0, n + 1):
            j = 0
            while i - j >= 0 and i + j < n and s[i + j] == s[i - j]:
                dp[i + j + 1] = min(dp[i + j + 1], dp[i - j] + 1)
                j += 1
            j = 1
            while i - j + 1 >= 0 and i + j < n and s[i - j + 1] == s[i + j]:
                dp[i + j + 1] = min(dp[i + j + 1], dp[i - j + 1] + 1)
                j += 1
        return dp[n] 

# 战胜了43.38%        
class Solution(object):
    def minCut(self, s):
        size = len(s)
        ans = [i for i in range(size)]
        p = [[False for i in range(size)] for j in range(size)]
        j = 1
        while j < size:
            i,ans[j] = j - 1,min(ans[j],ans[j - 1] + 1) 
            p[j][j] = True
            while i >= 0:
                if s[i] == s[j] and ((j - i) < 2 or  p[i+1][j-1]):
                    p[i][j] = True
                    if i == 0:
                        ans[j] = 0
                    else:
                        ans[j] = min(ans[j],ans[i - 1] + 1)
                i -= 1
            j += 1
        return ans[size - 1]

# leetcode-198:
# 动态规划一：时间复杂度为O(n),空间复杂度为O(1), 战胜了80.6%
class Solution:
    def rob(self, nums: List[int]) -> int:
        yes, no = 0, 0
        for i in nums:
            no, yes = max(no, yes), no+i
        return max(no, yes)

# 动态规划二：战胜了18.44%，与上面的差异仅在于语句：last, now = 0, 0
class Solution:
    def rob(self, nums: List[int]) -> int:
        last = now = 0  # 将这句改为：last, now = 0, 0后，战胜了80.6%
        for i in nums:
            last, now = now, max(last+i, now)
        return now