397. 整数替换 - 力扣LeetCode397. 整数替换 - 给定一个正整数 n 你可以做如下操作 1. 如果 n 是偶数则用 n / 2替换 n 。 2. 如果 n 是奇数则可以用 n 1或n - 1替换 n 。返回 n 变为 1 所需的 最小替换次数 。 示例 1输入n 8输出3解释8 - 4 - 2 - 1示例 2输入n 7输出4解释7 - 8 - 4 - 2 - 1或 7 - 6 - 3 - 2 - 1示例 3输入n 4输出2 提示 * 1 n 231 - 1https://leetcode.cn/problems/integer-replacement/题目描述给定一个正整数n我们可以执行两种操作如果n是偶数n n / 2如果n是奇数可以选择n n 1或者n n - 1求把n变为 1 需要的最少替换次数。数据范围1 n 2^31 - 1需要注意 int 溢出问题。核心思路贪心 二进制位运算偶数没有选择只能直接除以 2对应二进制右移一位消除末尾的 0。 难点在于奇数奇数只能 1 或者 - 1我们贪心选择操作后能产生更多末尾 0的方案末尾 0 越多后续可以连续除 2步数更少。奇数二进制最后一位一定是 1我们看最后两位末两位01n % 4 1执行n-1直接消除末尾 1得到末尾两个 0可以连续两次除 2。末两位11n % 4 3执行n1发生进位连续把一串 1 全部变成 0一次性消除多个低位 1。⚠️特殊特例 n 3二进制 11按照上面规则11应该 1 变成 4路径3→4→2→1需要 3 步 但3-12路径3→2→1只需要 2 步更优。所以必须单独判断n 3强制走n-1。class Solution { public: int integerReplacement(int n1) { int count0; long long nn1; while(n!1) { if(n%20) nn/2; else{ if(n3) n-1; else if((n (1 1)) ! 0)//判断二进制次低位是不是1末两位11 n1; else n-1; } count; } return count; } };