[数据结构与算法]面试算法记录＜并查集、回溯+剪枝＞

这两个月都在面试，算法方面，字节问的最多，不过都不难，虾皮问了一个最难的，腾讯没有问算法，其他公司问的都比较简单，这里简单记录一下两道个人觉得有点难度的。

1.字节算法题

题目：已知有如下的结构，表示商品编号及对应的价格，给定金额mount,求所有可能的商品组合使得刚好用完mount。

这题和排列组合有点像，不过更复杂一点。涉及到所有组合，大概率都是需要回溯的，这里利用排序再剪枝以降低复杂度。

const list = [
  {
    id: 1,
    price: 5,
  },
  {
    id: 2,
    price: 20,
  },
  {
    id: 3,
    price: 3,
  },
  {
    id: 4,
    price: 8,
  },
  {
    id: 5,
    price: 6,
  },
];

代码：

const getGroups = (list, mount) => {
  list.sort((a, b) => a.price - b.price); //先排序
  const res = [];
  const l = list.length;
  const cur = [];
  const handle = (index = 0, preSum = 0) => {
    if (preSum === mount) {
      res.push(cur.slice());
      return;
    }
    for (let i = index; i < l; i++) {
      if (preSum + list[i].price > mount) break; //剪枝
      cur.push(list[i]);
      handle(i + 1, preSum + list[i].price);
      cur.pop();
    }
  };
  handle();
  return res;
};

2.虾皮算法题

虾皮问的是一道并查集的。

给定一个字符串列表，有相同字符的单词可以合并，输出合并之后的字符串列表。

算是并查集的经典案例

思路就是，记录每个字符对应的下标，(注意是字符不是单词)，为了方便，转换成ascII编码-97，用数组存储。

然后遍历字符串，遍历每一个字符，判断当前字符串的字符是否指向其他单词，有的话说明要和其他单词合并，所以所有字符都指向目标字符。没有的话该单词的字符都指向第一个字符。

之后就是重新遍历单词，每个字符都映射为目标字符，用map记录，然后合并就好了

const arr = ["ac", "bc", "ed", "sf", "hi", "ae", "ab"];
const group = (arr) => {
  const stringList = new Array(26).fill(0).map((item, index) => index);
  const findNumber = (v) => {
    while (stringList[v] !== v) {
      v = stringList[v];
    }
    return v;
  };
  arr.forEach((item) => {
    const t = [].find.call(item, (s) => {
      const code = s.charCodeAt() - 97;
      return stringList[code] !== code;
    });
    const target = t || item[0];
    const targetIndex = findNumber(stringList[target.charCodeAt() - 97]);
    for (const s of item) {
      const code = s.charCodeAt() - 97;
      const last = findNumber(code);
      stringList[last] = targetIndex;
    }
  });
  const map = new Map();
  for (const item of arr) {
    for (const s of item) {
      const code = s.charCodeAt() - 97;
      const target = findNumber(code);
      if (!map.has(target)) {
        map.set(target, new Set(s));
      } else {
        map.get(target).add(s);
      }
    }
  }
  return [...map.values()].map((item) => [...item].join(""));
};