数学

Pow(x, n)

API：math.pow
循环：循环 1~n，不断累计
二分法：当 n 为偶数时 x^n =(x^(n/2))^2；当 n 为奇数时 x^n=(x(n/2))^2 * x（javascript 需要取整）

递归

function myPow(x: number, n: number): number {
  // n可能为负数
  let isNegative = false;
  if (n < 0) {
    isNegative = true;
    n = -n;
  }
  const result = handle(x, n);
  return isNegative ? 1 / result : result;
}

function handle(x: number, m: number): number {
  // 对 n 进行二分，例如 x^15 ==>
  // (x^7)^2 * x ==> ((x^3)^2 * x)^2 * x ===> (((x^1)^2*x)^2 * x)^2 * x
  // 即每分出一个奇数，则原先的值必须多乘以一个x
  if (m === 0) return 1;
  const handleResult: number = handle(x, Math.trunc(m / 2));
  return m & 1 ? handleResult * handleResult * x : handleResult * handleResult;
}

迭代 $n = 2^i0 + 2^i1 + 2^i2 + ...$ 可推导出 $x^n = x^{2^i0} * x^{2^i1} * x^{x^i2} * ...$

// 则可以根据 当前二进制数是否为0来判定是否需要相乘
// 假设二进制位全部为1，则最后一位是 x^1 * x^2 * x^4 * x^8 * ...，是成平方形式增长

function myPow(x: number, n: number): number {
  // n可能为负数
  let isNegative = false;
  if (n < 0) {
    isNegative = true;
    n = -n;
  }

  let result = 1;
  let prevResult = x;
  while (n > 0) {
    // 等于1时，需要多乘以一个x
    if (n & 1) {
      result *= prevResult; // 如果此处二进制为1，则表示需要加入result
    }
    prevResult *= prevResult; // 不断平方增加
    n = Math.trunc(n / 2); // 位运算可能超出32位有符号整型限制
  }

  return isNegative ? 1 / result : result;
}

基本计算器 II

字符串转换为计算，例如 “1 * 3 + 2”

function calculate(s: string): number {
  /**
   * 1. 识别数字，可能存在多位数字
   * 2. 识别符号，识别 + - * \
   * 3. 判断优先级
   *    - 由于不存在括号，则无序使用栈来存储括号
   *    - 分两次计算，先计算乘除；再计算加减
   */
}

可被 5 整除的二进制前缀

给出一个数组，作为二进制的每一位，判断第 i 位时，由[0,i] 组成的二进制是否可以整除以 5

暴力法：将每个二进制算一遍
动态规划（计算尾数）：由于只有尾数位 0、5 的数能被 5 整除，则记录尾数（个位数）即可
1. 每次移动一位时，即表示实际的值向左移一位
2. 如果移动后的值为 1，则还需要加 1
3. 保存个位数，则可以防止溢出

function prefixesDivBy5(A: number[]): boolean[] {}

平方数之和

function judgeSquareSum(c: number): boolean {
  /**
   * 穷举1：将范围内所有平方数记录下来：使用贪心算法从大到小计算
   *
   * 穷举2：从 c 的平方根开始枚举
   *
   * 数学：一个非负整数 c 如果能够表示为两个整数的平方和，当且仅当 c 的所有形如 4k + 3 的质因子的幂均为偶数
   */
}

笨阶乘

function clumsy(n: number): number {
  /**
   * 优于数学运算存在优先级，则按照优先级计算即可，以四个数为一集合，再以减法
   *
   * 1. 遍历优化：其中最关键的即使计算是否进位：x * (x-1) / (x-2) 其中最大值为6，即 x=3、x=4时，其余情况一律等于x+1
   * 2. 数学
   */
}

4 的余数

位运算：如果该数可以余除 4，则必然可以换算为 2^n，则这个数一定是如下的模式 100、10000、100100...，按照这种形式进行位运算

汉明距离总和

function totalHammingDistance(nums: number[]): number {
  /*
   * 32次循环：按照数字的位来计算，N个数，第M位存在不同的有K个，那么此位的汉明距离和为 K-1+K-2+K-3+...1 ==> K*(K-1)
   */
}

可被 K 整除的最小整数

function smallestRepunitDivByK(k: number): number {
  /*
   * 暴力法：
      1. 尾数：位数为1的只有如下乘法: 1*1、3*7、9*9
      2. 进位：假设进位此时为2，按照乘法原则个位、十位、百位的拼凑

     利用数组保存99乘法表，来进行拼凑
   */
}