127. 单词接龙
这一题的基本的单向BFS思路就是，从start单词开始，寻找其所有在wordList中的可行下一步，存入队列之后，按照BFS的思路一直找到最后一层。因此这种问题的主要复杂度开销来自于每一层的数量：
解决办法就是两边同时BFS进行搜索：
那么为什么可以减少搜索空间呢？其实看图就知道了，乍一看可能需要并行程序才可以完成时间的优化，因为最终还是需要搜索整个空间的。但其实搜索整个空间是错误的，单向BFS是三角形的搜索，但是变为双向的，其实是变成了菱形的，也因此不是严格的节约了1/2.
伪码与思路：
d1、d2 为两个方向的队列m1、m2 为两个方向的哈希表，记录每个节点距离起点的// 只有两个队列都不空，才有必要继续往下搜索// 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点while(!d1.isEmpty() && !d2.isEmpty()) {if (d1.size() < d2.size()) {update(d1, m1, m2);} else {update(d2, m2, m1);}}// update 为将当前队列 d 中包含的元素取出，进行「一次完整扩展」的逻辑（按层拓展）void update(Deque d, Map cur, Map other) {}
使用Rust写，存在一个lifetime的问题：
impl Solution {
/// 127. 单词接龙
pub fn ladder_length(begin_word: String, end_word: String, word_list: Vec<String>) -> i32 {
let set: HashSet<String> = HashSet::from_iter(word_list.into_iter());
// println!("{:?}", set);
if !set.contains(&end_word) { return 0; }
let res = Solution::bfs(&set, begin_word, end_word);
return if res == -1 { 0 }else { res + 1 }
}
/// 双向bfs的具体实现
fn bfs(set: &HashSet<String>, start: String, end: String) -> i32 {
// 对每一个String进行处理的包装,deque为当前方向的队列，cur为当前方向走过的路径，other为另一个方向
fn update<'a>(deque: &mut VecDeque<&'a String>, cur: &mut HashMap<&'a String, i32>,
other: &HashMap<&'a String, i32>, set: &'a HashSet<String>) -> i32
{
println!("{:?}", deque);
let mut m = deque.len();
// 遍历这一层,取出每一个单词进行替换
while m > 0 {
let mut temp = deque.pop_front().unwrap();
// 考虑该单词的每一个字符可能被替换的情况
for i in 0..temp.len() {
for j in b'a'..=b'z' {
// 替换该位置的字母为26个字符中的一个
let mut next = (*temp).clone();
next.replace_range(i..=i, (j as char).to_string().as_str());
// println!("{}", next);
if set.contains(&next) {
println!("{} -> {}; ", temp, next);
// 1. 如果这个字符在当前方向被记录过，跳过，后半段是一个小剪枝
if cur.contains_key(&next)
&& *cur.get(&next).unwrap() <= *cur.get(&temp).unwrap()
{ continue }
// 2. 如果另一个方向的包含了当前的这个元素，那么就不用跳过了，直接返回
if other.contains_key(&next) {
// 需要多加1，不然少算了一步
return *cur.get(&temp).unwrap() + *other.get(&next).unwrap() + 1;
}else {
// 否则进入下一层的BFS
let next = set.get(&next).unwrap();
deque.push_back(next);
cur.insert(next, *cur.get(&temp).unwrap() + 1);
}
}
}
}
m -= 1;
}
-1
}
let (mut d1, mut d2) = (VecDeque::new(), VecDeque::new());
let (mut m1, mut m2) = (HashMap::new(), HashMap::new());
// 放入头结点，开始进行BFS
d1.push_back(&start);
m1.insert(&start, 0);
d2.push_back(&end);
m2.insert(&end, 0);
// println!("{:?}", m1);
// println!("{:?}", m2);
while !d1.is_empty() && !d2.is_empty() {
let mut t = -1;
if d1.len() <= d2.len() {
println!("[--->正向]");
t = update(&mut d1, &mut m1, &m2, set);
println!("[--->此时的t]{}\n", t);
}else {
println!("[--->反向]");
t = update(&mut d2, &mut m2, &m1, set);
println!("[--->此时的t]{}", t);
}
if t != -1 { return t; }
}
-1
}
}
因为存储的只是存储在Set中的String，那么就存在两个问题：
- Deque以及HashMap中存储的引用的生命周期应该被约束为和函数生命周期以及set生命周期一样，因为存在一个问题，我们在函数作用域中修改了deque，并向其中添加了set中的String的引用，离开函数之后二者均还存在，但是我们需要保证，deque中的引用是可用的，也即deque中的引用不会在set中实际的String被释放之后还存在，因此deuqe中的String的生命周期和set的生命周期保持一致。map也是一样。
我们不能直接朝deque中添加next，因为next是一个函数范围内的变量，如果添加的话，就会出现悬垂指针。因此需要从set中找到next并获取他的引用。
433. 最小基因变化
先用双向BFS写一下： ```rust /// 433. 最小基因变化 双向BFS算法 pub fn min_mutation(start: String, end: String, bank: Vec
) -> i32 { fn update<’a> (set: &’a HashSet >, items: &Vec , cur: &mut HashMap<&'a Vec<char>, i32>, other: &HashMap<&'a Vec<char>, i32>) -> i32{
let mut len = deque.len(); while len > 0 { let temp = deque.pop_front().unwrap(); let step = *cur.get(temp).unwrap(); // 每一个元素定长为8位 for i in 0..8 { for c in &*items { let mut next = temp.clone(); if next[i] == *c { continue; } next[i] = *c; if !set.contains(&next) || cur.contains_key(&next) { continue; } if other.contains_key(&next) { return step + *other.get(&next).unwrap() + 1; } let next = set.get(&next).unwrap(); cur.insert(next, step + 1); deque.push_back(next); } } len -= 1; } -1}
let mut set = HashSet::new();
bank.into_iter().for_each(|x| {set.insert(x.chars().collect::<Vec<char>>());});
println!("{:?}", set);
let start = start.chars().collect::<Vec<char>>();
let end = end.chars().collect::<Vec<char>>();
if !set.contains(&end) { return -1; }
let items = vec!['A', 'G', 'C', 'T'];
let (mut d1, mut d2) = (VecDeque::new(), VecDeque::new());
let (mut m1, mut m2) = (HashMap::new(), HashMap::new());
d1.push_back(&start);
m1.insert(&start, 0);
d2.push_back(&end);
m2.insert(&end, 0);
while !d1.is_empty() && !d2.is_empty() {
let mut t = -1;
if d1.len() <= d2.len() {
t = update(&set, &mut d1, &items, &mut m1, &m2);
}else {
t = update(&set, &mut d2, &items, &mut m2, &m1);
}
if t != -1 { return t; }
}
-1
}
<a name="htnmu"></a>
## 启发式搜索：AStar算法
首先我们定义了一个对象，该对象存储基因序列以及其到终点的**步数**：
```rust
/// 记录节点inner与终点之间的距离
#[derive(Debug, Eq)]
struct Node {
pub inner: Vec<char>,
val: i32
}
impl Node {
fn new(s: &Vec<char>, end: &Vec<char>) -> Self {
let mut val = 0;
s.iter().zip(end.iter()).for_each(|x| {
if *x.0 != *x.1 {
val += *x.0 as i32 - *x.1 as i32;
}
});
Self {
inner: s.clone(),
val
}
}
}
impl PartialEq<Self> for Node {
fn eq(&self, other: &Self) -> bool {
self.inner == other.inner && self.val == other.val
}
}
impl PartialOrd<Self> for Node {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Node {
fn cmp(&self, other: &Self) -> Ordering {
self.val.cmp(&other.val)
}
}
算法的逻辑在于，我们使用一个大根堆，这个堆存储Node，每一次堆顶都是离终点距离最近的一个基因序列（不同的基因编号最多）。
因此算法逻辑为：
拿出一个距离end最远的序列temp，查找temp的所有可行下一步next，然后走过去：
- 如果
next是终点的话，直接返回map维护的到start的距离 - 如果不是终点，并且map中没有记录其与
Start的距离，或者距离过大，那么就更新，将next放入堆中，并记录其到start的距离
这个的逻辑也是BFS，也是从Start开始，然后遍历能够走到下一步的所有可能性。相比BFS的优化在于，使用了一个优先队列，将我们定义的基因序列到目的地的距离存储起来，每一次在查找的时候，BFS是不可定顺序的，但是基于堆我们可以每一次挑选距离end最近的节点进行选择，简化了代码。
pub fn min_mutation(start: String, end: String, bank: Vec<String>) -> i32 {
let mut set = HashSet::new();
bank.into_iter().for_each(|x| {set.insert(x.chars().collect::<Vec<char>>());});
let start = start.chars().collect::<Vec<char>>();
let end = end.chars().collect::<Vec<char>>();
// 存储每一个节点，大根堆，离end最远的元素将被放入堆顶
let mut p = BinaryHeap::new();
p.push(Reverse(Node::new(&start, &end)));
// map记录了这个元素到start的距离
let mut map = HashMap::new();
map.insert(&start, 0);
let items = vec!['A', 'G', 'C', 'T'];
while !p.is_empty() {
// 每一步拿出距离最远的序列
let node = p.pop().unwrap().0;
let temp = node.inner;
let step = *map.get(&temp).unwrap();
// 查找其可以走到的序列
for i in 0..8 {
for c in &items {
let mut next = temp.clone();
if next[i] == *c { continue; }
next[i] = *c;
if !set.contains(&next) { continue; }
// 在当前序列合法（可以走到的时候）
// 1. 如果走到了终点，那么直接返回结果
if next == end { return step + 1; }
// 2. 没有走到终点，如果曾经没有走过这个序列，或者说走过但是距离要远一些，那么我就进行更新
// 后面一部分算一个剪枝
if !map.contains_key(&next) || *map.get(&next).unwrap() > step + 1 {
let next = set.get(&next).unwrap();
map.insert(next, step+1);
p.push(Reverse(Node::new(next, &end)));
}
}
}
}
-1
}
建图+DFS
既然可以BFS，那就可以DFS，这个不细看了，没什么特别的
class Solution {
int N = 15, M = 15 * 15 * 2 + 50, idx = 0, loc = 1;
int[] he = new int[N], e = new int[M], ne = new int[M];
int n, ans;
void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}
void dfs(int u, int fa, int depth) {
if (depth >= ans) return ; // 最优解剪枝
if (u == n) {
ans = depth;
return ;
}
for (int i = he[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dfs(j, u, depth + 1);
}
}
public int minMutation(String S, String T, String[] bank) {
List<String> list = new ArrayList<>();
list.add(S);
boolean ok = false;
for (String s : bank) {
if (s.equals(S)) continue;
if (s.equals(T)) {
ok = true;
continue;
}
list.add(s);
}
if (!ok) return -1;
list.add(T);
n = list.size();
ans = n;
Arrays.fill(he, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
int cnt = 0;
for (int k = 0; k < 8 && cnt <= 1; k++) {
if (list.get(i).charAt(k) != list.get(j).charAt(k)) cnt++;
}
if (cnt == 1) {
add(i + 1, j + 1); add(j + 1, i + 1);
}
}
}
dfs(1, -1, 0);
return ans == n ? -1 : ans;
}
}
若有收获，就点个赞吧
0 人点赞
