首页 > 其他 > 详细

397. Integer Replacement

时间:2020-04-12 18:03:12      阅读:46      评论:0      收藏:0      [点我收藏+]

Problem:

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

思路

Solution (C++):

unordered_map<int, int> visited;
int integerReplacement(int n) {
    if (n == 1)  return 0;
    if (visited.count(n) == 0) {
        if (n & 1 == 1)
            visited[n] =  2 + min(integerReplacement(n/2), integerReplacement(n/2+1));               
        else 
            visited[n] = 1 + integerReplacement(n/2);
    }
    return visited[n];
}

性能

Runtime: 0 ms??Memory Usage: 9.7 MB

思路

Solution (C++):


性能

Runtime: ms??Memory Usage: MB

397. Integer Replacement

原文:https://www.cnblogs.com/dysjtu1995/p/12686150.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!