首页 > 代码库 > Leetcode Integer Replacement

Leetcode Integer Replacement

2024-08-27 15:48:07   233人阅读

Given a positive integer n and you can do operations as follow:

 

  1. If n is even, replace n with n/2.
  2. If n is odd, you can replace n with either 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

 

 

 

Leetcode Integer Replacement


联系
我们