每日一题 —— 混杂整数序列按规则进行重新排序

背景:

假设我们取一个数字 x 并执行以下任一操作：

• a:将 x 除以 3 (如果可以被 3 除)
• b:将 x 乘以 2

每次操作后，记下结果。如果从 9 开始，可以得到一个序列

有一个混杂的整数序列，现在任务是对它们重新排序，以使其符合上述序列并输出结果

示例:

输入: "[4,8,6,3,12,9]"
输出: [9,3,6,12,4,8]

解释: [9,3,6,12,4,8] => 9/3=3 -> 3*2=6 -> 6*2=12 -> 12/3=4 -> 4*2=8

输入: "[3000,9000]"
输出: [9000,3000]

输入: "[4,2]"
输出: [2,4]

输入: "[4,6,2]"
输出: [6,2,4]

人话翻译: 对数组重新排序，使得数组每一项可以满足这样一个规则：arr[i] = arr[i + 1] * 3 或者 arr[i] = arr[i + 1] / 2

解法:

function changeArr(arr) {
  const map = new Map();
  let find = false;
  let ret;
  arr.forEach((n) => {
    map.set(n, (map.get(n) || 0) + 1); // 定义数组中一个数剩余的次数
  });
  arr.forEach((n) => {
    if (find) return;
    dfs(n, 2, [n]);
  });

  function dfs(prev, index, res) {
    if (find) return;
    if (index === arr.length + 1) {
      // 找完了，退出搜索
      find = true;
      ret = res;
    }
    if (map.has(prev * 2) && map.get(prev * 2) > 0) {
      // 数组中有上个值 *2 的数据存在
      map.set(prev * 2, map.get(prev * 2) - 1);
      dfs(prev * 2, index + 1, [...res, prev * 2]); // 将这个值加到结果中，并
      map.set(prev * 2, map.get(prev * 2) + 1); // 没有找到，把次数加回来
    }
    if (!(prev % 3) && map.get(prev / 3) > 0) {
      // 当前值能被3整数并且被3整数的值存在
      map.set(prev / 3, map.get(prev / 3) - 1);
      dfs(prev / 3, index + 1, [...res, prev / 3]);
      map.set(prev / 3, map.get(prev / 3) + 1); // 没有找到，把次数加回来
    }
  }
  return ret;
}

来自: 2年前端,如何跟抖音面试官battle