广度优先搜索,深度优先搜索 + 贪心算法 + 掩码:求解《691. 贴纸拼词》

2022-05-14 18:38:15

广度优先搜索,深度优先搜索 + 贪心算法 + 掩码,求解《691. 贴纸拼词》

代码模板

多叉树层序遍历

const queue = [root]
let index = 0, distance = 0 // 移动 index 指针,代替数组的 shift() 或拷贝操作,提高性能
while (index < queue.length) {
  distance++
  const length = queue.length
  while (index < length) {
    const node = queue[index] // 拿到节点,distance 就是节点到根节点的距离
    // do something (本题,我们来算空闲时间,并更新最大值)
    index++
    for (const child of node) queue.push(child)
  }
}

例题

691. 贴纸拼词

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ,方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意,你可以多次使用每个贴纸,每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能,则返回 -1 。
注意:在所有的测试用例中,所有的单词都是从 1000 个最常见的美国英语单词中随机选择的,并且 target 被选择为两个随机单词的连接。

答案

广度优先搜索 + 层序遍历
var minStickers = function(stickers, target) {
  const q = [target], visited = new Set() 
  let depth = -1, index = 0
  while (index < q.length) {
    depth++
    for (const l = q.length; index < l; index++) {
      const n = q[index]
      if (n.length === 0) return depth
      for (let i = 0; i < stickers.length; i++) {
        const sticker = stickers[i]
        const cnt = new Uint8Array(26)
        for (let j = 0; j < sticker.length; j++) {
          cnt[sticker.charCodeAt(j) - 97]++
        }
        let a = n.split('')
        for (let j = a.length; j--;) {
          if (cnt[a[j].charCodeAt() - 97]  > 0) {
            cnt[a[j].charCodeAt() - 97]--
            a.splice(j, 1)
          }
        }
        if (a.length === n.length) continue
        const s = a.join('')
        if (visited.has(s)) continue
        visited.add(s)
        q.push(s)
      }
    }
  }
  return -1
};
深度优先搜索 + 贪心算法 + 掩码

贪心策略:每次总是取能改变最多的纸条


var minStickers = function(stickers, target) {
  const n = target.length
  const memo = new Uint8Array(2 ** n)
  const d = mask => {
    if (mask === 0) return 0
    if (memo[mask] > 0) return memo[mask]
    let r = n + 1
    for (let i = 0; i < stickers.length; i++) {
      let left = mask
      const cnt = new Uint8Array(26)
      for (let j = 0; j < stickers[i].length; j++) cnt[stickers[i].charCodeAt(j) - 97]++
      for (let j = 0; j < n; j++) {
        if ((mask & 1 << j) > 0 && cnt[target.charCodeAt(j) - 97] > 0) {
          cnt[target.charCodeAt(j) - 97]--
          left ^= 1 << j
        }
      }
      if (left < mask) r = Math.min(r, d(left) + 1)
    }
    return memo[mask] = r
  }
  const r = d(2 ** n - 1)
  return r > n ? -1 : r
};
function minStickers(stickers: string[], target: string): number {
  const n = target.length
  const memo = new Uint8Array(2 ** n)
  const d = mask => {
    if (mask === 0) return 0
    if (memo[mask] > 0) return memo[mask]
    let r = n + 1
    for (let i = 0; i < stickers.length; i++) {
      let left = mask
      const cnt = new Uint8Array(26)
      for (let j = 0; j < stickers[i].length; j++) cnt[stickers[i].charCodeAt(j) - 97]++
      for (let j = 0; j < n; j++) {
        if ((mask & 1 << j) > 0 && cnt[target.charCodeAt(j) - 97] > 0) {
          cnt[target.charCodeAt(j) - 97]--
          left ^= 1 << j
        }
      }
      if (left < mask) r = Math.min(r, d(left) + 1)
    }
    return memo[mask] = r
  }
  const r = d(2 ** n - 1)
  return r > n ? -1 : r
};
func minStickers(stickers []string, target string) int {
  n := len(target)
  mask := int(math.Pow(2, float64(n))) - 1
  memo := make([]int, mask + 1)
  var d func(mask int) int
  d = func(mask int) int {
    if mask == 0 {
      return 0
    }
    if memo[mask] > 0 {
      return memo[mask]
    }
    r := n + 1
    for _, sticker := range stickers {
      left, cnt := mask, make([]int, 26)
      for _, charCode := range sticker {
        cnt[charCode - 97]++
      }
      for i, charCode := range target {
        if (mask & (1 << i)) > 0 && cnt[charCode - 97] > 0 {
          cnt[charCode - 97]--
          left ^= 1 << i
        }
      }
      if left < mask {
        r = min(r, d(left) + 1)
      }
    }
    memo[mask] = r
    return r
  }
  r := d(mask)
  if r > n {
    return -1
  } else {
    return r
  }
}
func min(a int, b int) int {
  if a < b {
    return a
  }
  return b
}
class Solution {
  private $memo = array(); 
  function minStickers($stickers, $target) {
    $n = strlen($target);
    $this->memo = array_fill(0, 2 ** $n, 0);
    $r = $this->d(2 ** $n - 1, $stickers, $target);
    return $r > $n ? -1 : $r;
  }
  function d($mask, $stickers, $target) {
    if ($mask === 0) return 0;
    if ($this->memo[$mask] > 0) return $this->memo[$mask];
    $n = strlen($target);
    $r = $n + 1;
    foreach($stickers as $sticker) {
      $left = $mask;
      $cnt = array_fill(0, 26, 0);
      for ($i = 0; $i < strlen($sticker); $i++) {
        $cnt[ord($sticker[$i]) - 97]++;
      }
      for ($i = 0; $i < $n; $i++) {
        if (($mask & 1 << $i) > 0 && $cnt[ord($target[$i]) - 97] > 0) {
          $cnt[ord($target[$i]) - 97]--;
          $left ^=  1 << $i;
        }
      }
      if ($left < $mask) {
        $r = min($r, $this->d($left, $stickers, $target) + 1);
      }
    }
    return $this->memo[$mask] = $r;
  }
}

代码
广度优先搜索:求解《675. 为高尔夫比赛砍树》
广度优先搜索,求解《675. 为高尔夫比赛砍树》
代码
广度优先遍历+双端队列:求解《433. 最小基因变化》
广度优先遍历+双端队列,求解《433. 最小基因变化》
代码
反向搜索:深度优先搜索和广度优先搜索,三状态标记法,求解《417. 太平洋大西洋水流问题》
有一种热爱是双向奔赴。反向搜索,深度优先搜索和广度优先搜索,三状态标记法,求解《417. 太平洋大西洋水流问题》