0397. Integer Replacement

397. Integer Replacement #

题目 #

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

题目大意 #

给定一个正整数 n,你可以做如下操作:

  1. 如果 n 是偶数,则用 n / 2 替换 n。
  2. 如果 n 是奇数,则可以用 n + 1 或 n - 1 替换 n。

问 n 变为 1 所需的最小替换次数是多少?

解题思路 #

  • 题目给出一个整数 n,然后让我们通过变换将它为 1,如果 n 是偶数,可以直接变为 n/2,如果是奇数,可以先 n+1n-1,问最终变为 1 的最少步骤。

  • 当 n 为奇数的时候,什么时候需要加 1 ,什么时候需要减 1 ,通过观察规律可以发现,除了 3 和 7 以外,所有加 1 就变成 4 的倍数的奇数,都适合先加 1 运算,比如 15:

      15 -> 16 -> 8 -> 4 -> 2 -> 1
      15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1
        
      111011 -> 111010 -> 11101 -> 11100 -> 1110 -> 111 -> 1000 -> 100 -> 10 -> 1
      111011 -> 111100 -> 11110 -> 1111 -> 10000 -> 1000 -> 100 -> 10 -> 1
    
  • 对于 7 来说,加 1 和减 1 的结果相同,可以不用管,对于 3 来说,减 1 的步骤更少,所以需要先去掉这种特殊情况。

  • 最后如何判断某个数字加 1 后是 4 的倍数呢?这里有一个小技巧,由于之前判断了其是奇数了,那么最右边一位肯定是 1,如果其右边第二位也是 1 的话,那么进行加 1 运算,进位后右边肯定会出现两个 0,则一定是 4 的倍数。于是就可以判断出来了。剩下的情况就是偶数的情况,如果之前判定是偶数,那么直接除以 2 (右移一位)即可。

代码 #


package leetcode

func integerReplacement(n int) int {
	res := 0
	for n > 1 {
		if (n & 1) == 0 { // 判断是否是偶数
			n >>= 1
		} else if (n+1)%4 == 0 && n != 3 { // 末尾 2 位为 11
			n++
		} else { // 末尾 2 位为 01
			n--
		}
		res++
	}
	return res
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者