045.双向广搜

前置知识：常见经典递归过程解析、根据数据量猜解法的技巧、宽度优先遍历及其扩展

双向广搜常见用途 1：小优化 §

bfs 的剪枝策略，分两侧展开分支（双向奔赴），哪侧数量少就从哪侧展开（贪心：避免展开太宽）

题目1.单词接龙 §

题目描述 §

和 单词接龙 II 一样，要求的返回不同

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
•  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

测试链接 §

127.单词接龙

答案 §

var (
	emptyStruct = struct{}{}
)
 
func ladderLength(beginWord string, endWord string, wordList []string) int {
	// 总词表
	dict := make(map[string]struct{}, len(wordList))
	for _, word := range wordList {
		dict[word] = emptyStruct
	}
	if _, has := dict[endWord]; !has {
		return 0
	}
	// 数量小的一侧
	smallLevel := map[string]struct{}{}
	// 数量大的一侧
	bigLevel := map[string]struct{}{}
	// 由数量小的一侧，所扩展出的下一层列表
	nextLevel := map[string]struct{}{}
 
	smallLevel[beginWord] = emptyStruct
	bigLevel[endWord] = emptyStruct
	ans := 2 // 至少要包含 beginWord 和 endWord
	for ; len(smallLevel) > 0; ans++ {
		// 从小侧扩展
		for k := range smallLevel {
			word := []byte(k)
			wordLen := len(word)
			for i := 0; i < wordLen; i++ {
				old := word[i]
				var char byte = 'a'
				for ; char <= 'z'; char++ {
					if char == old {
						continue
					}
					word[i] = char
					wordStr := string(word)
					if _, has := bigLevel[wordStr]; has {
						// 两侧碰到了
						return ans
					}
					if _, has := dict[wordStr]; has {
						delete(dict, wordStr)
						nextLevel[wordStr] = emptyStruct
					}
				}
				word[i] = old
			}
		}
 
		if len(nextLevel) <= len(bigLevel) {
			nextLevel, smallLevel = smallLevel, nextLevel
		} else {
			smallLevel, bigLevel, nextLevel = bigLevel, nextLevel, smallLevel
		}
		clear(nextLevel)
	}
	return 0
}

双向广搜常见用途 2：重要！本体！ §

用于解决特征很明显的一类问题

特征：全量样本不允许递归完全展开，但是半量样本可以完全展开（根据数据量猜解法的技巧）

过程：把数据分成两部分，每部分各自展开计算结果，然后设计两部分结果的整合逻辑

题目1.牛牛背包问题 §

题目描述 §

牛牛准备参加学校组织的春游，出发前牛牛准备往背包里装入一些零食，牛牛的背包容量为 w。

牛牛家里一共有 n 袋零食，第 i 袋零食体积为 v[i]。

牛牛想知道在总体积不超过背包容量的情况下，他一共有多少种零食放法（总体积为 0 也算一种放法）。

输入描述：

输入包括两行

• 第一行为两个正整数 n 和 w，表示零食的数量和背包的容量。
• 第二行 n 个正整数 v[i]，表示每袋零食的体积。

输出描述：

输出一个正整数，表示牛牛一共有多少种零食放法。

数据规模：

• 1 <= n <= 30
• 1 <= w <= 2 * 10^9
• 0 <= v[i] <= 10^9

测试链接 §

• 牛客：牛牛的背包问题
• 洛谷：P4799【CEOI2015 Day2】世界冰球锦标赛

思路 §

看起来像是动态规划的背包问题，但是看数据量，使用动态规划必定超时

答案 §

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)
 
const (
	// 此数据量牛客和洛谷都能通过
	MAXN = 40
	MAXM = 1 << 20
)
 
var (
	n     int
	w     int
	arr   = [MAXN]int{}
	lNums = [MAXM]int{}
	lIdx  = 0
	rNums = [MAXM]int{}
	rIdx  = 0
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		w, _ = strconv.Atoi(in.Text())
		for i := 0; i < n; i++ {
			in.Scan()
			arr[i], _ = strconv.Atoi(in.Text())
		}
		fmt.Fprintln(out, compute())
	}
	out.Flush()
}
 
func compute() int {
	lIdx, rIdx = 0, 0
	// 左侧展开
	f(0, n>>1, 0, &lNums, &lIdx)
	// 右侧展开
	f(n>>1, n, 0, &rNums, &rIdx)
	// 整合两边
	// 排序便于整合——双指针
	sort.Ints(lNums[:lIdx])
	sort.Ints(rNums[:rIdx])
	ans := 0
	for i, j := lIdx-1, 0; i >= 0; i-- {
		for j < rIdx && lNums[i]+rNums[j] <= w {
			j++
		}
		ans += j
	}
	return ans
}
 
// arr[start:end] 展开，每个位置要或不要
// curW：累计的重量
// ans：将答案放到这里
func f(start, end, curW int, ans *[MAXM]int, idx *int) {
	if curW > w {
		return
	}
	if start == end {
		ans[*idx] = curW
		*idx++
	} else {
		// 不要 arr[i] 位置的数
		f(start+1, end, curW, ans, idx)
		// 要 arr[i] 位置的数
		f(start+1, end, curW+arr[start], ans, idx)
	}
}

复杂度 §

使用双向广搜：

时间复杂度：$O(2^{\frac{n}{2}}\ast lo{g}^{2^{\frac{n}{2}}})$，其中 $2^{15}=32768\approx 3\ast 10^5$

• 左右两侧各自展开：$O(2^{15})+O(2^{15})$，每个位置要或不要，递归下去。最多收集到 $2^{15}$ 个结果
• 整合：排序 $O(2^{15}\ast lo{g}^{2^{15}})$；双指针 $O(2^{15})$，其中 $2^{15}$ 是收集到答案的规模

使用普通广搜：

时间复杂度：$O(2^n)$，全递归展开，其中 $2^{30}=1073741824\approx 10^9$

题目2.最接近目标值的子序列和 §

题目描述 §

给你一个整数数组 nums 和一个目标值 goal 。

你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。

返回 abs(sum - goal) 可能的 最小值 。

注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。

提示：

• 1 <= nums.length <= 40
• -10^7 <= nums[i] <= 10^7
• -10^9 <= goal <= 10^9

测试链接 §

1755.最接近目标值的子序列和

答案 §

var (
	theNums []int
)
 
func minAbsDifference(nums []int, goal int) int {
	n := len(nums)
	theNums = nums
	positive, negative := 0, 0
	for _, num := range nums {
		if num >= 0 {
			positive += num
		} else {
			negative += num
		}
	}
	// 剪枝
	if positive <= goal {
		return abs(positive - goal)
	}
	if negative >= goal {
		return abs(negative - goal)
	}
 
	sort.Ints(nums)
	lSums := []int{}
	collect(0, n>>1, 0, &lSums)
	rSums := []int{}
	collect(n>>1, n, 0, &rSums)
	sort.Ints(lSums)
	sort.Ints(rSums)
	ans := abs(goal)
	lLen, rLen := len(lSums), len(rSums)
	lIdx, rIdx := 0, rLen-1
	for ; lIdx < lLen; lIdx++ {
		for rIdx > 0 && abs(goal-lSums[lIdx]-rSums[rIdx-1]) <= abs(goal-lSums[lIdx]-rSums[rIdx]) {
			rIdx--
		}
		ans = min(ans, abs(goal-lSums[lIdx]-rSums[rIdx]))
	}
	return ans
}
 
func collect(start, end, curSum int, ans *[]int) {
	if start == end {
		*ans = append(*ans, curSum)
		return
	}
 
	// 小优化：相同的数字不用一层一层展开，而是直接选择要几个
	// 比如有 3 个相同的数字，一层一层展开：2^3；直接选择要几个：3
 
	// theNums[start:i] 都是相同的数字
	i := start + 1
	for i < end && theNums[i-1] == theNums[i] {
		i++
	}
	// 要 j 个
	for j := 0; j <= i-start; j++ {
		collect(i, end, curSum+j*theNums[start], ans)
	}
}
 
func abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}