LeetCode算法题-Guess Number Higher or Lower（Java实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode算法题-Guess Number Higher or Lower（Java实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1449字，纯文字阅读大概需要3分钟。

内容图文

这是悦乐书的第211次更新，第224篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第79题（顺位题号是374）。我们正在玩数字游戏。 游戏如下：我从1到n中选择一个数字。 你必须猜测我选择了哪个数字。每次你猜错了，我都会告诉你这个数字是高还是低。您调用预定义的API guess（int num），它返回3个可能的结果（-1,1或0）：

-1：我的数字较低
1：我的数字更高
0：猜对了！

例如：

输入：n = 10，pick = 6
输出：6

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

暴力解法，直接使用for循环，依次调用guess（int num）方法，直到猜对了为止。但是此解法超时。

此解法时间复杂度是O(n)，空间复杂度是O(1)。

public int guessNumber(int n) {
    for (int i=1; i<n; i++) {
        if (guess(i) == 0) {
            return i;
        }
    }
    return n;
}

03 第二种解法

使用二分查找法来判断，在求中间数的时候，需要换种写法mid = (high-low)/2 + low;或者将类型换成long，这样做是为了避免溢出。

此解法的时间复杂度是O(log n)，空间复杂度是O(1)。

public int guessNumber2(int n) {
    int low = 1;
    int high = n;
    while (low <= high) {
        int mid = (high-low)/2 + low;
        int result = guess(mid);
        if (result == 0) {
            return mid;
        } else if(result == 1) {
            low = mid + 1;
        } else if(result == -1) {
            high = mid - 1;
        }
    }
    return -1;
}

04 小结

算法专题目前已连续日更超过两个月，算法题文章79+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！

内容总结

以上是互联网集市为您收集整理的LeetCode算法题-Guess Number Higher or Lower（Java实现）全部内容，希望文章能够帮你解决LeetCode算法题-Guess Number Higher or Lower（Java实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---