难度中等
给定一个正整数 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
class Solution: def integerReplacement(self, n: int) -> int: def backtracking(n,momo): if n == 1: momo[n] = 1 return 1 if n <=0: return 0 if n%2==1: res = 1 + min(backtracking(n+1,momo),backtracking(n-1,momo)) else: res = 1 + backtracking(n/2,momo) momo[n] = res return res momo = {} return backtracking(n,momo)-1
标签:示例,int,整数,momo,397,替换,def From: https://www.cnblogs.com/zle1992/p/17452905.html