679.24点游戏

链接：679.24点游戏
难度：Hard
标签：数组、数学、回溯
简介：你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

题解 1 - typescript

• 编辑时间：2020-08-22
• 执行用时：1092ms
• 内存消耗：74.7MB
• 编程语言：typescript
• 解法介绍：遍历所有可能创建模板,使用 eval 进行计算。

function judgePoint24(nums: number[]): boolean {
  const numLen = nums.length;
  const op = ['+', '-', '*', '/'];
  const opLen = op.length;
  const set = new Set<number>();
  const getTemplates = (
    num1: number,
    num2: number,
    num3: number,
    num4: number,
    op1: string,
    op2: string,
    op3: string
  ): string[] => {
    return [
      `(${num1}${op1}${num2})${op2}(${num3}${op3}${num4})`,
      `${num1}${op1}(${num2}${op2}${num3}${op3}${num4})`,
      `(${num1}${op1}${num2}${op2}${num3})${op3}${num4}`,
      `${num1}${op1}${num2}${op2}(${num3}${op3}${num4})`,
      `(${num1}${op1}${num2})${op2}${num3}${op3}${num4}`,
      `${num1}${op1}${num2}${op2}${num3}${op3}${num4}`,
    ];
  };
  for (let i1 = 0; i1 < numLen; i1++) {
    const num1 = nums[i1];
    set.add(i1);
    for (let i2 = 0; i2 < numLen; i2++) {
      const num2 = nums[i2];
      if (set.has(i2)) continue;
      set.add(i2);
      for (let i3 = 0; i3 < numLen; i3++) {
        const num3 = nums[i3];
        if (set.has(i3)) continue;
        set.add(i3);
        for (let i4 = 0; i4 < numLen; i4++) {
          const num4 = nums[i4];
          if (set.has(i4)) continue;
          for (let o1 = 0; o1 < opLen; o1++) {
            const op1 = op[o1];
            for (let o2 = 0; o2 < opLen; o2++) {
              const op2 = op[o2];
              for (let o3 = 0; o3 < opLen; o3++) {
                const op3 = op[o3];
                for (const template of getTemplates(num1, num2, num3, num4, op1, op2, op3)) {
                  const comp = eval(template);
                  if (comp > 24 - 6e-10 && comp < 24 + 6e-10) return true;
                }
              }
            }
          }
        }
        set.delete(i3);
      }
      set.delete(i2);
    }
    set.delete(i1);
  }
  return false;
}

题解 2 - typescript

• 编辑时间：2020-08-22
• 执行用时：108ms
• 内存消耗：43.4MB
• 编程语言：typescript
• 解法介绍：回溯算法。

function judgePoint24(nums: number[]): boolean {
  if (nums.length === 1) return nums[0] > 24 - 6e-11 && nums[0] < 24 + 6e-10;
  const len = nums.length;
  const getCopyArr = () => [...nums];
  for (let i = 0; i < len; i++) {
    const num1 = nums[i];
    for (let j = i + 1; j < len; j++) {
      const num2 = nums[j];
      const getArr = (num: number): number[] => {
        const arr = getCopyArr();
        arr.splice(j, 1);
        arr.splice(i, 1);
        arr.push(num);
        return arr;
      };
      if (
        judgePoint24(getArr(num1 + num2)) ||
        judgePoint24(getArr(num1 * num2)) ||
        judgePoint24(getArr(num1 - num2)) ||
        judgePoint24(getArr(num2 - num1)) ||
        judgePoint24(getArr(num1 / num2)) ||
        judgePoint24(getArr(num2 / num1))
      )
        return true;
    }
  }
  return false;
}