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(\log n)$

或者根據題意直接進行遞歸

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({?}^{\log n})$，其中 $?=\frac{1+\sqrt{5}}{2}\approx 1.618$表示黃金分割比。

• 空間復雜度：$O(\log n)$。每一次遞歸都會將 n 減小一半，因此需要 $O(\log n) $的棧空間。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/integer-replacement
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。