《热题100》回溯篇

class Solution:

def permuteUnique(self , num: List[int]) -> List[List[int]]:

    n = len(num)

    if n == 0:

        return []

    ans = []

    use = [False]*n

    def dfs(i,path):

        if i == n:

            ans.append(**path.copy())**

            return

        for j in range(n):

            if not use[j]:

                path.append(num[j])

                use[j] = True

                dfs(i+1,path)

                use[j] = False #恢复现场

                path.pop()

    dfs(0,[])

    return ans

class Solution:

def permuteUnique(self , num: List[int]) -> List[List[int]]:

    n = len(num)

    if n == 0:

        return []

    ans = []

    use = [False]*n

    num = sorted(num) #为了最后是升序，先排列再找

    def dfs(i,path):

        if i == n:

            if path not in ans: #防止答案重复

                ans.append(**path.copy())**

            return

        for j in range(n):

            if not use[j]:

                path.append(num[j])

                use[j] = True

                dfs(i+1,path)

                use[j] = False #恢复现场

                path.pop()

    dfs(0,[])

    return ans

思路：遍历二维数组，遇到1之后，就先给答案加1，然后进入递归，将1的上下左右都换成0，避免之后再进入。最后输出答案。

class Solution:

def dfs(self,grid,i,j):

    if i >= len(grid) or i < 0: #判出条件

        return

    if j >= len(grid[0]) or j < 0:

        return

    if grid[i][j] == '1': #修改为'0'

        grid[i][j] = '0'

  **  else:**

** return**

    self.dfs(grid,i-1,j) #探寻上下左右

    self.dfs(grid,i+1,j)

    self.dfs(grid,i,j-1)

    self.dfs(grid,i,j+1)

def solve(self , grid: List[List[str]]) -> int:

    n = len(grid)  #异常判断

    if n <= 0:

        return 0

    m = len(grid[0])

    if m <= 0:

        return 0

   ** ans = 0**

    for i in range(n):

        for j in range(m):

            if grid[i][j] == '1':

                **self.dfs(grid,i,j)**

                **ans += 1**

    return ans

思路：还是按照由相同数字的全排列，但是因为这次的数据量更大，所以需要先排序和剪枝。排序使相同的字母放在一起，如果当前两个字母相等，而且前一个字母已经被用了，那就跳出本次循环。

class Solution:

def Permutation(self , s: str):

    n = len(s)

    if n == 0:

        return []

    ans = []

    use = [False]*n

    **s = sorted(list(s)) #先排列**

    def dfs(i,path):

        if i == n:

            ans.append(''.join(path.copy()))

            return

        for j in range(n):

            if not use[j]:

                **if j > 0 and s[j] == s[j-1] and use[j-1]: #剪枝**

** continue**

                use[j] = True

                path.append(s[j])

                dfs(i+1,path)

                use[j] = False

                path.pop()

    dfs(0,[])

    return ans

思路：单纯的深度递归会超时，因为之前会有大量的数据计算，所以需要一个数组来保存当前的最大递增路径的值。遍历数组，每遇到一个值都计算一次当前的最大递增路径，和答案比较，如果比答案大就更新答案。在遍历当前值时，如果当前dp值不是0，那就说明之前计算过该值，直接返回。否则开始计算，先让dp+1，然后从上下左右四个方向去更新dp。

class Solution:

def path(self,matrix,i,j,dp):

  **  if dp[i][j] != 0:**

** return dp[i][j]**

    **dp[i][j] += 1**

    if i+1 >= 0 and i+1 < len(matrix) and matrix[i+1][j] > matrix[i][j]:

        dp[i][j] = max(**dp[i][j],self.path(matrix,i+1,j,dp)+1**)

    if i-1 >= 0 and i-1 < len(matrix) and matrix[i-1][j] > matrix[i][j]:

        dp[i][j] = max(**dp[i][j],self.path(matrix,i-1,j,dp)+1**)

    if j+1 >= 0 and j+1 < len(matrix[0]) and matrix[i][j+1] > matrix[i][j]:

        dp[i][j] = max(**dp[i][j],self.path(matrix,i,j+1,dp)+1**)

    if j-1 >= 0 and j-1 < len(matrix[0]) and matrix[i][j-1] > matrix[i][j]:

        dp[i][j] = max(**dp[i][j],self.path(matrix,i,j-1,dp)+1**)

    return dp[i][j]

def solve(self , matrix: List[List[int]]) -> int:

    n = len(matrix)

    ans = 0

    if n == 0:

        return 0

    m = len(matrix[0])

    if m == 0:

        return 0

    dp = [[0]*m for _ in range(n)]

    for i in range(n):

        for j in range(m):

            ans = max(ans,self.path(matrix,i,j,dp))

    return ans

思路：每一行每一列都需要放入一个皇后，我们可以递归行号，然后在该行内，找列可以放的位置，如果都不冲突，就可以放入。然后记录列号，继续递归。需要用一个col[]记录每一行放入了哪一列。

class Solution:

def Nqueen(self , n: int) -> int:

    col = [0]*n #下标表示行号，第row行放在了col[row]列

    ans = 0

    def dfs(row,s): #递归下一行和剩下可以取的列

        if row == n:#如果当前找到了最后一行

            nonlocal ans

            ans += 1

            return

       ** for c in s:**#枚举剩下可以取的列

            #对于row之前的每一行，当前的取值row+c都不能等于之前的行号+列号

            #row-c也不能等于之前的行号-列号，才能保证不冲突

          **  if all(row+c != r+col[r] and row-c != r-col[r] for r in range(row)):**

               ** col[row] = c **#如果不冲突，就记录下当前列

                **dfs(row+1,s-{c}) **#继续递归下一行和剩下可以取的列

    **dfs(0,set(range(n)))**#列举列数[0,n-1]

    return ans    

插入一个题：输入几个json，将其中相同的地方合并，然后输出：

输入：

{'name':'hahha','id':123,'sci':'no'}
{'name': 'aaa', 'id': 12, 'sci': 'yes'}
{'name': 'hahha', 'id': 123, 'age': 11}
{'name': 'aaa', 'id': 12, 'age': 44}
{'name': 'bb', 'id': 56, 'age': 45}

输出：

{'name': 'hahha', 'id': 123, 'sci': 'no', 'age': 11}
{'name': 'aaa', 'id': 12, 'sci': 'yes', 'age': 44}
{'name': 'bb', 'id': 56, 'age': 45}

思路：用while true来获得输入的每一行json字符，将其用loads转换为字典。当输入是换行，就跳出循环。比较记录中的每个字典，如果有相同key和value，就合并（d1.update(d2)），然后删除多余的那个字典。用while循环来遍历记录，可以控制移动的下标。

import json

d1 = []

ans = []

while True:

    data = input()

    if data != '':

        res = **json.loads(data.replace("'",'"'))** #单引号会导致loads出错，将单引号换成双引号

        d1.append(res)

    else:

        break

def merge(dict1,dict2): #合并字典

    return (dict1.update(dict2))

i= 0

while i < len(d1)-1: #遍历该字典数组，遇到有相同部分的就合并

    j = i+1

    while j < len(d1):

        if any(d1[i][k] == d1[j][k] for k in d1[i] if k in d1[i] and k in d1[j]):

            merge(d1[i], d1[j])

            d1.remove(d1[j])

        else:

            j += 1

    i += 1

for k in d1:

    print(k)

思路：n对括号相当于在2n个位置上放置左括号和右括号。所以每个位置上都有选左括号和选右括号的可能。当l<n时，当前位置可以选左括号，当r<l时，当前位置也可以选择右括号。

class Solution:

def generateParenthesis(self , n: int) -> List[str]:

    m = n*2

    if m == 0:

        return []

    ans = []

    def dfs(i,path,l,r):

        if i == m:

            ans.append(''.join(path.copy()))

            return

        if l < n: #选左括号

            path.append('(')

            dfs(i+1,path,l+1,r)

            path.pop()

        if r < l: #选右括号

            path.append(')')

            dfs(i+1,path,l,r+1)

            path.pop()

    dfs(0,[],0,0)

    return ans