3.1 深度优先DFS
问题1：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
image.png
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
思路：深度优先搜索，从根节点到每个叶子节点的所有路径即结果，深度为子串的长度
示例代码:
var (
letterMap = []string{
" ", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz", //9
}
res = []string{}
)
func letterCombinations(digits string) []string {
if digits == "" {
return []string{}
}
res = []string{}
dfs(digits, 0, "")
return res
}
func dfs(digits string, i int, s string) {
if i == len(digits) {
res = append(res, s)
return
}
curs := letterMap[digits[i] - '0']
for _, ch := range curs {
dfs(digits, i+1, s + string(ch))
}
}
问题2：给定一个数组，要求在这个数组中找出 k 个数之和为 target 的所有组合。
Input: nums = [1, 0, -1, 0, -2, 2], and target = 0.
Output: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
思路：深度优先搜索，层数为k。注意去重的处理。
示例代码:
import "sort"
var res = [][]int{}
func fourSum(nums []int, target int) [][]int {
if len(nums) == 0 {
return [][]int{}
}
sort.Ints(nums)
res = [][]int{}
r := []int{}
dfs_sum(nums, 0, r, target)
return res
}
func dfs_sum(nums []int, i int, r []int, target int) {
if i == 4 || 0 == len(nums) {
if len(r) >= 4 && r[0] + r[1] + r[2] + r[3] == target {
res = append(res, []int{r[0], r[1], r[2], r[3]})
}
return
}
for j := 0; j < len(nums); j++ {
if j > 0 && nums[j] == nums[j-1] {
continue
}
r = append(r, nums[j])
dfs_sum(nums[j+1:], i + 1, r, target)
if len(r) >= 1 {
r = r[:len(r)-1]
}
}
}
3.2 宽度优先搜索 BFS
宽度优先搜索通常用在求最短路径，按层遍历，第一次满足要求的层数就是最短的路径。BFS需要借助队列来保存每一层的节点，访问过的节点要做标记避免重复访问。
3.2.1 二进制矩阵中的最短路径
题目描述：给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
1 路径途经的所有单元格都的值都是 0 。
2 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度 是该路径途经的单元格总数。
思路：从左上角开始，遍历所有可以走的方向，BFS方式求到达右下角的最小层数。
示例代码：
type Pos struct {
x, y int
}
func shortestPathBinaryMatrix(grid [][]int) int {
if len(grid) == 0 || len(grid[0]) == 0 {
return -1
}
M, N := len(grid), len(grid[0])
direction := []Pos{{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}}
Q := list.New()
// 根节点入队
Q.PushBack(Pos{0, 0})
path_len := 0
for Q.Len() != 0 {
// 保存当前层的长度
level_size := Q.Len()
path_len++
// 依次处理当前层的所有节点
for i := 0; i < level_size; i++ {
cur_pos := Q.Front().Value.(Pos)
Q.Remove(Q.Front())
if grid[cur_pos.x][cur_pos.y] == 1 {
continue
}
// 如果到达右下角返回结果
if cur_pos.x == (M - 1) && cur_pos.y == (N - 1) {
return path_len
}
// 访问过的位置标记为1
grid[cur_pos.x][cur_pos.y] = 1
// 遍历所有能走的方向，加入队列
for _, dr := range direction {
nx, ny := cur_pos.x + dr.x, cur_pos.y + dr.y
if nx < 0 || nx >= M || ny < 0 || ny >= N {
continue
}
Q.PushBack(Pos{nx, ny})
}
}
}
return -1
}
3.2.2 完全平方数
题目描述：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
思路：转化为BFS问题模型，从1到根号n的所有平方数（1，4，9...）为每次所有可能的路径。从n开始遍历，当n=0时即为结果。
示例代码：
func numSquares(n int) int {
numsqs := []int{}
for i, ii := 1, 1; ii <= n; i, ii = i + 1, (i + 1) * (i + 1){
numsqs = append(numsqs, ii)
}
mark := map[int]bool{}
Q := list.New()
Q.PushBack(n)
mark[n] = true
ans := 0
for Q.Len() != 0 {
lv_size := Q.Len()
ans++
for i := 0; i < lv_size; i++ {
cur := Q.Front().Value.(int)
Q.Remove(Q.Front())
for _, nq := range numsqs {
if cur == nq {
return ans
}
if cur < nq {
break
}
if mark[cur - nq] {
continue
}
mark[cur - nq] = true
Q.PushBack(cur - nq)
}
}
}
return n
}
网友评论