[LeetCode] 397. Integer Replacement

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

If n is even, replace n with n/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

整数替换。

题意是给一个整数，给了如下运算规则，如果是偶数可以除以2；如果是奇数可以+1或-1。问最少需要几步操作可以得到1。

这题的tag给的是位运算，但是我没有实现出来。有哪位朋友实现了位运算的做法，欢迎留言。这题我只会用递归实现。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int integerReplacement(int n) {
 3         return f(n);
 4     }
 5 
 6     private static int f(int n) {
 7         if (n == 1) //终点就是1
 8             return 0;
 9         if (n % 2 == 0) //n为偶数，则右移1位
10             return f(n >>> 1) + 1;
11         else //n为奇数，则需要取两种运算中步数最少的运算
12             return Math.min(f(n - 1), f(n + 1)) + 1;
13     }
14 }

JavaScript实现

 1 /**
 2  * @param {number} n
 3  * @return {number}
 4  */
 5 var integerReplacement = function(n, memo = {}) {
 6     if (n === 1) return 0;
 7     if (memo[n]) return memo[n];
 8     memo[n] =
 9         n % 2 === 0
10             ? integerReplacement(n / 2, memo) + 1
11             : Math.min(integerReplacement(n + 1, memo), integerReplacement(n - 1, memo)) + 1;
12     return memo[n];
13 };

LeetCode 题目总结