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+1或n-1,让我们求变为1的最少步骤。那么一看道题的要求,就会感觉应该用递归很合适,我们直接按照规则写出递归即可,注意由于有n+1的操作,所以当n为INT_MAX的时候,就有可能溢出,所以我们可以先将n转为长整型,然后再进行运算,参见代码如下:

 

解法一:

class Solution {
public:
    int integerReplacement(int n) {
        if (n == 1) return 0;
        if (n % 2 == 0) return 1 + integerReplacement(n / 2);
        else {
            long long t = n;
            return 2 + min(integerReplacement((t + 1) / 2), integerReplacement((t - 1) / 2));
        }
    }
}; 

 

我们也可以使用迭代的解法,那么这里就有小技巧了,当n为奇数的时候,我们什么时候应该加1,什么时候应该减1呢,通过观察来说,除了3和7意外,所有加1就变成4的倍数的奇数,适合加1运算,比如15:

15 -> 16 -> 8 -> 4 -> 2 -> 1

15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1

对于7来说,加1和减1的结果相同,我们可以不用管,对于3来说,减1的步骤小,所以我们需要去掉这种情况。那么我们如何知道某个数字加1后是否是4的倍数呢,我们可以用个小技巧,由于我们之前判定其是奇数了,那么最右边一位肯定是1,如果其右边第二位也是1的话,那么进行加1运算,进位后右边肯定会出现两个0,则一定是4的倍数,搞定。如果之前判定是偶数,那么除以2即可,参见代码如下:

 

解法二:

class Solution {
public:
    int integerReplacement(int n) {
        long long t = n;
        int cnt = 0;
        while (t > 1) {
            ++cnt;
            if (t & 1) {
                if ((t & 2) && (t != 3)) ++t;
                else --t;
            } else {
                t >>= 1;
            }
        }
        return cnt;
    }
};

 

参考资料:

https://discuss.leetcode.com/topic/58655/0ms-cpp-solution

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation