数位操作

如何逐位取出整数的各位数字？

• 取末位: x % 10;
• 去掉末位: Math.floor(x / 10);
• 循环: 直到 x 归零, 依次得到从低位到高位的各位数字;

const digits = [];
while (x > 0) {
  digits.push(x % 10); // 从低位到高位
  x = Math.floor(x / 10);
}

• 顺序: 取出的顺序是从低位到高位, 需要高位优先时最后反转;

整数反转为什么必须处理溢出？

• 目标: 反转整数各位, 结果超出 32 位有符号范围时返回 0;
• 溢出边界: 正数上限 $2^{31} - 1$, 负数下限 $-2^{31}$;
• 判定时机: 累加下一位之前先判断 res 是否已经超过 (max - digit) / 10, 避免先乘后判导致精度丢失;
• 符号处理: 先取绝对值与符号位, 反转后再乘回符号;

const reverse = (x) => {
  const sign = Math.sign(x);
  let rest = Math.abs(x);
  const digits = [];
  while (rest > 0) {
    digits.push(rest % 10);
    rest = Math.floor(rest / 10);
  }

  const max = Math.pow(2, 31);
  let res = 0;
  for (const digit of digits) {
    if (res > (max - digit) / 10) return 0; // 提前判溢出
    res = 10 * res + digit;
  }
  return sign * res;
};

• 复杂度: 时间 $O(\log x)$, 空间 $O(\log x)$;

如何判断一个整数是回文数？

• 预处理: 负数一定不是回文数, 直接返回 false;
• 思路: 取出各位数字后用双指针从两端向中间比较;
• 等价写法: 只反转后半部分再与前半部分比较, 可省下数组;

const isPalindrome = (x) => {
  if (x < 0) return false;
  const digits = [];
  while (x > 0) {
    digits.push(x % 10);
    x = Math.floor(x / 10);
  }
  let left = 0;
  let right = digits.length - 1;
  while (left < right) {
    if (digits[left] !== digits[right]) return false;
    left++;
    right--;
  }
  return true;
};

• 复杂度: 时间 $O(\log x)$, 空间 $O(\log x)$;

第 N 位数字如何定位到具体数字？

• 规律: 1 位数有 9 个、2 位数有 90 个、$d$ 位数有 $9 \times 10^{d-1}$ 个;
• 第一步: 逐位长度累减 n, 确定第 n 位落在几位数的区间内;
• 第二步: start + Math.floor((n - 1) / digit) 求出所在的具体数字;
• 第三步: (n - 1) % digit 求出在该数字中的下标;

const findNthDigit = (n) => {
  let start = 1; // 当前位数区间的起始数字
  let digit = 1; // 当前位数
  let count = 9; // 当前位数区间的数字个数
  while (n > digit * count) {
    n -= digit * count; // 跳过整个区间
    start *= 10;
    digit += 1;
    count *= 10;
  }
  const num = start + Math.floor((n - 1) / digit);
  return Number(String(num)[(n - 1) % digit]);
};

• 复杂度: 时间 $O(\log n)$, 空间 $O(1)$;
• 易错点: 三个变量必须同步更新, 漏掉任一个都会算错区间起点;

Excel 表列名称如何做 26 进制转换？

• 差异: Excel 列名从 A 开始计数而非从 0, 所以每位都要先减 1 消除偏移;
• 实现: 循环取 columnNumber - 1 对 26 的余数作为字母下标, 再整除 26;

const convertToTitle = (columnNumber) => {
  const startCode = "A".charCodeAt(0);
  const res = [];
  while (columnNumber) {
    columnNumber--; // 消除 1 基偏移
    res.unshift(String.fromCharCode(startCode + (columnNumber % 26)));
    columnNumber = Math.floor(columnNumber / 26);
  }
  return res.join("");
};

• 复杂度: 时间 $O(\log_{26} n)$, 空间 $O(\log_{26} n)$;
• 关联 API: String.prototype.charCodeAt 与 String.fromCharCode;