这题的核心思路很直接偶数直接除以 2奇数时在 n 1 和 n - 1 之间选一个能让后续步骤更少的方向。贪心 位运算推荐class Solution {public int integerReplacement(int n) {long m n;int count 0;while (m ! 1) {if ((m 1) 0) {m 1;} else if (m 3 || (m 3) 1) {m–;} else {m;}count;}return count;}}要点m 1 0偶数直接右移一位相当于 / 2。m 3特殊处理减 1 更优因为 3 - 2 - 1 比 3 - 4 - 2 - 1 少一步。(m 3) 1末尾两位是 01减 1 后能更快出现连续 0优先减。(m 3) 3末尾两位是 11加 1 能产生更多低位 0优先加。用 long 是为了避免 n Integer.MAX_VALUE 时 n 1 溢出。时间复杂度O(log n)空间复杂度O(1)记忆化递归class Solution {MapInteger, Integer memo new HashMap();public int integerReplacement(int n) { if (n 1) return 0; if (!memo.containsKey(n)) { if (n % 2 0) { memo.put(n, 1 integerReplacement(n / 2)); } else { memo.put(n, 2 Math.min( integerReplacement(n / 2), integerReplacement(n / 2 1) )); } } return memo.get(n); }}这里奇数时把 n 1、n - 1 后的下一步 / 2 合并成两次操作所以是 2 min(…)。时间复杂度O(log n)空间复杂度O(log n)面试里如果追求简洁和性能优先写第一种如果想体现递归和剪枝思路可以补上第二种。需要我帮你把这道题和 LeetCode 375猜数字大小放在一起对比说说两道题在状态压缩思路上的异同吗
