Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 397. Integer Replacement

---

題目：


方法：

如果 n == 3 => 一定選 n - 1

否則：
    看 n 的最後兩個 bit
    - 如果 n % 4 == 1 => 做 n - 1
    - 如果 n % 4 == 3 => 做 n + 1

解答：

class Solution {
public:
    int integerReplacement(int n) {
        long x = n;
        int ans = 0;

        while (x != 1) {
            if (x % 2 == 0) {
                x >>= 1;
            }
            else {
                if (x == 3 || x % 4 == 1) {
                    x -= 1;
                }
                else {
                    x += 1;
                }
            }
            ans += 1;
        }

        return ans;
    }
};