思路
动态规划(TEL)
哈希表

leetcode - 1711. 大餐计数

July 13, 2021

思路

动态规划(TEL)

主要思想为动态规划,对前i道菜能做成大餐的数量为 dp[i], 则对前i + 1道菜能做成大餐的数量为 dp[i+1] = dp[i] + (第i+1道菜和前面i道菜能做大餐的数量)

const remainder = 10 ** 9 + 7;

function countPairs(deliciousness: number[]): number {
  const dp = Array.from(deliciousness).fill(0);

  // 至少两道菜可以做大餐,因此从下标1开始
  for (let i = 1; i < deliciousness.length; i++) {
    let count = 0;
    for (let j = 0; j <= i - 1; j++) {
      if (isPowerOfTwo(deliciousness[j] + deliciousness[i])) {
        count++;
      }
    }

    dp[i] = (dp[i - 1] + count) % remainder;
  }

  console.log(dp);

  return dp[dp.length - 1];
}

function isPowerOfTwo(x: number): boolean {
  // 防御性编程
  if (isNaN(x) || x === 0) {
    return false;
  }

  return (x & (x - 1)) === 0;
}
  • 时间复杂度: $O(n * n)$
  • 空间复杂度: $O(n)$

哈希表

由于给定条件中美味程度上限已知,因此可以对每种菜品A,枚举幂值对B的出现次数,借助哈希表,把每次查询的复杂度优化到 O(1)

const remainder = 10 ** 9 + 7;

function countPairs(deliciousness: number[]): number {
  let map = new Map<number, number>();
  let res = 0;
  for (let food of deliciousness) {
    for (let i = 0; i <= 22; i++) {
      const pair = (1 << i) - food;
      if (pair >= 0 && map.has(pair)) {
        res = (res + map.get(pair)) % remainder;
      }
    }

    map.set(food, (map.get(food) || 0) + 1);
  }

  return res;
}
  • 时间复杂度: $O(n)$
  • 空间复杂度: $O(n)$

feiker 少年起而行之