Given a positive integer n and you can do operations as follow:
n/2.n + 1 or n - 1.What is the minimum number of replacements needed for n to become 1?
Example 1:
Input: 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1
Example 2:
Input: 7 Output: 4 Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1
本题可以直接用递归的方法求解，并可以通过OJ.
1 def integerReplacement(self, n): 2 """ 3 :type n: int 4 :rtype: int 5 """ 6 if n == 1: 7 return 0 8 9 if n % 2 == 0: 10 return self.integerReplacement(n/2) + 1 11 else: 12 return min(self.integerReplacement(n-1), self.integerReplacement(n+1)) + 1
不用递归的话，对于偶数的n，处理方式是确定的 n /= 2。关键在于对于奇数的n，处理方式应该是n-1还是n+1。经过观察，如果n + 1是4的倍数(除了3， see L14)。那么应该取加1。比如 n = 7, 15, ...
1 def integerReplacement(self, n): 2 """ 3 :type n: int 4 :rtype: int 5 """ 6 if n == 1: 7 return 0 8 9 count = 0 10 while n > 1: 11 if n % 2 == 0: 12 n /= 2 13 count += 1 14 elif (n+1) % 4 == 0 and n != 3: 15 n += 1 16 count += 1 17 else: 18 n -= 1 19 count += 1 20 21 return count
原文：http://www.cnblogs.com/lettuan/p/6189031.html