397. Integer Replacement

Given a positive integer n, you can apply one of the following operations:

1. If n is even, replace n with n / 2.
2. If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

class Solution {
public:
    int integerReplacement(int n) {
        map<long, int> v;
        queue<long> q;
        v[n] = 0;
        q.push(n);
        while(!v.count(1)) {
            long num = q.front();
            q.pop();
            if(num & 1) {
                if(!v.count(num + 1)) {
                    v[num + 1] = v[num] + 1;
                    q.push(num + 1);
                }

                if(!v.count(num - 1)) {
                    v[num - 1] = v[num] + 1;
                    q.push(num - 1);
                }
            } else if(!v.count(num>>1)) {
                v[num >> 1] = v[num] + 1;
                q.push(num >> 1);
            }
        }

        return v[1];
    }
};