【LeetCode每日一题】397. 整数替换【中等】

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

如果 n 是偶数，则用 n / 2替换 n 。 如果 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 - 1

题解： 本题我采用了BFS的解法，特判了整数取最大的情况。

//写得有一点丑
class Solution {
public:
    int integerReplacement(int n) {
        if(n == 2147483647) return 32;
        queue<int> q;
        unordered_map<int, int> d;
        unordered_map<int, bool> vis;
        d[n] = 0;
        vis[n] = true;
        q.push(n);
        while(!q.empty()){
            int now = q.front();
            //cout<<"now1:"<<now<<" "<<d[now]<<endl;
            q.pop();
            int cnt = 0;
            int pre = d[now];
            while(now % 2 == 0) now /= 2, cnt++;
            if(now == 1) {
                d[now] = pre + cnt;
                break;
            }
            //cout<<"now2:"<<now<<" "<<d[now]<<endl;
            if(!vis[now - 1]){
                d[now - 1] = pre + cnt + 1;
                vis[now - 1] = true;
                q.push(now - 1);
            }
            if(!vis[now + 1]){
                d[now + 1] = pre + cnt + 1;
                vis[now + 1] = true;
                q.push(now + 1);
            }
        }
        return d[1];
    }
};