397.整数替换

链接：397.整数替换
难度：Medium
标签：贪心、位运算、记忆化搜索、动态规划
简介：给定一个正整数 n ，n 变为 1 所需的最小替换次数是多少？。

题解 1 - typescript

• 编辑时间：2021-11-19
• 执行用时：80ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：dfs。

const map: Record<number, number> = { 1: 0 };
function integerReplacement(n: number): number {
  if (map[n] !== undefined) return map[n];
  const ans =
    (n & 1
      ? Math.min(integerReplacement(n + 1), integerReplacement(n - 1))
      : integerReplacement(n / 2)) + 1;
  return (map[n] = ans);
}