leetcode 397. Integer Replacement 二分查找 + 深度优先遍历DFS

朴灿烈づ我的快乐病毒、 2022-06-04 06:28 144阅读 0赞

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

题意很简单，就是做一个简单的DFS深度优先遍历查找，

**注意要使用long long数据类型，使用int可能超时**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int integerReplacement(int n) 
        {
            if (n <= 1)
                return 0;
            else
                return (int)getRes(n);
        }
    
        int getRes(long long n)
        {
            if (n == 1)
                return 0;
            else
            {
                if (n % 2 == 0)
                    return getRes(n / 2) + 1;
                else
                {
                    int a = getRes(n - 1) + 1;
                    int b = getRes(n + 1) + 1;
                    return min(a, b);
                }
            }
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关深度优先遍历(DFS)和广度优先遍历(BFS)

深度优先遍历(DFS)和广度优先遍历(BFS) 转载：https://blog.csdn.net/rr123rrr/article/details/77971771 图

ゝ一纸荒年。/ 2023年07月06日 14:46/ 0 赞/ 39 阅读

相关 leetcode 52. N-Queens II DFS深度优先遍历

Follow up for N-Queens problem. Now, instead outputting board configurations, return th

蔚落/ 2022年06月09日 10:42/ 0 赞/ 148 阅读

相关 leetcode 51. N-Queens DFS深度优先遍历

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no

墨蓝/ 2022年06月09日 10:42/ 0 赞/ 206 阅读

相关 leetcode 22. Generate Parentheses DFS深度优先遍历

Given n pairs of parentheses, write a function to generate all combinations of well-form

缺乏、安全感/ 2022年06月09日 08:07/ 0 赞/ 204 阅读

相关 leetcode 113. Path Sum II DFS深度优先遍历

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals

超、凢脫俗/ 2022年06月08日 04:15/ 0 赞/ 196 阅读

相关 leetcode 112. Path Sum DFS深度优先遍历

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that a

以你之姓@/ 2022年06月08日 03:17/ 0 赞/ 229 阅读

相关 leetcode 101. Symmetric Tree BFS广度优先遍历+DFS深度优先遍历

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its ce

绝地灬酷狼/ 2022年06月08日 02:14/ 0 赞/ 265 阅读

相关 leetcode 397. Integer Replacement 二分查找 + 深度优先遍历DFS

Given a positive integer n and you can do operations as follow: If n is even, replace n

朴灿烈づ我的快乐病毒、/ 2022年06月04日 06:28/ 0 赞/ 145 阅读

相关 Python深度优先遍历DFS与广度优先遍历BFS

深度优先遍历DFS与广度优先遍历BFS 以下代码块是在python3.7-32bit下成功运行的例子，其中广度优先遍历是由队列实现的，深度优先遍历是由递归和栈两种方法实现

今天药忘吃喽~/ 2022年04月23日 10:36/ 0 赞/ 351 阅读

相关 DFS深度优先搜索遍历

转载：[https://blog.csdn.net/qq\_38442065/article/details/81634282][https_blog.csdn.net_qq_

悠悠/ 2021年11月22日 11:14/ 0 赞/ 416 阅读