这道题是一个从 1 到 n 的数组,共有 n! 个全排列序列,找到第 k 个全排列序列。
刚开始没仔细读题就之间 DFS 回溯,很快写好但超时了哈哈哈。再读一下题目,发现如果 k 很大,要一个个找过去,所以会很慢。
实际上,这是一道数学题(找规律)。以 n = 5 举例,共有 5!= 120 个排列,我们发现:当 k <= 24,排列全部以 1 开头;24 < k <= 48,排列全部以 2 开头,以此类推。因此,我们可以一位一位的构造答案,根据 k 值判断其落在哪个区间,找到开头数字加入结果;然后,从数组中删除该开头数字,并确定 k 值位于当前区间的第几个,更新 k 值;按照上述方法进行操作,直到得到一个全排列,就是最后的答案。
以 n = 5,k = 31 为例(nums = 1,2,3,4,5):
class Solution:
def getPermutation(self, n: int, k: int) -> str:
ans = ""
nums = [(i + 1) for i in range(n)]
while len(ans) != n: # 迭代方法,逐个字符加入到结果中
nf = math.factorial(len(nums) - 1)
for i in range(len(nums)):
if k <= (i + 1) * nf: # 找到k位于哪个区间
ans += str(nums[i])
del nums[i]
k -= i * nf # k位于当前区间的第几个
break
return ans
这道题是给一个 m*n 的字符矩阵 board 和一个单词 word,判断 word 是否存在字符矩阵中。
这道题很明显用 DFS 回溯法去解决。做法如下:
board[i][j] == word[0]
**,则将 boardi 位置先改为 ""(因为每个位置字符只能使用一次),然后进入回溯函数 search(i, j, path, wind)
(path 记录单词路径,wind 为 word 索引)进行深搜判断。如果没有在 search() 函数中找到,说明没有以当前字符 boardi 开头的单词,要恢复原来该位置的字符。** class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def search(i, j, path, wind): # (i,j)是匹配word第一个字符的坐标,path记录结果,wind为word索引
isfind = False
if path == word: # 找到了该单词
return True
for p in pos:
if 0 <= i+p[0] < m and 0 <= j+p[1] < n and board[i+p[0]][j+p[1]] == word[wind]:
tmp = board[i+p[0]][j+p[1]]
board[i+p[0]][j+p[1]] = ""
isfind = search(i+p[0], j+p[1], path+word[wind], wind+1)
board[i+p[0]][j+p[1]] = tmp # 先恢复原来的字符
if isfind == True: # 再判断返回结果,如果是True直接返回;如果是False继续查找
return True
return False
if len(word) == 0 or len(board) == 0:
return False
pos = [[-1,0], [1,0], [0,-1], [0,1]] # 上下左右四个位置
m = len(board)
n = len(board[0])
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
tmp = board[i][j]
board[i][j] = ""
if search(i, j, word[0], 1):
return True
board[i][j] = tmp # 如果没有找到,恢复原来的字符
return False
这道题是给一个数字字符串,返回所有可能的 IP 地址组合。
这道题和下面的 Leetcode 131 以及 Leetcode 842 做法是类似的,也是使用回溯法 DFS 对字符串前缀进行划分。注意该深搜函数 search(s, path)
(s 为后半部分字符串,path 为划分的 IP 子段)的几个出口:
在 for 循环中,还要注意去除前导 0 以及字符串前缀数字 > 255 的情况,才能进行递归调用深搜。
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def search(s, path):
if len(path) > 4: # 不满足题意
return
if not s and len(path) < 4: # 不满足题意
return
if not s and len(path) == 4: # 找到一组解
ans.append('.'.join(path))
return
for i in range(1, len(s) + 1):
pre = s[:i] # 划分前缀
if (len(pre) > 1 and pre[0] == '0') or int(pre) > 255: # 不满足题意
continue
search(s[i:], path + [pre])
ans = []
search(s, [])
return ans
这道题是给一个字符串,将字符串分割成一些子串,使得所有子串都是回文串,求所有划分的方案数。
一个子串是否是回文串可以使用 s == s[::-1]
来判断。
方法1(Brute Force):
首先想到一种暴力解法,就是对于字符串的每个字符 si,依次将 si 加入到回文串前缀列表中每个回文串前缀的后面,然后再判断 si 的加入能否形成新的回文串前缀。如果可以,拓展回文串前缀列表。最后,遍历完所有字符后,列表中存储的就是最终结果。
以 s = "abba" 举例:
这种做法时间复杂度为 O(n^4),空间复杂度为 O(n^2),能够 AC。
Python3 实现:
class Solution:
def partition(self, s: str) -> List[List[str]]:
ans = [[]]
for i in range(len(s)):
for a in ans: # 将当前字符加入到每个字符串前缀列表的后面
a.append(s[i])
for a in ans:
N = len(a)
st = a[-1]
for j in range(N-2, -1, -1):
st = a[j] + st # 从最后一个字符开始构造新的子串
if st == st[::-1] and a[:j] + [st] not in ans: # 判断新的子串是否是回文串,且构成的回文串前缀是否之前出现过
ans.append(a[:j] + [st]) # 将新的回文串前缀加入到结果列表中
return ans
方法2(DFS):
其实这道题一看是求所有结果,很明显用 DFS 回溯法求解,但是刚开始没有思路,找不到如果求解的方法,最后看了别人的做法才明白。
使用回溯法的解题思路是对于字符串 s 的前缀进行划分,然后判断前缀是否是回文子串。如果是,形成临时结果,将 s 的后半部分和临时结果传入到下一层(深搜);如果不是,那就继续划分下一个前缀。最后,传入的 s 会变成空串,这时形成的结果必定是回文串的一个划分,加入到结果列表中即可。
以 s = "aab" 举例,用 path 记录一种划分结果:
优化:可以通过用区间 DP 来计算任意 si:j 之间是否是回文串 【区间DP、双指针】647. Palindromic Substrings,并保存结果;然后再执行DFS,如果发现某条子串不是回文,就可以直接退出,从而减少计算量。
Python3 实现:
class Solution:
def partition(self, s: str) -> List[List[str]]:
def search(s, path):
if not s: # s 变为空串,将形成的一种结果path加入到ans中
ans.append(path[:])
for i in range(1, len(s) + 1):
pre = s[:i] # 对于s的每一个前缀
if pre == pre[::-1]: # 如果前缀是回文串,则深搜
search(s[i:], path + [pre]) # 将后半部分和临时结果传入到下一层
ans = []
search(s, [])
return ans
这道题是给一个数字字符串 S,将其划分成斐波那契序列。
很容易想到用 DFS 回溯法去找斐波那契序列的一种划分。类似于上面的 Leetcode 131,对于数字字符串 S 的前缀进行划分,如果 S 的前缀合法(没有前导 0 并且数字没有越界),就将 S 的后半部分和临时结果 path 传入,进行递归调用。
递归出口:
ans.extend(path)
,返回 True。第一次提交时,WA 了,报错如下:
检查了一下发现没什么问题啊?然后重新读题,很敏感的发现斐波那契序列数值要求为 <= 2 ** 31 - 1(2147483647),然后发现报错结果的最后一项 11336528511 > 2 ** 31 - 1,因此在代码中加入了数值范围的判断,就 AC 了。
class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
def search(S, path):
if len(path) >= 3 and path[-3] + path[-2] != path[-1]: # 不满足斐波那契条件
return False
if not S and len(path) >= 3: # S为空串,说明可以划分
ans.extend(path) # 找到一种划分,保存结果到ans中,返回
return True
for i in range(1, len(S) + 1):
pre = S[:i] # 划分前缀
if (len(pre) > 1 and pre[0] == '0') or (int(pre) > 2 ** 31 - 1): # 不满足题意
continue
if search(S[i:], path + [int(pre)]): # 将S后半部分和临时结果传入进行递归调用
return True
return False # S本身长度小于3
ans = []
search(S, [])
return ans