coding刷题总结-深度优先搜索类型题目-使用python语言-由易到难，梯度设置合理

1. 本文整理了Lintcode深度优先搜索类型题目的coding练习，参考了九章算法课程的配套习题，题目顺序由易到难，非常典型。算法入门的同学可以按照这个题目顺序进行练习。

2. 代码都是用python实现，基本上是参考了九章用的解法，如果发现有错误或者不理解的地方，可以留言告诉我。

3. 体会：

4. 目前在持续更新中
   

   题目目录

   • 17 · 子集
   • • 二刷
     • 三刷
   • 18 · 子集 II
   • • 二刷，没能独立做出来
     • 三刷，需要再刷一次
   • 15 · 全排列
   • • 二刷，没能独立做出来
     • 三刷，掌握的不错
   • 16 · 带重复元素的排列
   • • 二刷，没能独立做出来
     • 三刷，基本掌握，但是对于怎么不跳过取还不是很熟练
   • 10 · 字符串的不同排列
   • • 二刷，独立完成
   • 33 · N皇后问题
   • 34 · N皇后问题 II
   • 153 · 数字组合 II
   • • 二刷
     • 三刷，递归提前结束来优化时间复杂度
   • 135 · 数字组合
   • • 二刷
   • 680 · 分割字符串
   • • 二刷，基本可以独立完成
   • 力扣 · 剑指 Offer 46. 把数字翻译成字符串
   • • 二刷，这个用动规似乎更好
   • 136 · 分割回文串
   • • 二刷
   • 152 · 组合
   • • 二刷
   • 196 · 寻找缺失的数
   • • 二刷，80分
   • 425 · 电话号码的字母组合
   • • 二刷，70fe
     • 三刷，不如一刷的代码好，70分
   • 123 · 单词搜索
   • • 二刷，40分
     • 三刷，60分
   • 652 · 因式分解
   • • 二刷，掌握的一般
   • 570 · 寻找丢失的数 II
   • • 二刷，需要三刷
   • 107 · 单词拆分 I
   • • 二刷，掌握的不好
     • 三刷，记忆化搜索掌握的不好
   • 108 · 分割回文串 II
   • 683 · 单词拆分 III
   • 52 · 下一个排列
   • • 二刷，60分
   • 51 · 上一个排列
   • • 二刷，50分
   • 197 · 排列序号
   • • 二刷，70分
   • 198 · 排列序号II
   • • 二刷，50分
   • 426 · 恢复IP地址
   • • 二刷，60分

17 · 子集

给定一个含不同整数的集合，返回其所有的子集。
子集中的元素不能以降序排列，解集不能包含重复的子集。

class Solution:"""@param nums: A set of numbers@return: A list of lists"""def subsets(self, nums):# write your code here# 典型的组合问题，从nums中选数来构造数组# 基本可以理解答案，自己尝试实现一下nums.sort()  # 题目要求子集中的元素不能以降序排列result = []tmp = []pos = 0self.dfs(nums, pos, tmp, result)return resultdef dfs(self, nums, pos, tmp, result):result.append(tmp[:])for i in range(pos, len(nums)):tmp.append(nums[i])self.dfs(nums, i + 1, tmp, result)tmp.pop()

二刷

思路和代码和一刷一样，没有一次写出来，还需要再整理一下这个代码。

三刷

没有思路了，也基本忘记了代码模板。对于递归和深度优先搜索理解的还很不够。再多加练习，加深理解。

18 · 子集 II

给定一个可能具有重复数字的列表，返回其所有可能的子集。
子集中的每个元素都是非降序的
两个子集间的顺序是无关紧要的
解集中不能包含重复子集

class Solution:"""@param nums: A set of numbers.@return: A list of lists. All valid subsets."""def subsetsWithDup(self, nums):# write your code here# 这个题目就是nums中有重复元素了，但是要求不能有重复的子集# 也就是说nums是[1, 2(1), 2(2), 2(3)], 但是子集[1, 2(1)]、[1, 2(2)]是一样的# 我们只关心取了多少个2，不关心取哪几个# 那就规定必须从第一个2开始连续取（作为重复集合中的代表）# 即必须是[1, 2(1)]不能是[1, 2(2)]# 自己尝试代码实现一下nums.sort()  result = []tmp = []pos = 0self.dfs(nums, pos, tmp, result)return resultdef dfs(self, nums, pos, tmp, result):result.append(tmp[:])for i in range(pos, len(nums)):# 如果i等于pos意味着接着上一个位置在取，上一个位置取过了，不会跳过重复的元素# 如果i不等于pos，并且nums[i]和它前面的数相等，说明跳过了，不是连续取，continueif i != pos and nums[i] == nums[i -1]: continuetmp.append(nums[i])self.dfs(nums, i + 1, tmp, result)tmp.pop()

二刷，没能独立做出来

三刷，需要再刷一次

class Solution:"""@param nums: A set of numbers.@return: A list of lists. All valid subsets."""def subsetsWithDup(self, nums):# write your code herenums.sort()tmp = []res = []index = 0used = [False] * len(nums)self.dfs(nums, index, tmp, used, res)return res def dfs(self, nums, index, tmp, used, res):res.append(tmp[:])if index == len(nums):return for i in range(index, len(nums)):if i != 0 and nums[i] == nums[i - 1] and used[i - 1] == False:continue tmp.append(nums[i])used[i] = Trueself.dfs(nums, i + 1, tmp, used, res)tmp.pop()used[i] = False

15 · 全排列

给定一个数字列表，返回其所有可能的排列。
你可以假设没有重复数字。

class Solution:"""@param: nums: A list of integers.@return: A list of permutations."""def permute(self, nums):# write your code here# 排列问题似乎比组合问题要容易入门一些# 也是适合用递归来做，自己尝试做一下tmp = []result = []visited = set()self.dfs(nums, tmp, visited, result)return resultdef dfs(self, nums, tmp, visited, result):if len(tmp) == len(nums):result.append(tmp[:])returnfor i in range(len(nums)):if nums[i] in visited:continuetmp.append(nums[i])visited.add(nums[i])self.dfs(nums, tmp, visited, result)tmp.pop()visited.remove(nums[i])

二刷，没能独立做出来

三刷，掌握的不错

16 · 带重复元素的排列

给出一个具有重复数字的列表，找出列表所有不同的排列。

class Solution:"""@param: :  A list of integers@return: A list of unique permutations"""def permuteUnique(self, nums):# write your code here# 考虑nums中有重复的元素，先排列，将重复元素放一块# 也规定重复元素必须从第一个开始取，即按照顺序取# 不能跳过前面和我一样的数nums.sort()tmp = []result = []visited = [False] * len(nums)self.dfs(nums, tmp, visited, result)return resultdef dfs(self, nums, tmp, visited, result):if len(tmp) == len(nums):result.append(tmp[:])return for i in range(len(nums)):if visited[i] or (i > 0 and nums[i] == nums[i - 1] and visited[i - 1] == False):continuetmp.append(nums[i])visited[i] = Trueself.dfs(nums, tmp, visited, result)tmp.pop()visited[i] = False         

二刷，没能独立做出来

三刷，基本掌握，但是对于怎么不跳过取还不是很熟练

10 · 字符串的不同排列

给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次。

class Solution:"""@param str: A string@return: all permutations"""def stringPermutation2(self, str):# write your code here# 这个看着和重复数字的排列类似，先排序# 规定必须从第一个字母开始取，s = list(str)s.sort()tmp = []result = []visited = [False] * len(s)self.dfs(s, tmp, visited, result)return resultdef dfs(self, s, tmp, visited, result):if len(tmp) == len(s):result.append("".join(tmp[:]))return for i in range(len(s)):if visited[i] or (i > 0 and s[i] == s[i - 1] and visited[i - 1] == False):continuetmp.append(s[i])visited[i] = Trueself.dfs(s, tmp, visited, result)tmp.pop()visited[i] = False

二刷，独立完成

33 · N皇后问题

n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击(任意两个皇后不能位于同一行，同一列，同一斜线)。
给定一个整数n，返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。

这个题目需要反复多做几次

class Solution:"""@param: n: The number of queens@return: All distinct solutions"""def solveNQueens(self, n):# write your code here# 看了答案也不能理解，看了视频讲解才稍稍理解# 将题目转化成一个0 1 2 3的全排列问题，# 然后看全排列是否满足题目要求# 然后把满足题目要求的全排列放置“Q”和“.”result = []cols = []self.search(n, cols, result)return resultdef search(self, n, cols, result):rows = len(cols)if rows == n:result.append(self.drawChessboard(cols))returnfor col in range(n):if not self.isValid(cols, col, rows):continuecols.append(col)self.search(n, cols, result)cols.pop()def isValid(self, cols, col, rows):# 判断即将放置的col和前面的皇后是否同一行、同一列、同一斜线for r, c in enumerate(cols):if c == col:return False  # 在同一列了if rows - col == r - c:return False  # 在左上右下斜线if rows + col == r + c:return False  # 在右上左下斜线return Truedef drawChessboard(self, cols):n = len(cols)board = []for r in range(n):row = []for c in range(n):if cols[r] == c:row.append("Q")else:row.append(".")board.append("".join(row))return board

34 · N皇后问题 II

根据n皇后问题，现在返回n皇后不同的解决方案的数量而不是具体的放置布局。

class Solution:"""@param n: The number of queens.@return: The total number of distinct solutions."""def totalNQueens(self, n):# write your code here# 仍然可以用DFS找到所有的方案，然后看一共多少个self.total = 0tmp = []self.search(n, tmp)return self.totaldef search(self, n, tmp):rows = len(tmp)if rows == n:self.total += 1return for i in range(n):if self.attack(tmp, i):continuetmp.append(i)self.search(n, tmp)tmp.pop()def attack(self, tmp, col):for r, c in enumerate(tmp):if c == col:return Trueif r + c == len(tmp) + col:return Trueif r - c == len(tmp) - col:return Truereturn False 

153 · 数字组合 II

给定一个数组 num 和一个整数 target. 找到 num 中所有的数字之和为 target 的组合.
在同一个组合中, num 中的每一个数字仅能被使用一次.
所有数值 (包括 target ) 都是正整数.
返回的每一个组合内的数字必须是非降序的.
返回的所有组合之间可以是任意顺序.
解集不能包含重复的组合.

class Solution:"""@param num: Given the candidate numbers@param target: Given the target number@return: All the combinations that sum to target"""def combinationSum2(self, num, target):# write your code here# num中可能有重复的元素，但是解集中不能有重复的组合# 规定重复的元素必须从第一个开始取if sum(num) < target:return []num.sort()tmp = []result = []pos = 0self.dfs(num, target, pos, tmp, result)return resultdef dfs(self, num, target, pos, tmp, result):if sum(tmp) == target:result.append(tmp[:])returnif sum(tmp) > target:returnfor i in range(pos, len(num)):# 如果i不等于pos，说明不是从第一个元素开始取的，并且还和前一个数相等的话# 不是连续取的if i != pos and num[i] == num[i - 1]:continuetmp.append(num[i])self.dfs(num, target, i + 1, tmp, result)tmp.pop()

二刷

class Solution:"""@param num: Given the candidate numbers@param target: Given the target number@return: All the combinations that sum to target"""def combinationSum2(self, num, target):# write your code here# 组合或者子集类问题# 因为有重复的数字，规定重复的数字只能从第一个数开始取，num.sort()tmp = []result = []pos = 0tmp_sum = 0self.dfs(num, target, pos, tmp, tmp_sum, result)return resultdef dfs(self, num, target, pos, tmp, tmp_sum, result):if tmp_sum == target:result.append(tmp[:])return if tmp_sum > target:return for i in range(pos, len(num)):if i != pos and num[i] == num[i - 1]:continuetmp.append(num[i])tmp_sum += num[i]self.dfs(num, target, i + 1, tmp, tmp_sum, result)tmp.pop()tmp_sum -= num[i]

三刷，递归提前结束来优化时间复杂度

135 · 数字组合

给定一个候选数字的集合 candidates 和一个目标值 target. 找到 candidates 中所有的和为 target 的组合.
在同一个组合中, candidates 中的某个数字不限次数地出现.
所有数值 (包括 target ) 都是正整数.
返回的每一个组合内的数字必须是非降序的.
返回的所有组合之间可以是任意顺序.
解集不能包含重复的组合.

class Solution:"""@param candidates: A list of integers@param target: An integer@return: A list of lists of integers"""def combinationSum(self, candidates, target):# write your code here# 同一个组合中，某个数字可以不限次数的出现# 是不是意味着不需要pos这个参数了呢?candidates.sort()tmp = []result = []pos = 0self.dfs(candidates, target, pos, tmp, result)return resultdef dfs(self, candidates, target, pos, tmp, result):if sum(tmp) == target:result.append(tmp[:])return if sum(tmp) > target:returnfor i in range(pos, len(candidates)):if i != pos and candidates[i] == candidates[i - 1]:continuetmp.append(candidates[i])self.dfs(candidates, target, i, tmp, result)tmp.pop()

二刷

题目稍微修改了一下，就不会做了。。。

680 · 分割字符串

给一个字符串,你可以选择在一个字符或两个相邻字符之后拆分字符串,使字符串由仅一个字符或两个字符组成,输出所有可能的结果

class Solution:"""@param: : a string to be split@return: all possible split string array"""def splitString(self, s):# write your code here# 不会做，也不太理解答案# 大概思路就是每次拆分掉一个字符或者两个字符，存到path中# 当整个字符串拆分完毕，即字符串为空时，将path存到result中# 虽然要所有可能的结果这类题目不适合用动规，但是依然有点动规的思想# 第一步有拆分掉一个字符或者两个字符两种选择，剩下的字符串也是有两种选择# 自己根据答案尝试实现一下if len(s) == 0:return [[]]result = []path = []self.dfs(s, result, path)return resultdef dfs(self, s, result, path):if len(s) == 0:result.append(path[:])  # 用[:]来克隆列表return # 拆分掉一个字符或者两个字符两个选择for i in range(2):if i + 1 <= len(s):path.append(s[:i + 1])self.dfs(s[i + 1:], result, path)path.pop()  # 去掉列表中最后一个元素。不是特别能理解

二刷，基本可以独立完成

力扣 · 剑指 Offer 46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

class Solution:def translateNum(self, num: int) -> int:# 字符串分割题目，子串是0到25，s = str(num)res = []tmp = []self.dfs(s, tmp, res)return len(res)def dfs(self, s, tmp, res):if s == '':res.append(tmp[:])return for i in range(1, 3):if i <= len(s):substr = s[:i]if int(substr) > 25 or (len(substr) == 2 and substr[0] == '0'):continue tmp.append(substr)self.dfs(s[i:], tmp, res)tmp.pop() 

二刷，这个用动规似乎更好

class Solution:def translateNum(self, num: int) -> int:# 字符串分割题目，子串是0到25，#     s = str(num)#     res = []#     tmp = []#     self.dfs(s, tmp, res)#     return len(res)# def dfs(self, s, tmp, res):#     if s == '':#         res.append(tmp[:])#         return #     for i in range(1, 3):#         if i <= len(s):#             substr = s[:i]#             if int(substr) > 25 or (len(substr) == 2 and substr[0] == '0'):#                 continue #             tmp.append(substr)#             self.dfs(s[i:], tmp, res)#             tmp.pop() # 是不是用动规更好呢？# dp[i]表示前i个字符的翻译方法，dp[i+1] = max(dp[i], dp[i]+dp[i-1] i和i+1字符可以被翻译)s = str(num)n = len(s)dp = [0] * n dp[0] = 1if n >= 2:if s[0] != '0' and int(s[:2]) <= 25:dp[1] = 2else:dp[1] = 1for i in range(2, n):if s[i - 1] != '0' and int(s[i - 1: i + 1]) <= 25:dp[i] = dp[i - 1] + dp[i - 2]else:dp[i] = dp[i - 1]return dp[n - 1]

##三刷，尝试把空间复杂度优化到O(1)

136 · 分割回文串

给定字符串 s, 需要将它分割成一些子串, 使得每个子串都是回文串.
返回所有可能的分割方案.
不同的方案之间的顺序可以是任意的.
一种分割方案中的每个子串都必须是 s 中连续的一段.

class Solution:"""@param: s: A string@return: A list of lists of string"""def partition(self, s):# write your code here# 真的不会做，刚开始练习DFS，也不太能理解答案# 想不明白递归result = []tmp = []self.dfs(s, tmp, result)return resultdef dfs(self, s, tmp, result):if s == "":result.append(tmp[:])returnfor i in range(0, len(s)):if self.isPalindrome(s[:i + 1]):tmp.append(s[:i + 1])self.dfs(s[i + 1:], tmp, result)tmp.pop()def isPalindrome(self, s):if s == s[::-1]:return Truereturn False

二刷

思路清晰，基本掌握了dfs的思维方式

152 · 组合

给定两个整数 n 和 k. 返回从 1, 2, … , n 中选出 k 个数的所有可能的组合.
你可以以任意顺序返回所有的组合, 但是一个组合内的所有数字需要是升序排列的.

class Solution:"""@param n: Given the range of numbers@param k: Given the numbers of combinations@return: All the combinations of k numbers out of 1..n"""def combine(self, n, k):# write your code here# 不会做，基本可以理解答案# 自己尝试实现一下self.result = []tmp = []count = 0idx = 1self.dfs(n, k, idx, count, tmp)return self.resultdef dfs(self, n, k, idx, count, tmp):if count == k:self.result.append(tmp[:])return for i in range(idx, n + 1):tmp.append(i)self.dfs(n, k, i + 1, count + 1, tmp)tmp.pop()

二刷

思路清晰，基本掌握了dfs的思维方式

class Solution:"""@param n: Given the range of numbers@param k: Given the numbers of combinations@return: All the combinations of k numbers out of 1..n"""def combine(self, n, k):# write your code here# 也是比较清晰的dfs题目tmp = []res = []pos = 1self.dfs(n, k, pos, tmp, res)return res def dfs(self, n, k, pos, tmp, res):if k == 0:res.append(tmp[:])return for i in range(pos, n + 1):tmp.append(i)k -= 1self.dfs(n, k, i + 1, tmp, res)tmp.pop()k += 1

196 · 寻找缺失的数

给出一个包含 0 … N 中 N 个数的序列，找出0 … N 中没有出现在序列中的那个数。
挑战
在数组上原地完成，使用O(1)的额外空间和O(N)的时间。

class Solution:"""@param nums: An array of integers@return: An integer"""def findMissing(self, nums):# write your code here# 要求原地完成，时间复杂度是O(n)# 遍历数组，把每一个数放在正确的位置上i = 0while i < len(nums):while nums[i] != i and nums[i] < len(nums):tmp = nums[i]nums[i] = nums[tmp]nums[tmp] = tmpi += 1for i in range(len(nums)):if nums[i] != i:return ireturn len(nums)

二刷，80分

425 · 电话号码的字母组合

给一个不包含0和1的数字字符串，每个数字代表一个字母，请返回其所有可能的字母组合。

下图的手机按键图，就表示了每个数字可以代表的字母。

以上的答案是按照词典编撰顺序进行输出的，不过，在做本题时，你也可以任意选择你喜欢的输出顺序。

KEYBOARD = {'2': 'abc','3': 'def','4': 'ghi','5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
class Solution:"""@param digits: A digital string@return: all posible letter combinations"""def letterCombinations(self, digits):# write your code hereif not digits:return []tmp = []result = []index = 0self.dfs(digits, tmp, index, result)return resultdef dfs(self, digits, tmp, index, result):if index == len(digits):result.append("".join(tmp))returnfor char in KEYBOARD[digits[index]]:tmp.append(char)self.dfs(digits, tmp, index + 1, result)tmp.pop()

二刷，70fe

三刷，不如一刷的代码好，70分

digit2char = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
class Solution:"""@param digits: A digital string@return: all posible letter combinations"""def letterCombinations(self, digits):# write your code hereif len(digits) == 0:return []tmp = []res = []index = 0self.dfs(digits, index, tmp, res)return resdef dfs(self, digits, index, tmp, res):if index == len(digits) and len(tmp) == len(digits):res.append(''.join(tmp[:]))return for i in range(index, len(digits)):for char in digit2char[digits[i]]:tmp.append(char)self.dfs(digits, i + 1, tmp, res)tmp.pop()

123 · 单词搜索

给出一个二维的字母板和一个字符串单词，寻找字母板网格中是否存在这个字符串单词。
字符串单词可以由按顺序的相邻单元的字母组成，其中相邻单元指的是水平或者垂直方向相邻。每个单元中的字母最多只能使用一次。

class Solution:"""@param board: A list of lists of character@param word: A string@return: A boolean"""def exist(self, board, word):# write your code here# 不会做，看答案是遍历board中的每个字母# 看从这个字母开始，能否找到所给的单词# 采用的方法也是DFS，不知道这个能不能用BFS或者动规来做m = len(board)n = len(board[0])visited = [[False for col in range(n)] for row in range(m)]for i in range(m):for j in range(n):if self.exist2(board, word, visited, i, j):return Truereturn Falsedef exist2(self, board, word, visited, row, col):if word == "":return Truem, n = len(board), len(board[0])if row >= m or row < 0 or col >= n or col < 0:return Falseif board[row][col] == word[0] and visited[row][col] == False:visited[row][col] = Trueif self.exist2(board, word[1:], visited, row - 1, col) \or self.exist2(board, word[1:], visited, row + 1, col) \or self.exist2(board, word[1:], visited, row, col - 1) \or self.exist2(board, word[1:], visited, row, col + 1):return Trueelse:visited[row][col] = Falsereturn False 

二刷，40分

class Solution:"""@param board: A list of lists of character@param word: A string@return: A boolean"""def exist(self, board, word):# write your code herem, n = len(board), len(board[0])used = [[False] * n for _ in range(m)]index = 0for i in range(m):for j in range(n):# 从i, j开始，看能否找到该字符串if self.exist2(board, word, i, j, index, used):return True return False def exist2(self, board, word, row, col, index, used):m, n = len(board), len(board[0])if index == len(word):return True directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]# 先判断row,cl否效以是if self.isValid(board, row, col, index, word, used):used[row][col] = True for dx, dy in directions:row_, col_ = row + dx, col + dyif self.exist2(board, word, row_, col_, index + 1, used):return True else:used[row][col] = False return False def isValid(self, board, row, col, index, word, used):m, n = len(board), len(board[0])if 0 <= row < m and 0 <= col < n and board[row][col] == word[index] and not used[row][col]:return True return False 

三刷，60分

class Solution:"""@param board: A list of lists of character@param word: A string@return: A boolean"""def exist(self, board, word):if len(board) == 0:return False m, n = len(board), len(board[0])visited = [[False] * n for _ in range(m)]for i in range(m):for j in range(n):if board[i][j] == word[0]:visited[i][j] = True if self.dfs(board, word[1:], i, j, visited):return True visited[i][j] = False return False def dfs(self, board, word, row, col, visited):m, n = len(board), len(board[0])if word == '':return True directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]for dx, dy in directions:x, y = dx + row, dy + col if 0 <= x < m and 0 <= y < n and board[x][y] == word[0] and visited[x][y] == False:visited[x][y] = True if self.dfs(board, word[1:], x, y, visited):return True visited[x][y] = False  # 开始写的==，搞了半天才发现错误在哪里return False 

652 · 因式分解

一个非负数可以被视为其因数的乘积。编写一个函数来返回整数 n 的因数所有可能组合。
组合中的元素(a1,a2,…,ak)必须是非降序。(即，a1≤a2≤…≤ak)。
结果集中不能包含重复的组合。

class Solution:"""@param n: An integer@return: a list of combination"""def getFactors(self, n):# write your code here# 这个题目看了很多遍了，每次都是看看后又放下# 今天终于不太抗拒，尝试完成一下# 其实思路就是不断地分解ntmp = []result = []start = 2self.dfs(n, tmp, start, result)return resultdef dfs(self, n, tmp, start, result):if n == 1:if len(tmp) > 1:result.append(tmp[:])return import mathfor i in range(start, int(math.sqrt(n)) + 1):if n % i == 0:tmp.append(i)self.dfs(n // i, tmp, i, result)tmp.pop()if n >= start:tmp.append(n)self.dfs(1, tmp, n, result)tmp.pop()

二刷，掌握的一般

没理解透彻为什么有if n >= start，为什么i是start到math.sqrt(n) + 1

class Solution:"""@param n: An integer@return: a list of combination"""def getFactors(self, n):# write your code heretmp = []res = []start = 2self.dfs(n, start, tmp, res)return res def dfs(self, n, start, tmp, res):if n == 1:if len(tmp) > 1:res.append(tmp[:])return for i in range(start, int(math.sqrt(n)) + 1): # 注意这里要加1if n % i == 0:tmp.append(i)self.dfs(n // i, i, tmp, res)tmp.pop()if n >= start:tmp.append(n)self.dfs(1, n, tmp, res)tmp.pop() 

570 · 寻找丢失的数 II

给一个由 1 - n 的整数随机组成的一个字符串序列，其中丢失了一个整数，请找到它。
n < 100
数据保证有且仅有唯一解
如果您找到的答案列表丢失了多个数字，可能是您没有找到正确的字符串拆分方式

class Solution:"""@param n: An integer@param str: a string with number from 1-n in random order and miss one number@return: An integer"""def findMissing2(self, n, str):# write your code here# 看了很多次这个题目，每次都是抗拒，然后放下# 今天尝试做一做# 因为n < 100，所以是一位数或者两位数# 那么就每次取一个数或者两个数来拆分字符串# 把1-n没找到的给记下来index = 0used = [False] * (n + 1)return self.dfs(n, str, index, used)def dfs(self, n, str, index, used):if index == len(str):result = []for i in range(1, n + 1):if used[i]:continueresult.append(i)return result[0] if len(result) == 1 else -1if str[index] == '0':return -1for i in range(1, 3):num = int(str[index:(index + i)])if num >= 1 and num <= n and not used[num]:used[num] = Truetarget = self.dfs(n, str, index + i, used)if target != -1:return targetused[num] = Falsereturn -1

二刷，需要三刷

class Solution:"""@param n: An integer@param str: a string with number from 1-n in random order and miss one number@return: An integer"""def findMissing2(self, n, str):# write your code heretmp = set()result = []index = 0return self.dfs(n, str, index, tmp, result)def dfs(self, n, str, index, tmp, result):if index >= len(str):if len(tmp) == n - 1:return (n + 1) * n // 2 - sum(tmp)return -1if str[index] == '0':return -1for i in range(1, 3):if index + i <= len(str):num = int(str[index:index + i])if 0 <= num <= n and num not in tmp:tmp.add(num)target = self.dfs(n, str, index + i, tmp, result)if target != -1:return targettmp.remove(num)return -1

107 · 单词拆分 I

Given a string s and a dictionary of words dict, determine if s can be broken into a space-separated sequence of one or more dictionary words.
Because we have used stronger data, the ordinary DFS method can not pass this question now.
s.length <= 1e5
dict.size <= 1e5

采用普通DFS会time　limit　exceeded，但是也把代码记录如下。递归的时间复杂度一般是指数级的。

class Solution:"""@param s: A string@param wordSet: A dictionary of words dict@return: A boolean"""def wordBreak(self, s, wordSet):# write your code here# 虽然题目已经说了普通DFS不能通过，因为使用了更强大的数据# 但是还是先练习一下# 看s的前缀是不是在字典中，在的话，递归看后面的是不是在index = 0return self.dfs(s, index, wordSet)def dfs(self, s, index, wordSet):if s in wordSet:return Trueif index == len(s):return Truefor i in range(len(s)):if index + i > len(s):breakprefix = s[index:index + i]if prefix not in wordSet:continueif self.dfs(s, index + i, wordSet):return Truereturn False

可以想到的优化方法是采用记忆化搜索，其实最有的解法是动规，先尝试实现记忆化搜索。
记忆化搜索也是会超时

class Solution:"""@param s: A string@param wordSet: A dictionary of words dict@return: A boolean"""def wordBreak(self, s, wordSet):# write your code here# 普通DFS会超时，采用记忆化搜索优化看看# 其实不太会记忆化搜索，尝试实现看看# 记忆化搜索就是把搜索到的结果存起来，# 下次搜索时先看看是不是搜索过了，不必重复搜索if s == '':return Trueif len(wordSet) == 0 or wordSet == []:return Falseindex = 0memo = {}maxlength = max(len(word) for word in wordSet)return self.memo_dfs(s, index, memo, wordSet, maxlength)def memo_dfs(self, s, index, memo, wordSet, maxlength):if index in memo:return memo[index]if s in wordSet:return Trueif index == len(s):return Truefor i in range(1, maxlength + 1):if index + i > len(s):breakprefix = s[index:index + i]if prefix not in wordSet:continueif self.memo_dfs(s, index + i, memo, wordSet, maxlength):memo[index] = Truereturn Truereturn False

动规

class Solution:"""@param s: A string@param wordSet: A dictionary of words dict@return: A boolean"""def wordBreak(self, s, wordSet):# write your code here# 这个题目就该采用动规，# dp[i]表示前i个字符是否可以被分割# dp[i] = or(dp[j], j < i and s[j:i]在字典中)# 初始化dp[0] = Truedp = [False] * (len(s) + 1)dp[0] = Truefor i in range(1, len(s) + 1):for j in range(i):if dp[j] and s[j:i] in wordSet:dp[i] = Truebreakreturn dp[len(s)] 

二刷，掌握的不好

三刷，记忆化搜索掌握的不好

class Solution:"""@param s: A string@param wordSet: A dictionary of words dict@return: A boolean"""def wordBreak(self, s, wordSet):# write your code hereimport sysmaxwordLen = 0minwordLen = sys.maxsizefor word in wordSet:maxwordLen = max(maxwordLen, len(word))minwordLen = min(minwordLen, len(word))#     return self.dfs(s, wordSet, maxwordLen, minwordLen)# def dfs(self, s, wordSet, maxwordLen, minwordLen):#     if s == '':#         return True #     if len(s) < minwordLen:#         return False #     for i in range(minwordLen, maxwordLen + 1):#         if i <= len(s):#             prefix = s[:i]#             if prefix in wordSet:#                 res = self.dfs(s[i:], wordSet, maxwordLen, minwordLen)#                 if res:#                     return True #     return False # dp[i]表示前i个字符串可以分割# dp[i] = or(dp[j], j-i的字符串在字典中)dp = [False] * (len(s) + 1)dp[0] = True for i in range(1, len(s) + 1):if i <= maxwordLen:for j in range(i):if dp[j] and s[j:i] in wordSet:dp[i] = True break if i > maxwordLen:for j in range(i - maxwordLen, i):if dp[j] and s[j:i] in wordSet:dp[i] = True break return dp[len(s)]

记忆化搜索，没超时，但是超内存了

class Solution:"""@param s: A string@param wordSet: A dictionary of words dict@return: A boolean"""def wordBreak(self, s, wordSet):# write your code hereif s == '':return True if len(wordSet) == 0:return False maxwordLen = max([len(word) for word in wordSet])cannotBreak = set()return self.dfs(s, wordSet, cannotBreak, maxwordLen)def dfs(self, s, wordSet, memo, maxwordLen):if s == '':return True if s in memo:return False for i in range(maxwordLen + 1):if i <= len(s):prefix = s[:i]if prefix in wordSet:if self.dfs(s[i:], wordSet, memo, maxwordLen):return True else:memo.add(s)# else:#     memo.add(s[i:])memo.add(s)return False 

108 · 分割回文串 II

给定字符串 s, 需要将它分割成一些子串, 使得每个子串都是回文串.
最少需要分割几次?

时间复杂度是O(n^2)，但是依然超时了，咋整？

class Solution:"""@param s: A string@return: An integer"""def minCut(self, s):# write your code here# 直接采用动规吧# dp[i]表示前i个字符串需要的最少分割次数# dp[i] = min(dp[j] + 1, s[j:i]是回文串)# 初始化，前i个字符的最大分割次数i - 1dp = []  # dp[0] = -1for i in range(0, len(s) + 1):dp.append(i - 1)palindrome = self.palindromeSet(s)for i in range(1, len(s) + 1):for j in range(i):if s[j:i] in palindrome:dp[i] = min(dp[i], dp[j] + 1)return dp[len(s)]def palindromeSet(self, s):# 运用双指针或者区间型动规的思想palindrome = set()# 长度为偶数的回文串for i in range(len(s) - 1):left, right = i, i + 1while left >= 0 and right <= len(s) - 1 and s[left] == s[right]:palindrome.add(s[left:right + 1])left -= 1right += 1# 长度为奇数的回文串for i in range(len(s)):left, right = i, iwhile left >= 0 and right <= len(s) - 1 and s[left] == s[right]:palindrome.add(s[left:right + 1])left -= 1right += 1return palindrome

683 · 单词拆分 III

给出一个单词表和一条去掉所有空格的句子，根据给出的单词表添加空格, 返回可以构成的句子的数量, 保证构成的句子中所有的单词都可以在单词表中找到.
忽略大小写

不太会用动规，先尝试DFS试试。

class Solution:"""@param s: A string@param dict: A set of word@return: the number of possible sentences."""def wordBreak3(self, s, dict):# Write your code here# 先是尝试了动规，以失败告终# 尝试用DFS试试if len(dict) == 0:return 0self.total = 0index = 0maxlength = max(len(word) for word in dict)new_dict = set()for word in dict:new_dict.add(word.lower())self.dfs(s.lower(), index, new_dict, maxlength)return self.totaldef dfs(self, s, index, new_dict, maxlength):if s in new_dict:return 1if index == len(s):return 1for i in range(1, maxlength + 1):if index + i > len(s):breakprefix = s[index:index + i]if prefix not in new_dict:continueif self.dfs(s, index + i, new_dict, maxlength) == 1:self.total += 1

普通的DFS会超时，尝试记忆化搜索试试。

class Solution:"""@param s: A string@param dict: A set of word@return: the number of possible sentences."""def wordBreak3(self, s, dict):# Write your code here# 显示尝试了动规，以失败告终# 尝试用DFS试试if len(dict) == 0:return 0self.total = 0index = 0maxlength = max(len(word) for word in dict)new_dict = set()for word in dict:new_dict.add(word.lower())memo = {}return self.dfs(s.lower(), index, new_dict, maxlength, memo)# return self.totaldef dfs(self, s, index, new_dict, maxlength, memo):if s in new_dict:return 1if index == len(s):return 1if index in memo:return memo[index]memo[index] = 0for i in range(1, maxlength + 1):if index + i > len(s):breakprefix = s[index:index + i]if prefix not in new_dict:continuememo[index] += self.dfs(s, index + i, new_dict, maxlength, memo)return memo[index]

52 · 下一个排列

给定一个整数数组来表示排列，按升序找出其下一个排列。
排列中可能包含重复的整数

class Solution:"""@param nums: A list of integers@return: A list of integers"""def nextPermutation(self, nums):# write your code here# 理解思路用了好久，还是leetcode上讲的清楚# 下一个排列就是比现在这个排列大一号的排列# 找到左边较小的数，这个数要尽量靠右a[i]，# i+1到n-1是降序的# 找到右边大于a[i]的较大数a[j]，这个数要尽量小# 交换这个两个数，i+1到n-1是降序的，升序排列n = len(nums)for i in range(n - 2, -1, -1):if nums[i] < nums[i + 1]:breakelse:nums.reverse()return numsfor j in range(n - 1, i, -1):if nums[j] > nums[i]:breaknums[i], nums[j] = nums[j], nums[i]left = i + 1right = n - 1while left < right:nums[left], nums[right] = nums[right], nums[left]left += 1right -= 1return nums

二刷，60分

51 · 上一个排列

给定一个整数数组来表示排列，按升序找出其上一个排列。
排列中可能包含重复的整数

class Solution:"""@param: nums: A list of integers@return: A list of integers that's previous permuation"""def previousPermuation(self, nums):# write your code here# 思路和下一个排列类似# 找比当前排列小一号的排列# 找左边一个较大的数a[i]，尽量靠近右边# i+1到n-1是sheng序的# 找右边一个小于a[i]较小的的数，尽量dan = len(nums)for i in range(n - 2, -1, -1):if nums[i] > nums[i + 1]:breakelse:nums.reverse()return numsfor j in range(n - 1, -1, -1):if nums[j] < nums[i]:breaknums[i], nums[j] = nums[j], nums[i]left = i + 1right = n- 1while left < right:nums[left], nums[right] = nums[right], nums[left]left += 1right -= 1return nums

二刷，50分

197 · 排列序号

给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。

class Solution:"""@param A: An array of integers@return: A long integer"""def permutationIndex(self, A):# write your code here# 题目可以转化成比该排列小的排列一共有多少个# 看该排列的每一位，右边比这一位小的数有多少个# 交换位置，右边还可以全排列if len(A) == 0:return 0res = 0import mathfor i in range(len(A)):cnt = self.count(A, i)  # i+1到n- 1中比A[i]小的数的个数res += cnt * math.factorial(len(A) - 1 - i)return res + 1def count(self, A, index):cnt = 0for i in range(index + 1, len(A)):if A[i] < A[index]:cnt += 1return cnt

二刷，70分

198 · 排列序号II

给出一个可能包含重复数字的排列，求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从1开始。

class Solution:"""@param A: An array of integers@return: A long integer"""def permutationIndexII(self, A):# write your code here# 有重复元素，思路和197还是一样的# 区别在于要除以重复元素的阶乘# 实现方式不同，这个的更好if len(A) == 0:return 0counter = {}index, factor, multi_fact = 0, 1, 1for i in range(len(A) - 1, -1, -1):if A[i] in counter:counter[A[i]] += 1else:counter[A[i]] = 1multi_fact *= counter[A[i]]count = 0for j in range(i + 1, len(A)):if A[j] < A[i]:count += 1index += count * factor // multi_factfactor *= (len(A) - i)return index + 1

二刷，50分

426 · 恢复IP地址

给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。
(你的任务就是往这段字符串中添加三个点, 使它成为一个合法的IP地址. 返回所有可能的IP地址.)
你可以以任意顺序返回所有合法的IP地址.

class Solution:"""@param s: the IP string@return: All possible valid IP addresses"""def restoreIpAddresses(self, s):# write your code here# 很容易想到用DFS# IP地址是4段，每段长是1-3，# 每段可以是0但是不能是0开头tmp = ""result = []count = 0self.dfs(s, tmp, count, result)return resultdef dfs(self, s, tmp, count, result):if count == 4:if s == "":result.append(tmp[:-1])return for length in range(1, 4):if length <= len(s):if length > 1 and s[0] == '0':breakif int(s[:length]) <= 255:self.dfs(s[length:], tmp + s[:length] + '.', count + 1, result)

二刷，60分

class Solution:"""@param s: the IP string@return: All possible valid IP addresses"""def restoreIpAddresses(self, s):# write your code here# IP地址在0-255之间，不能以0开头，数字是1-3个tmp = ''result = []count = 0index = 0self.dfs(s, index, tmp, count, result)return result def dfs(self, s, index, tmp, count, result):if count == 4:if index == len(s):result.append(tmp[:-1])return if index == len(s):return for i in range(1, 4):if s[index] == '0':self.dfs(s, index + 1, tmp + s[index] + '.', count + 1, result)breakelif index + i <= len(s) and int(s[index:index + i]) <= 255:self.dfs(s, index + i, tmp + s[index:index + i] + '.', count + 1, result)