专栏首页MiningAlgorithmsPython3刷题系列(六)

Python3刷题系列(六)

目录:

一、递归:

1,leetcode-70

2,leetcode-17

3,leetcode-46

二、动态规划:

1,leetcode-131

2,leetcode-132

3,leetcode-198

一、递归:

1,leetcode-70. Climbing Stairs:

https://leetcode.com/problems/climbing-stairs/

# 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)

2,leetcode-17. Letter Combinations of a Phone Number:

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

# 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

3,leetcode-46. Permutations:

https://leetcode.com/problems/permutations/

# 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

二、动态规划:

1,leetcode-131. Palindrome Partitioning:

https://leetcode.com/problems/palindrome-partitioning/

# 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

2,leetcode-132. Palindrome Partitioning II:

https://leetcode.com/problems/palindrome-partitioning-ii/

# 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]

3,leetcode-198. House Robber:

https://leetcode.com/problems/house-robber/

# 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

本文分享自微信公众号 - MiningAlgorithms(gh_d0cc50d1ed34)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 利用java自带的MD5加密

    使用混淆的字符串是:{'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}

    用户5640963
  • nginx proxy_set_header设置、自定义header

    允许重新定义或者添加发往后端服务器的请求头。value可以包含文本、变量或者它们的组合。 当且仅当当前配置级别中没有定义proxy_set_header指令时,...

    用户5640963
  • 002.DNS-BIND简介

    Bind是Berkeley Internet Name Domain Service的简写,它是一款实现DNS服务器的开放源码软件。已经成为世界上使用最为广泛的...

    木二
  • c# 利用AForge.NET组件操作摄像头

    private FilterInfoCollection videoDevices;

    用户5640963
  • Liunx命令行:vi详解

    进入vi的命令 vi filename :打开或新建文件,并将光标置于第一行首 vi +n filename :打开文件,并将光标置于第n行首 vi + ...

    用户5640963
  • springmvc整合axis2 过程

    项目需要使用springmvc发布一个对外的服务,原来使用spring+cxf的结合,使用axis2的客户端调用,没有任何问题,但是使用pb9的客户端调用,一直...

    用户5640963
  • 001.常见监控简介

    主动模式:客户端主动上报数据到服务器端,对服务器的开销较小,适合大规模的监控环境。

    木二
  • 002.NFS相关配置项

    <输出目录> [客户端1 选项(访问权限,用户映射,其他)] [客户端2 选项(访问权限,用户映射,其他)]

    木二
  • linux应用之wget命令详解

    wget是linux最常用的下载命令, 一般的使用方法是: wget + 空格 + 要下载文件的url路径

    用户5640963
  • NGINX 配置文件 fastcgi_pass

    语法:fastcgi_pass fastcgi-server 默认值:none 使用字段:http, server, location 指定FastCGI...

    用户5640963

扫码关注云+社区

领取腾讯云代金券