2044. 统计按位或能得到最大值的子集数目

还是先从简单地一题看起，首先是暴力做法，使用了状态压缩，但是是暴力遍历
image.png
注意点：

  1. 位运算中，mask的第k位标记了选中的子集，为1表示选中，并进行或运算

  2. 在把mask移动了nums长度位之后，得到的就是所有可能的情况，比如3个元素的情况，我给到一个mask为1<<3就可以描述所有子集情况：001,000,111,101,110...

    1. pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
    2.  let n = nums.len();                     
    3.  // n代表了集合中的数量，也即对集合中的元素进行标记，第1个元素由第一位标识
    4.  let mask = 1<<n;
    5.  let (mut res, mut max) = (0, 0);
    6.  // 关键来了，对于这么一个n长度的集合来说，其所有的子集转换为1的位置
    7.  // 而从0..mask表示了集合中所有的子集情况
    8.  for x in 0..mask {
    9.      let mut cur = 0;
    10.      // 当前子集下的所有元素进行取或
    11.      for j in 0..n {
    12.          // 如果子集中j号元素存在，那么就试或
    13.          if (x >> j) & 1 == 1 { cur |= nums[j]; }
    14.      }
    15.      if cur > max { 
    16.          max = cur;
    17.          res = 1;
    18.      }else if cur == max { res += 1; }
    19.  }
    20.  res
    21. }

    优化为DP

    image.png
    我们优化的目的是优化第二层for，因为对于每一个子集实际上我们进行了一次从头到尾的计算，这显然是一种浪费，比如求011情况，必然是从010过来的，我们使用一个数组记录010的情况，然后查询010时刻的或的值，再将其与001也即第一个元素取或就可以快速得到011的值。那么我们还可以推测到的是：100 -> 110 -> 111
    下一个问题就是，如何快速之后最后面的一个1，其对应的是nums中的哪个元素？
    这样我们就通过一个map来进行存储，快速获取到对应的元素位置，获取到元素值，然后进行状态的递推。

    1. /// 状压dp，优化，usize和i32的处理需要很细心才行
    2. pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
    3.  use std::collections::HashMap;
    4.  // 存储每一个字节标识位对应的nums中的元素的位置
    5.  let mut location = HashMap::new();
    6.  (0..nums.len()).for_each(|i| { location.insert((1 << i), i); });
    8.  let mask :usize = 1 << nums.len();
    9.  let mut dp = vec![0; mask];
    10.  let (mut res, mut max) = (0, 0);
    11.  (1..mask).for_each(|i| {
    12.      // 获取当前情况的最低位，i从1开始因为空集没有意义,i代表了所有的集合可能
    13.      let k = i as i32;
    14.      let low_bit = k & (-k);
    15.      let prev = (k - low_bit) as usize;
    16.      dp[i] = dp[prev] | nums[*location.get(&low_bit).unwrap()];
    17.      if dp[i] > max  {
    18.          max = dp[i];
    19.          res = 1;
    20.      }else if dp[i] == max { res += 1; }
    21.  });
    22.  res
    23. }

    优化为DFS

    image.png
    这里解决的问题也是第二个for，因为我们暴力做法是寻找所有子集情况然后进行求或获得值，除了使用DP记录前述状态来进行优化外，还可以使用树来进行优化，实际上，dp的思路展开了也很像树。

    pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
 // dfs求解，对于集合中的每一个数，获取子集无非就是当前元素取或者不取两种情况
 // n代表遍历到第几个元素，val代表此时的值，max为预期的最大值，res最大值数量
 fn dfs(nums: &Vec<i32>, n: usize, val: i32, max: &mut i32, res: &mut i32) {
     if n == nums.len() {
         if val > *max {
             *max = val;
             *res = 1;
         }else if val == *max { *res += 1; }
         return;
     }
     dfs(nums, n + 1, val, max, res);
     dfs(nums, n + 1, val | nums[n], max, res);
 }
 let (mut res, mut max) = (0, 0);
 dfs(&nums, 0, 0, &mut max, &mut res);
 res
}

    1125. 最小的必要团队

    字节的笔试有一道类似的，讲的是集换卡，知道n个集换卡，形式为：**"000"**, **"111"**, **"222"**, **"345"**, **"678"**, **"891"**求最少需要多少个才可以凑齐1..=9的集换卡
    字节这题就是简化的最小必要团队，在编码上简化了一些，直接给定了需要的范围，同时对于每一个可选的“候选人”来说，字节这题也是框定了3的长度。

这一题可以转换为上面的一题，注意两个注意点。我们有一个目标的集合，这个集合是要求的技术栈，另一个集合是用户集合，包含了用户拥有的所有的技术。第一个注意点是，对于我们需要的目标技术栈的集合，其中的每一个子集可以通过mask的方法进行表示，那么问题就可以转换为当前技术栈要求，为上一个技术栈要求的传递，此为dp的传递性与无后效性达成了；第二个注意点，不管应聘者的技术栈为啥，都可以编码为一个整数，其中的位置标记了技术。

定义DP[i] 为当前i (001,100)二进制情况下表示的技术栈要求情况下的，最小适配用户集合，定义skills[i]代表用户i的技术栈编码，对于需求技术栈为i：

  1. 如果DP[i].len == 0意味着当前情况，没有候选者，直接跳过。代码中，只是大于1的时候才跳过，避免了初始化失败的情况，在大于1的情况下，如果需求为i的情况下没有候选者的话，说明当前情况要么没有递推到，要么是不可达。也即，其实这里的dp不是常规的**1..=n**的递推。
  2. 假设选择当前用户j那么此时的技术栈总量为i | skills[j]，即事实上的下一个状态其实为DP[i | skills[j]]而不是DP[i+1]：
    1. 如果包含了此用户的技术栈的最小适配用户组为空DP[i | skills[j]] == null
    2. 如果包含了此用户的技术栈的最小适配用户组的大小比我把他加入目前的候选集中用户数更大DP[i | skills[j]].len > DP[i].len + 1

这两种情况下进行更新，自然是更新DP[i | skills[j]]为原本的DP[i]的集合加 上这个数。

/// 1125. 最小的必要团队
/// 状态压缩dp经典题目
pub fn smallest_sufficient_team(req_skills: Vec<String>, people: Vec<Vec<String>>) -> Vec<i32> {
    use std::collections::HashMap;
    // 状态压缩,首先是需要的技术栈的编码,使得可以通过打表得到需求技术的对应编码
    let mut map = HashMap::new();
    (0..req_skills.len()).for_each(|i| { map.insert(req_skills[i].clone(), i); });
    let mut skills = Vec::with_capacity(people.len());
    people.into_iter().for_each(|ones| {
        let mut mask = 0;
        ones.into_iter().for_each(|skill| {
            let idx = *map.get(&skill).unwrap();
            mask |= 1 << idx;
        });
        skills.push(mask);
    });
    println!("{:?}", skills);

    // 定义dp为技术栈为i情况下的最小用户集合,使用下标存储
    let all = 1<<req_skills.len();
    let mut dp = vec![Vec::new(); all];
    (0..all).for_each(|i| {
        if i > 0 && dp[i].len() == 0 {
            ()  // 还是不能单独作为continue使用
        }else {
            for j in 0..skills.len() {
                if skills[j] == 0 { continue; }
                let next = i | skills[j];
                if dp[next].len() == 0 || dp[next].len() > dp[i].len() + 1 {
                    dp[next] = dp[i].clone();
                    dp[next].push(j);
                }
            }
        }
    });
    dp[all - 1].iter().map(|i| *i as i32).collect::<Vec<i32>>()
}