1 題目描述

2 解題思路

2.1 遞歸

class Solution:def integerReplacement(self, n: int) -> int:if(n==1):return 0elif(n%2==0):return 1+self.integerReplacement(n//2)else:return 2+min(self.integerReplacement((n+1)//2),self.integerReplacement((n-1)//2))

2.2 加備忘錄的遞歸

將之前已經考慮過的數及其對應的結果存在一個字典里面

class Solution:def integerReplacement(self, n: int) -> int:dit={1:0}def dfs(nn):nonlocal ditprint(dit)if(nn in dit):return(dit[nn])elif(nn%2==0):dit[nn]=1+dfs(nn//2)return(dit[nn])else:dit[nn]=2+min(dfs((nn+1)//2),dfs((nn-1)//2))return(dit[nn])dfs(n)print(dit)return(dit[n])

可以看到，相比于原先不帶存儲的dfs，加備忘錄之后的方法時間會省下很多（因為不用一次一次遞歸遍歷，之前已經計算過的都已經存在字典里面了）

2.3 廣度優先遍歷 bfs

對于一個數，當其為偶數的時候只有一種操作（除2）；當其為奇數的時候存在兩種操作，我們可以通過廣度優先遍歷求解最少操作次數。誰先得到1，誰就是最小次數。

class Solution:def integerReplacement(self, n: int) -> int:lst=[(n,0)]while(lst):tmp_n,tmp_count=lst.pop(0)if(tmp_n==1):return(tmp_count)elif(tmp_n%2==0):lst.append(((tmp_n//2),tmp_count+1))else:lst.append((tmp_n-1,tmp_count+1))lst.append((tmp_n+1,tmp_count+1))

2.4 位運算

偶數的二進制格式都是0bXXX0,那么直接左移即可。

對于奇數的話，如果是1，直接返回0；

大于1的奇數格式為0bXX01或者XX11，對于前一種格式直接-1（減一后的結果是00，加一后的結果是10，前者連續的零多，那么需要的操作步驟少），對于后一種格式直接+1（加一后的結果是00，減一后的結果是10，前者連續的零多，那么需要的操作步驟少）。

但是有一個數要特判，那就是3，因為3的二進制只有2位，0b11

class Solution:def integerReplacement(self, n: int) -> int:count=0while (n!=1):if(n&1==0):#如果最后一位為0，也就是說它是偶數，那么就向右移n=n>>1else:if(n==3):#3的時候要特判n=n-1else:if(n&2==0):n=n-1else:n=n+1count+=1return(count)

時間和帶存儲的dfs一樣，是用時最少的

總結

以上是生活随笔為你收集整理的文巾解题 397. 整数替换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。