leetcode 9.14-9.20

2020-09-17

22 括号生成
46 全排列

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：剪枝，递归。规律是字符串总是以左括号开始，用left表示剩余的左括号数目，right表示剩余的右括号数目，只有当剩余的右括号比左括号多时，字符串才可以append一个右括号。

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ret = []
        def myParenthesis(left, right, s):
            if left == 0 and left == right:
                ret.append(s)

            if left > 0:
                myParenthesis(left - 1, right, s+"(")
            if right > left:
                myParenthesis(left, right - 1, s+")")

        myParenthesis(n-1, n, "(")
        return ret

46. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：递归，n个数字的全排列，是在 n-1个数字全排列的结果里，每个位置插入第n个数字。官方题解是回溯+DFS

AC代码：

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) == 1:
            return [nums]
        if len(nums) == 2:
            return [nums, [nums[1], nums[0]]]
        
        tmp_ret = self.permute(nums[1:])
        ret = []
        for arr in tmp_ret:
            for i in range(len(arr)+1):
                ret.append(arr[0:i] + [nums[0]] + arr[i:])
        return ret
      

# 提交里时间短的，没看懂
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res=[[]]
        for i in range(len(nums)):
            res=[s+[j] for s in res for j in nums if j not in s]
        return res