Leetcode 17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
图片.png
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
解题思路：建立一个多层循环，注意这里的now和state的转换。
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if digits == '':
return None
state = ['']
dic = {'2':['a', 'b', 'c'], '3':['d', 'e', 'f'], '4':['g', 'h', 'i'], '5':['j', 'k', 'l'], '6':['m', 'n', 'o'], '7':['p', 'q', 'r', 's'], '8':['t', 'u', 'v'],
'9':['w', 'x', 'y', 'z']}
for d in range(len(digits)):
digit = digits[d]
now = []
for letter in dic[digit]:
for s in state:
s += letter
now.append(s)
state = now
return state
Leetcode 79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
解题思路：递归
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
m = len(board)
n = len(board[0])
used = [[False for i in range(n)] for j in range(m)]
%枚举所有起点
for i in range(m):
for j in range(n):
if self.dfs(board, used, i, j, word, 0):
return True
return False
def dfs(self, board, used, r, c, word, pos):
%如果r和c越界，或者当前位置已经访问过，或者当前位置和目标不相同，就返回false
if r < 0 or r >= len(board) or c < 0 or c >=len(board[0]) or word[pos]!=board[r][c] or used[r][c]:
return False
%这里是当前位置和目标相同的情况，如果额外的，pos是最后一个，就说明找到了
if pos == len(word) - 1:
return True
used[r][c] = True
ans = self.dfs(board, used, r-1, c, word, pos+1) or self.dfs(board, used, r+1, c, word, pos+1) or self.dfs(board, used, r, c-1, word, pos+1) or self.dfs(board, used, r, c+1, word, pos+1)
print(ans)
used[r][c] = False
return ans
Leetcode 46. 全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
class Solution(object):
def __init__(self):
self.ans = []
self.path = []
self.used = []
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
for i in range(len(nums)):
self.used.append(False)
self.dfs(nums, 0)
return self.ans
def dfs(self, nums, pos):
if pos == len(nums):
self.ans.append(self.path)
return
for i in range(len(nums)):
if not self.used[i]:
self.used[i] = True
self.path.append(nums[i])
self.dfs(nums, pos+1)
self.used[i] = False
self.path = self.path[:-1]
Leetcode 47. 全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解题思路：跟上面大致相同，不过需要先对数组排序，然后在选择某一位的数字时判断这个数字跟下一位数字是否一致，如果一致的话在考虑之后的排列时就要改变之后的遍历策略。注意python中要使用copy.deepcopy()来进行数组复制，否则的话就只是复制指针。
import copy
class Solution(object):
def __init__(self):
self.ans = []
self.used = []
self.path = []
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
self.path = [0 for i in range(len(nums))]
for i in range(len(nums)):
self.used.append(False)
self.dfs(nums, 0, 0)
return self.ans
def dfs(self, nums, pos, start):
if pos == len(nums):
res = copy.deepcopy(self.path)
self.ans.append(res)
return
for i in range(start, len(nums)):
if not self.used[i]:
self.used[i] = True
self.path[i] = nums[pos]
if pos+1 < len(nums) and nums[pos] != nums[pos+1]:
self.dfs(nums, pos + 1, 0)
else:
self.dfs(nums, pos + 1, i+1)
self.used[i] = False
Leetcod 78. 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解题思路：二进制法，将数组的长度转化为二进制，然后遍历得到从0 ~ 2^n - 1的数字，如果对应位置上为1，则在结果中加入这个数。
import math
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
n = len(nums)
max_num = int(math.pow(2, n) - 1)
for num in range(max_num + 1):
num = bin(num)
num = num[2:].zfill(n)
res = []
for i in range(n):
if num[i] == '1':
res.append(nums[i])
ans.append(res)
return ans
Leetcode 90. 子集 II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
import copy
class Solution(object):
def __init__(self):
self.ans = []
self.path = []
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
self.dfs(nums, 0)
return self.ans
def dfs(self, nums, pos):
if pos == len(nums):
res = copy.deepcopy(self.path)
self.ans.append(res)
return
k = 0
while (pos+k <len(nums)) and nums[pos+k]==nums[pos]:
k += 1
for i in range(k+1):
self.dfs(nums, pos+k)
self.path.append(nums[pos])
self.path = self.path[:-k-1]
Leetcode 216. 组合总和
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
class Solution:
def combinationSum3(self, k, n):
ans = []
self.dfs(range(1, 10), k, n, 0, ans, [])
return ans
def dfs(self, nums, k, n, index, ans, path):
if k < 0 or n < 0:
return
elif k == 0 and n == 0:
ans.append(path)
return
for i in range(index, len(nums)):
self.dfs(nums, k - 1, n - nums[i], i + 1, ans, path + [nums[i]])
Leetcode 52. N皇后II
图片.png图片.png
class Solution:
def __init__(self):
self.count=0
def totalNQueens(self, n):
def check(k,j):
for i in range(k):
if board[i]==j or abs(k-i)==abs(board[i]-j):
return False
return True
def dfs(depth):
if depth==n:
self.count+=1
return
for i in range(n):
if check(depth,i):
board[depth]=i
dfs(depth+1)
board=[-1 for i in range(n)]
dfs(0)
return self.count
Leetcode 473. 火柴拼正方形
图片.png
class Solution:
def makesquare(self, nums: List[int]) -> bool:
if len(nums) < 4:
return False
perimeter = sum(nums)
length = perimeter // 4
if length * 4 != perimeter:
return False
nums.sort(reverse = True)
subSum = [0 for _ in range(4)]
return self.dfs(nums, subSum, length, 0)
def dfs(self, nums, subSum, length, index):
if subSum[0] == length and subSum[1] == length and subSum[2] == length:
return True
for i in range(4):
if subSum[i] + nums[index] > length:
continue
subSum[i] += nums[index]
if self.dfs(nums, subSum, length, index+1):
return True
subSum[i] -= nums[index]
return False
