397.整数替换

这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战

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

解题思路

利用队列实现广度优先搜索，按照操作次数进行入队操作，每次同一批出队的，都是具有相同操作次数的，因此我们可以根据出队的批次，得出转化为1的操作次数，每次对于出队的元素判断其奇偶性，如果 n 是偶数，则将 n / 2入队 。如果 n 是奇数，则将 n + 1和n - 1入队。使用set记录已经遍历过的数字，防止重复。直到我们队头元素出现1，那么当前出队的批次则是最小的替换次数

代码

class Solution {
public:
    int integerReplacement(int n) {

        queue<long> q;
        set<long> seen;
        seen.insert(n);
        q.push(n);
        int res(0);
        while (!q.empty()){
         
            int size=q.size();
            for (int i = 0; i < size; ++i) {
                long cur=q.front();

                if (cur==1)
                    return res;

                q.pop();
                if (cur%2==0){
                    if (!seen.count(cur/2))
                    {
                        q.push(cur/2);
                        seen.insert(cur/2);
                    }
                }else {
                    if (!seen.count(cur+1))
                    {
                        q.push(cur+1);
                        seen.insert(cur+1);
                    }
                    if (!seen.count(cur-1))
                    {
                        q.push(cur-1);
                        seen.insert(cur-1);
                    }
                }
            }
   res++;
        }
        return  0;
    }
};
复制代码

• 时间复杂度：
  $O(\log{n})$

  O(logn)

• 空间复杂度：
  $O(\log{n})$

  O(logn)

或者根据题意直接进行递归

class Solution {
public:
    int integerReplacement(int n) {
        if (n==1)
        return  0;
        if (n==INT_MAX)
            return 32;
        if (n%2==0)
            return integerReplacement(n/2)+1;
        else return min(integerReplacement(n+1),integerReplacement(n-1))+1;
    }
};
复制代码

• 时间复杂度：

  $O(\phi ^{\log n})$

  O(ϕlogn)，其中

  $\phi = \dfrac{1+\sqrt{5}}{2} \approx 1.618$

  ϕ=21+5​​≈1.618表示黄金分割比。

• 空间复杂度：

  $O(\log n)$

  O(logn)。每一次递归都会将 n 减小一半，因此需要

  $O(\log n)$

  O(logn)的栈空间。