广度优先遍历+双端队列,求解《433. 最小基因变化》

Java 比较字符串相等

==: 比较字符串基本类型的值,或者字符串对象的引用是否相等
String.equals(equals): 比较内容是否相等

例题

433. 最小基因变化

基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
例如,"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化,只有基因库中的基因才是有效的基因序列。
给你两个基因序列 start 和 end ,以及一个基因库 bank ,请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化,返回 -1 。
注意:起始基因序列 start 默认是有效的,但是它并不一定会出现在基因库中。

答案

广度优先搜索 + 双端队列

var minMutation = function(start, end, bank) {
  const queue = [start], banks = new Set(bank)
  let depth = 0, index = 0
  while (index < queue.length) {
    let l = queue.length
    depth++
    while (index < l) {
      const n = queue[index++]
      for (let i = 0; i < 8; i++) {
        for (const char of ['A', 'C', 'G', 'T']) {
          const next = n.slice(0, i) + char + n.slice(i + 1)
          if (banks.has(next) === false) continue
          if (next === end) return depth
          banks.delete(next)
          queue.push(next)
        }
      }
    }
  }
  return -1
};
function minMutation(start: string, end: string, bank: string[]): number {
  const queue = [start], banks = new Set(bank)
  let depth = 0, index = 0
  while (index < queue.length) {
    let l = queue.length
    depth++
    while (index < l) {
      const n = queue[index++]
      for (let i = 0; i < 8; i++) {
        for (const char of ['A', 'C', 'G', 'T']) {
          const next = n.slice(0, i) + char + n.slice(i + 1)
          if (banks.has(next) === false) continue
          if (next === end) return depth
          banks.delete(next)
          queue.push(next)
        }
      }
    }
  }
  return -1
};
func minMutation(start string, end string, bank []string) int {
  queue, banks  := []string{start}, map[string]struct{}{}
  for _, b := range bank {
    banks[b] = struct{}{}
  }
  index, depth, chars := 0, 0, []string{"A", "C", "G", "T"}
  for index < len(queue) {
    l := len(queue)
    depth++
    for index < l {
      n := queue[index]
      index++
      for i := 0; i < 8; i++ {
        for _, char := range chars {
          next := n[:i] + char + n[i + 1:]
          if _, ok := banks[next]; ok {
            if next == end {
              return depth
            }
            queue = append(queue, next)
            delete(banks, next)
          }
        }
      }
    }
  }
  return -1
}
class Solution {
    function minMutation($start, $end, $bank) {
      $queue = [$start];
      $banks = array_flip($bank);
      $depth = $index = 0;
      while ($index < count($queue)) {
        $length = count($queue);
        $depth++;
        while ($index < $length) {
          $n = $queue[$index++];
          for ($i = 0; $i < 8; $i++) {
            foreach (['A', 'C', 'G', 'T'] as $char) {
              $next = substr($n, 0, $i) . $char . substr($n, $i + 1);
              if (array_key_exists($next, $banks)) {
                if ($next === $end) return $depth;
                unset($banks[$next]);
                $queue []= $next;
              }
            }
          }
        }
      }
      return -1;
    }
}
class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        queue, banks, depth, index = deque([start]), set(bank), 0, 0
        while index < len(queue) :
          l = len(queue)
          depth += 1
          while index < l:
            n = queue[index]
            index += 1
            for i in range(0, 8):
              for char in 'ACGT':
                next = n[:i] + char + n[i + 1:]
                if next in banks:
                  if next == end: return depth
                  banks.remove(next)
                  queue.append(next)
        return -1
class Solution {
  public int minMutation(String start, String end, String[] bank) {
    Queue<String> queue = new ArrayDeque<String>();
    HashSet<String> banks = new HashSet<String>();
    for (String b : bank) banks.add(b);
    queue.offer(start);
    int depth = 0;
    String ds = "ACGT";
    while (queue.isEmpty() == false) {
      int l = queue.size();
      depth++;
      while (l-- > 0) {
        String n = queue.poll();
        for (int i = 0; i < 8; i++) {
          for (int j = 0; j < 4; j++) {
            StringBuffer sb = new StringBuffer(n);
            sb.setCharAt(i, ds.charAt(j));
            String next = sb.toString();
            if (banks.contains(next)) {
              if (end.equals(next)) return depth;
              banks.remove(next);
              queue.offer(next);
            }
          }
        }
      }
    }
    return -1;
  }
}

代码
广度优先搜索,深度优先搜索 + 贪心算法 + 掩码:求解《691. 贴纸拼词》
广度优先搜索,深度优先搜索 + 贪心算法 + 掩码,求解《691. 贴纸拼词》
代码
双端队列:求解《933. 最近的请求次数》
双端队列,求解《933. 最近的请求次数》
代码
哈希表、队列、约瑟夫环的迭代和递归,动态规划求解《1823. 找出游戏的获胜者》和《剑指 Offer 62. 圆圈中最后剩下的数字》
哈希表、队列、递归、迭代,用约瑟夫环的递推公式,求解《1823. 找出游戏的获胜者》和《剑指 Offer 62. 圆圈中最后剩下的数字》