计算 24 点组合算法

最近参加了某行业大厂的前端架构师职位面试, 最后的笔试题是计算 24 点的组合算法, 受时间限制, 没有完成, 但是这个题目还是很有意思的, 事后花了一个小时写了一个简单的解法, 本文记录一下详细细节

Leetcode 上有一个类似的题目, 679. 24 点游戏, 难度级别是 Hard 😭

问题描述

和679. 24 点游戏问题几乎完全一样, 给定四个数字, 通过加减乘除, 计算出 24, 返回所有可能的表达式

毫无疑问, 面试题实际要比 Leetcode 上的题目更难一点, 附加的难点在于如何生成所有可能的表达式

679. 24 点游戏 的解法

我们先来看一下 Leetcode 上的题目的解法, 概括一下，通过回溯算法, 来计算所有可能的最终结果, 如果出现 24, 则说明可以得到 24 点, 那回溯的具体逻辑是什么呢？

简而言之, 先任意选出两个数，然后进行四则运算，得到一个新的数，然后把这个新的数和剩下的数再进行四则运算，直到只剩下一个数，然后判断这个数是否等于 24 即可。

参考 Carl 哥的回溯算法模板:

function backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择: 本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果;
    }
}

可以得到代码如下：

function backtracking(nums: number[]): boolean {
  if (nums.length === 1) {
    return Math.abs(nums[0] - 24) < 1e-8;
  }

  const size = nums.length;

  for (let i = 0; i < nums.size; i++) {
    for (let j = 0; j < nums.size; j++) {
      if (i === j) continue;
      const newNums = [];
      for (let k = 0; k < nums.length; k++) {
        if (k !== i && k !== j) {
          newNums.push(nums[k]);
        }
      }

      for (let k = 0; k < 4; k++) {
        if (k < 2 && i > j) {
          continue;
        }
        if (k === 0) {
          newNums.push(nums[i] + nums[j]);
        } else if (k === 1) {
          newNums.push(nums[i] * nums[j]);
        } else if (k === 2) {
          newNums.push(nums[i] - nums[j]);
        } else {
          if (nums[j] !== 0) {
            newNums.push(nums[i] / nums[j]);
          } else {
            continue;
          }
        }
        if (backtracking(newNums)) {
          return true;
        }
        newNums.pop();
      }
    }
  }
  return false;
}

算法解析

接下来，我们详细拆解一下代码的逻辑，其实只需要对应上面的回溯算法描述即可：

先任意选出两个数，然后进行四则运算，得到一个新的数，然后把这个新的数和剩下的数再进行四则运算，直到只剩下一个数，然后判断这个数是否等于 24 即可。:::

1.先任意选出两个数

对应代码片段如下：

  for(let i = 0; i < nums.size; i++) {
    for(let j = 0; j < nums.size; j++) {
      if (i === j) continue;
      ...
    }
  }

因为数字不可以复用，所以需要两层循环，i 和 j 不能相等(i === j 说明选到了同一个数字)

2.然后进行四则运算，得到一个新的数

对应代码片段如下：

for (let k = 0; k < 4; k++) {
  if (k < 2 && i > j) {
    continue;
  }
  if (k === 0) {
    newNums.push(nums[i] + nums[j]);
  } else if (k === 1) {
    newNums.push(nums[i] * nums[j]);
  } else if (k === 2) {
    newNums.push(nums[i] - nums[j]);
  } else {
    if (nums[j] !== 0) {
      newNums.push(nums[i] / nums[j]);
    } else {
      // 除数不能为0
      continue;
    }
  }
  ...
}

这里的 k 代表四则运算符号，0 代表加法，1 代表乘法，2 代表减法，3 代表除法

以下代码片段和剪枝优化有关，加法和乘法满足交换律，所以当 k < 2 (加法/乘法) && i > j 时，不需要重复计算，因为 nums[i] + nums[j] 和 nums[j] + nums[i] 是一样的

举个例子：nums = [1,2,3,4], i = 1, j = 2, k = 0, 也就是 nums[1] + nums[2]，继续迭代，当 i = 2, j = 1, k = 0, 也就是 nums[2] + nums[1]，这两个结果是一样的，所以不需要重复计算

if (k < 2 && i > j) {
  continue;
}

3.然后把这个新的数和剩下的数再进行四则运算

以下代码是收集没有选中的数字, 创建一个新的数组来存储

const newNums = [];
for (let k = 0; k < nums.length; k++) {
  if (k !== i && k !== j) {
    newNums.push(nums[k]);
  }
}

4.再进行四则运算，直到只剩下一个数

这句话实际上就是描述了回溯的递归逻辑, 对应代码片段如下：

if (backtracking(newNums)) {
  // 递归
  return true;
}
newNums.pop(); // 撤销处理结果

处理节点; 这个步骤实际上就是 newNums.push(nums[i] + nums[j])，撤销处理结果 就是 newNums.pop()，这里的 backtracking(newNums) 就是递归的过程

5.然后判断这个数是否等于 24 即可

这一步就是判断递归的终止条件, 模版片段如下：

    if (终止条件) {
        存放结果;
        return;
    }

对应代码片段如下：

if (nums.length === 1) {
  return Math.abs(nums[0] - 24) < 1e-8;
}

至此

const OPERATORS = {
  '+': 1,
  '-': 1,
  '*': 1,
  '/': 1,
};

// 表达式树
class ExpressionTreeNode {
  left?: ExpressionTreeNode;
  right?: ExpressionTreeNode;
  val: number | string;
  constructor(val: number | string) {
    this.val = val;
  }

  toString(): string {
    function traverse(root: ExpressionTreeNode | undefined, list: string[]) {
      if (root === undefined) {
        return;
      }
      if (root.left && root.right) {
        list.push('(');
      }
      traverse(root.left, list);
      list.push(root.val.toString());
      traverse(root.right, list);
      if (root.left && root.right) {
        list.push(')');
      }
    }

    const result: string[] = [];
    traverse(this, result);
    result.pop();
    result.shift();
    return result.join('');
  }
}

// 转换成中缀表示
function toInfixString(tokens: string[] | string): string {
  if (typeof tokens === 'string') {
    tokens = tokens.split('');
  }

  let stack = [];
  let str = [];
  for (let c of tokens) {
    if (c in OPERATORS) {
      const right = stack.pop();
      const left = stack.pop();
      const node = new ExpressionTreeNode(c);
      node.right = right;
      node.left = left;
      stack.push(node);
    } else {
      stack.push(new ExpressionTreeNode(c));
    }
  }
  const root = stack.pop()!;
  return root.toString();
}

// 对逆波兰式求值
function evalRPN(tokens: string[] | string): number {
  if (typeof tokens === 'string') {
    tokens = tokens.split('|');
  }
  console.log('tokens', tokens);
  let stack = [];
  let str = [];
  for (let c of tokens) {
    if (c in OPERATORS) {
      const operand2 = stack.pop();
      const operand1 = stack.pop();
      const result = eval(`${operand1}${c}(${operand2})`);
      stack.push(result);
    } else {
      stack.push(c);
    }
  }
  return stack.pop();
}

interface Path {
  paths: [number | Path, string, number | Path];
  num: number;
}

const Operators = ['+', '*', '-', '/'];

const TARGET = 24;
const DIFF = 10 ** -6;

function isTarget(exp: number | string) {
  if (typeof exp === 'number') {
    return false;
  }
  return Math.abs(evalRPN(exp) - TARGET) < DIFF;
}

function judgePoint24(cards: number[]): boolean {
  const solutions: string[] = [];
  function backtracking(nums: Array<string | number>) {
    const size = nums.length;
    if (size === 1) {
      // 计算式已经组合完成
      if (isTarget(nums[0])) {
        // 结果为24点
        solutions.push(nums[0] as string);
      }
      return;
    }

    for (let i = 0; i < size; i++) {
      for (let j = 0; j < size; j++) {
        // 选出card[i], card[j]先进行计算
        if (i !== j) {
          //  数字不可以重复使用
          const newList: Array<string | number> = [];
          // 把剩余的数加入新的数组做递归
          for (let k = 0; k < size; k++) {
            if (k !== i && k !== j) {
              newList.push(nums[k]);
            }
          }

          // 四则运算做递归
          Operators.forEach((op) => {
            // 使用逆波兰式可以隐含括号
            const rpn = `${nums[i]}${nums[j]}${op}`;
            newList.push(rpn);
            // 递归
            backtracking([...newList]);
            // 回溯
            newList.pop();
          });
        }
      }
    }
  }

  backtracking(cards);
  solutions.forEach((solution) => {
    console.log(toInfixString(solution));
  });
  return solutions.length > 0;
}

测试链接