397. 整数替换-leetcode

给定一个正整数 n，你可以做如下操作：

1. 如果 n 是偶数，则用 n / 2替换 n。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。
   n 变为 1 所需的最小替换次数是多少？

示例 1:

输入:

8

输出:

3

解释:

8 -> 4 -> 2 -> 1

示例 2:

输入:

7

输出:

4

解释:

7 -> 8 -> 4 -> 2 -> 1

或

 -> 6 -> 3 -> 2 -> 1

---

这个题目其实就是用到递归了,leetcode归类到了位运算，可是我没想到位运算怎么解决。

就是需要注意

n = Int.max

不能加一，只能减一

class Solution {
    func integerReplacement(_ n: Int) -> Int {
        if n == 1 {
            return 0
        }
        if n & 0b1 == 0 {
            return integerReplacement(n >> 1) + 1
        } else if (n == Int.max) {
            return integerReplacement(n - 1) + 1
        }
        
        return min(integerReplacement(n - 1),integerReplacement(n + 1)) + 1
    }
}