DFS
- Word Ladder
从原始词通过词典变成目标词，每次改变一个字母
为了速度，可以看做双向查找，原始词和目标词路径互换
def word_range(word):
for ind in range(len(word)):
temp = word[ind]
for c in [chr(x) for x in range(ord('a'), ord('z') + 1)]:
if c != temp:
yield word[:ind] + c + word[ind + 1:]
def ladder_length(begin_word, end_word, word_list):
if len(begin_word) != len(end_word):
return -1
if begin_word == end_word:
return 0
if sum(c1 != c2 for c1, c2 in zip(begin_word, end_word)) == 1:
return 1
begin_set = set()
end_set = set()
begin_set.add(begin_word)
end_set.add(end_word)
result = 2
while begin_set and end_set:
if len(begin_set) > len(end_set):
begin_set, end_set = end_set, begin_set
next_begin_set = set()
for word in begin_set:
for ladder_word in word_range(word):
if ladder_word in end_set:
return result
if ladder_word in word_list:
next_begin_set.add(ladder_word)
word_list.remove(ladder_word)
begin_set = next_begin_set
result += 1
return -1
assert ladder_length(
'hit', 'cog', ["hot", "dot", "dog", "lot", "log"]) == 5
- 质因子分解
因子平方小于等于值之前递归，如果值除以因子没有余数则继续往深度搜索，循环中因子累加
def get_factors(n):
def factor(n, i, combi, res):
while i * i <= n:
if n % i == 0:
res += combi + [i, int(n / i)],
factor(n / i, i, combi + [i], res)
i += 1
return res
return factor(n, 2, [], [])
assert get_factors(16) == [[2, 8], [2, 2, 4], [2, 2, 2, 2], [4, 4]]
- 岛计算
1为陆地，0为海水，规则：如果陆地上下左右被海水包围算一个岛，例如：
[[1, 1, 1, 0, 0],
[1, 1, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 0, 0]]
岛个数：2
遍历地图(可以看做二维数组)，如果值为1，即陆地，则将与之相邻的陆地变为0，然后视为一个岛，结果+1
def num_islands(grid):
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
dfs(grid, i, j)
count += 1
return count
def dfs(grid, i, j):
if (i < 0 or i >= len(grid)) or (j < 0 or j >= len(grid[0])):
return
if grid[i][j] != 1:
return
grid[i][j] = 0
dfs(grid, i + 1, j)
dfs(grid, i - 1, j)
dfs(grid, i, j + 1)
dfs(grid, i, j - 1)
grid = [[1, 1, 1, 0, 0],
[1, 1, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 0, 0]]
assert num_islands(grid) == 2
- 数独
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次。
首先通过已给出数字筛选出所有空格候选填充数字组，接着开始在空格中填充数字，如果考虑速度，可以优先选择候选数字少的空格，然后向深处搜索，如果空格选完证明完成任务，保存结果；如果在填充数字过程中出现空格无候选数字证明任务失败，终止当前分支
import numpy as np
import copy
import queue
class Sudoku(object):
def __init__(self, board):
board = np.asarray(board)
assert board.shape == (9, 9)
self.results = queue.Queue()
valids = self.gather_value(board)
copy_v = copy.deepcopy(valids)
copy_b = board.copy()
self.solve(copy_v, copy_b)
def gather_value(self, board):
nums = [i for i in range(1, 10)]
valids = {(i, j): nums.copy() for i in range(9)
for j in range(9) if board[i, j] == 0}
for i, row in enumerate(board):
for j, v in enumerate(row):
if v != 0:
for index in range(9):
if (i, index) in valids and v in valids[(i, index)]:
valids[(i, index)].remove(v)
if (index, j) in valids and v in valids[(index, j)]:
valids[(index, j)].remove(v)
_row, _col = i // 3, j // 3
for i_row in range(3):
for i_col in range(3):
_idx = (_row * 3 + i_row, _col * 3 + i_col)
if _idx in valids and v in valids[_idx]:
valids[_idx].remove(v)
return valids
def solve(self, valids, board):
if len(valids) == 0:
self.results.put([board])
return
slot = min(valids.keys(), key=lambda x: len(valids[x]))
nums = valids[slot]
for n in nums:
r, c = slot
copy_b = board.copy()
copy_b[r, c] = n
copy_v = copy.deepcopy(valids)
del copy_v[slot]
for index in range(9):
if (index, c) in copy_v and n in copy_v[(index, c)]:
copy_v[(index, c)].remove(n)
if len(copy_v[(index, c)]) == 0:
return
if (r, index) in copy_v and n in copy_v[(r, index)]:
copy_v[(r, index)].remove(n)
if len(copy_v[(r, index)]) == 0:
return
_row, _col = r // 3, c // 3
for i_row in range(3):
for i_col in range(3):
_idx = (_row * 3 + i_row, _col * 3 + i_col)
if _idx in copy_v and n in copy_v[_idx]:
copy_v[_idx].remove(n)
if len(copy_v[_idx]) == 0:
return
self.solve(copy_v, copy_b)
board = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
s = Sudoku(board)
for r in s.results.get():
print(r)
'''
[[5 3 4 6 7 8 9 1 2]
[6 7 2 1 9 5 3 4 8]
[1 9 8 3 4 2 5 6 7]
[8 5 9 7 6 1 4 2 3]
[4 2 6 8 5 3 7 9 1]
[7 1 3 9 2 4 8 5 6]
[9 6 1 5 3 7 2 8 4]
[2 8 7 4 1 9 6 3 5]
[3 4 5 2 8 6 1 7 9]]
'''
