【力扣】374.猜数字大小

简介: 【力扣】374.猜数字大小

374.猜数字大小

题目描述

猜数字游戏的规则如下:

  • 每轮游戏,我都会从 1n 随机选择一个数字。 请你猜选出的是哪个数字。
  • 如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-110):

  • -1:我选出的数字比你猜的数字小 pick < num
  • 1:我选出的数字比你猜的数字大 pick > num
  • 0:我选出的数字和你猜的数字一样。恭喜!你猜对了!pick == num

返回我选出的数字。

示例 1:

输入:n = 10, pick = 6

输出:6

示例 2:

输入:n = 1, pick = 1

输出:1

示例 3:

输入:n = 2, pick = 1

输出:1

示例 4:

输入:n = 2, pick = 2

输出:2

提示:

  • 1 <= n <= 231 - 1
  • 1 <= pick <= n

解题方案

  • C 二分法
/**
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return       -1 if num is higher than the picked number
 *            1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */
int guessNumber(int n) {
    int left = 1, right = n; // 定义左值、右值
    int mid = 0;             // 定义中值

    while (left <= right) {
        mid = left + (right - left) / 2; // 计算中值
        int ret = guess(mid);            // 猜数
        if (ret == 0) {
            return mid;
        } else if (ret == 1) {
            left = mid + 1; // 增大左值
        } else {
            right = mid - 1; // 减小右值
        }
    }
    return 0;
}

复杂度分析

时间复杂度为 O(log⁡n),n 为区间初始长度。

空间复杂度为 O(1)。


相关文章
|
SQL JavaScript 前端开发
如何用 23 种编程语言说“Hello World”
如何用 23 种编程语言说“Hello World”
|
数据采集 存储 SQL
基于Apache doris的元数据管理系统
什么是元数据?元数据和数据的区别是什么?元数据有什么作用。
1538 0
基于Apache doris的元数据管理系统
|
6月前
|
机器学习/深度学习 设计模式 API
Python 高级编程与实战:构建微服务架构
本文深入探讨了 Python 中的微服务架构,介绍了 Flask、FastAPI 和 Nameko 三个常用框架,并通过实战项目帮助读者掌握这些技术。每个框架都提供了构建微服务的示例代码,包括简单的 API 接口实现。通过学习本文,读者将能够使用 Python 构建高效、独立的微服务。
|
JavaScript Java 测试技术
基于SpringBoot+Vue+uniapp的个人云盘管理系统的详细设计和实现(源码+lw+部署文档+讲解等)
基于SpringBoot+Vue+uniapp的个人云盘管理系统的详细设计和实现(源码+lw+部署文档+讲解等)
162 1
|
Java 编译器
成功解决:java file outside of source root
解决Java文件不在源代码根目录内的问题,可以通过在IDEA中将包含.java文件的目录设置为Sources Root来修复。
成功解决:java file outside of source root
|
存储 安全 数据安全/隐私保护
配置本地安全策略(一)
配置本地安全策略(一)
365 0
QT TextEdit控件 全面详解
本文详细的介绍了TextEdit控件的各种操作,例如:获取内容、输入控件字符、保持在最后一行添加(自动滚屏)、定时关闭、添加数据换行、向鼠标位置插入一行字符、设置字体颜色属性等操作。 本系列QT全面详解文章目前共有十五篇,本系列文章较为详细的讲述了QT控件的基础操作和使用,也谢谢大家的关注、点赞、收藏。
1897 2
QT TextEdit控件 全面详解
|
Web App开发 网络协议 测试技术
教你用Chrome 浏览器+Postman搞定接口测试
本文介绍了软件测试的两类主要类型:客户端测试(包括UI和兼容性测试)和服务端测试(主要为接口测试)。接口测试能直接检验服务端功能,尤其在复杂如阿里核心链路的系统中,它能更早发现潜在问题。分层测试模型显示,从单元测试到UI测试,越高层的测试发现bug的成本越高。尽管接口测试覆盖广泛,但不能替代客户端测试,因为UI测试关乎用户体验。文中推荐了Postman作为接口测试工具,并展示了如何使用Postman发送GET请求。此外,还介绍了cURL命令行工具及其在接口测试中的应用,包括模拟请求、修改参数和调试。通过实例,读者可以学习如何使用cURL进行GET、POST请求及设置认证和代理。
|
分布式计算 MaxCompute 开发工具
在MaxCompute中,使用`CREATE TEMPORARY TABLE`语句创建的临时表
【2月更文挑战第18天】在MaxCompute中,使用`CREATE TEMPORARY TABLE`语句创建的临时表
621 3
|
弹性计算 Ubuntu Linux
ECS使用体验
学生优惠ECS使用体验