闯关leetcode——69. Sqrt(x)

大纲

  • 题目
    • 地址
    • 内容
  • 解题
    • 代码地址

题目

地址

https://leetcode.com/problems/sqrtx/description/

内容

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since we round it down to the nearest integer, 2 is returned.

Constraints:

  • 0 <= x <= 231 - 1

解题

这题是要求小于等于一个数的最大平方数。比如9、10、11……15对应的数字都是3,而16对应的数是4。
因为平方数没有太多的规律,所以基本就是挨个尝试来逼近结果。这种问题一般使用二分查找法,解法非常类似于《闯关leetcode——35. Search Insert Position》,主要区别就是我们要返回边界触发时左侧边界。
但是这题解法还是有一定的优化空间,这就涉及二进制相关知识。比如数字16,它的二进制是0x10000,即1左移4次。它也可以表达为1左移2次的数(4)的平方;再比如17,它的二进制是0x10001。它一定比1左移2次的平方大,比1左移3次平方小(这个很好证明)。我们就可以在最开始时分析这个数的二进制中最高位的1所在的位,来限制我们二分查找的区间。
这题还有一个陷阱就是:警惕探索过程中数字乘积越过类型界限。我们在本例的二分查找中就使用了更大的类型来避免这个坑。

class Solution {
public:int mySqrt(int x) {if (x == 0) return 0;int num = x;int i = 1;for (; num > 0; i++) {num >>= 1;}int start = 0;if (i > 2) {start = 1 << (i / 2 - 1);} else {start = 1 << 0;}int end = start << 1;return binarySearch(start, end, x);}
private:int binarySearch(unsigned long long start, unsigned long long end, unsigned long long x) {unsigned long long mid = (start + end) / 2;if (start > end) return end;unsigned long long result = mid * mid;if (result == x) return mid;if (result < x) return binarySearch(mid + 1, end, x);return binarySearch(start, mid - 1, x);}
};

在这里插入图片描述

代码地址

https://github.com/f304646673/leetcode/tree/main/69-Sqrt(x)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/430489.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

计算机毕业设计之:基于微信小程序的中药材科普系统(源码+文档+讲解)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

模拟实现(优先级队列)priority_queue:优先级队列、仿函数、 反向迭代器等的介绍

文章目录 前言一、优先级队列二、仿函数三、 反向迭代器总结 前言 模拟实现&#xff08;优先级队列&#xff09;priority_queue&#xff1a;优先级队列、仿函数、 反向迭代器等的介绍 一、优先级队列 优先级队列本质是一个堆&#xff0c;使用vector容器进一步改进进行实现&am…

vue使用PDF.JS踩的坑--部署到服务器上显示pdf.mjs viewer.mjs找不到资源

之前项目使用的pdf.js 是2.15.349版本&#xff0c;最近换了一个4.6.82的版本&#xff0c;在本地上浏览文件运行的好好的&#xff0c;但是发布到服务器&#xff08;IIS&#xff09;上打不开文件&#xff0c;控制台提示找不到pdf.mjs viewer.mjs。 之前使用的2.15.349pdf和viewer…

mock虚拟接口技术

一、什么是mock mock指的就是使用mock创建出来的一个虚拟的接口 二、对于测试人员而言&#xff0c;我们为什么要使用mock 当我们进行接口测试时&#xff0c;如果对应的接口还没有开发好&#xff0c;但是我们又需要用到这个接口响应的信息&#xff0c;这个时候我们就可以使用…

邮件发送高级功能详解:HTML格式、附件添加与SSL/TLS加密连接

目录 一、邮件HTML格式设置 1.1 HTML邮件的优势 1.2 HTML邮件的编写 二、添加附件 2.1 附件的重要性 2.2 添加附件的代码示例 2.3 注意事项 三、使用SSL/TLS加密连接 3.1 SSL/TLS加密的重要性 3.2 SSL/TLS加密的工作原理 3.3 在邮件发送中启用SSL/TLS 3.3.1 邮件客…

智能算法躲避拥堵,高德企业用车上线“动态选路服务”为出行提效

近日&#xff0c;高德企业用车正式上线了一项全新服务——“动态选路服务”&#xff0c;旨在基于智能算法&#xff0c;动态规避突发拥堵路线&#xff0c;为企业用车用户提供更便捷、智能的出行方案。 以技术着眼细节&#xff0c;高德企业用车在帮助企业用车用户节约出行时间和…

飞睿智能实时雷达活体探测传感器模块,智能家居静止检测实时感知人员有无

随着科技的飞速发展&#xff0c;我们的生活正在经历着未有的创新。在这个创新的浪潮中&#xff0c;实时雷达活体探测传感器模块的技术正逐渐崭露头角&#xff0c;以其独特的优势为我们的生活带来安全与便捷。今天&#xff0c;我们就来详细探讨一下这项技术&#xff0c;看看它是…

TCL25届校招测评笔试TAS人才测评题库:高分攻略真题分析

&#x1f31f; 职场新人必看&#xff1a;TCL校招测评全解析 &#x1f31f; 亲爱的小伙伴们&#xff0c;你是否正准备踏入职场&#xff0c;或是对即将到来的校招感到既兴奋又紧张&#xff1f;今天&#xff0c;我将带你深入了解TCL校招中的TAS人才测评&#xff0c;让你在面试前做…

MyBatis - 动态SQL

前言 我们在某网站填写个人信息时&#xff0c;时常会遇到可以选填的空&#xff08;即可填&#xff0c;可不填&#xff09;&#xff0c;由于之前讲过的Java中的SQL语句都是固定的&#xff0c;且我们不可能对所有情况都写出与之对应的插入语句&#xff08;太过繁琐&#xff09;&…

最新简洁大方的自动发卡网站源码/鲸发卡v11.61系统源码/修复版

源码简介&#xff1a; 最新简洁大方的自动发卡网站源码&#xff0c;它就是鲸发卡v11.61系统源码&#xff0c;它是修复版。 说到鲸发卡系统&#xff0c;鲸发卡系统在发卡圈很多人都知道的&#xff0c;它是市面最好发卡系统之一&#xff0c;操作起来简单得很&#xff0c;界面也…

03-Docker下载加速

03-Docker下载加速 docker下载加速 方式1&#xff1a;使用 网易数帆、阿里云等容器镜像仓库进行下载。 网易数帆官网&#xff1a;https://sf.163.com/ 例如&#xff0c;下载网易数帆镜像中的mysql。&#xff08;网易数帆的地址为 hub.c.163.com&#xff0c;网易数帆对dockerh…

Protobuf:基本概念与使用流程

Protobuf&#xff1a;基本概念与使用流程 基本概念Linux 安装使用流程.proto文件编译使用 运行机制 基本概念 在进行网络编程时&#xff0c;经常需要进行数据传输&#xff0c;只有双方主机都保证数据格式的一致性&#xff0c;才能保证数据被正常解析。这个过程称为序列化与反序…

Android平台Unity3D下如何同时播放多路RTMP|RTSP流?

技术背景 好多开发者&#xff0c;提到希望在Unity的Android头显终端&#xff0c;播放2路以上RTMP或RTSP流&#xff0c;在设备性能一般的情况下&#xff0c;对Unity下的RTMP|RTSP播放器提出了更高的要求。实际上&#xff0c;我们在前几年发布Unity下直播播放模块的时候&#xf…

CTFHub技能树-SQL注入-Cookie注入

使用bp发现cookie的注入点 id1&#xff0c;发现为数字型 首先使用联合查询 id 1 order by 2 id 1 order by 3发现2的时候有回显&#xff0c;而3的时候无回显 Cookie: id-1 union select database(),user() 后面开始库->表->列->数据 Cookie: id-1 union select 1…

Gin中间件

Gin框架允许开发者在处理请求的过程中&#xff0c;加入用户自己的钩子&#xff08;Hook&#xff09;函数。这个钩子函数就叫中间件&#xff0c;中间件适合处理一些公共的业务逻辑&#xff0c;比如登录认证、权限校验、数据分页、记录日志、耗时统计等。 定义中间件 Gin中的中…

上半年亏损扩大/百亿资产重组终止,路畅科技如何“脱困”?

在智能网联汽车市场形势一片大好的前提下&#xff0c;路畅科技上半年的营收却出现了下滑&#xff0c;并且亏损也进一步扩大。 2024年半年度报告显示&#xff0c;路畅科技营业收入1.35亿元&#xff0c;同比下滑7.83%&#xff1b;实现归属上市公司股东的净利润为亏损2491.99万元…

一篇讲完CSS的核心内容

目录 一 、引言 1.1CSS概念 二、 CSS简介 2.1 什么是CSS 2.2 CSS能干什么 2.3 CSS书写规范 2.4 基础语法 三、 CSS导入方式 3.1 内嵌方式(内联方式) 3.2 内部方式 3.3 外部方式 四、 CSS选择器 4.1 基本选择器 [重点] 4.2 属性选择器 五、 CSS属性 5.1 文字属性…

sheng的学习笔记-AI-强化学习(Reinforcement Learning, RL)

AI目录&#xff1a;sheng的学习笔记-AI目录-CSDN博客 基础知识 什么是强化学习 强化学习&#xff08;Reinforcement Learning, RL&#xff09;&#xff0c;又称再励学习、评价学习或增强学习&#xff0c;是机器学习的范式和方法论之一&#xff0c;用于描述和解决智能体&#…

【RabbitMQ】RabbitMQ 的概念以及使用RabbitMQ编写生产者消费者代码

目录 1. RabbitMQ 核心概念 1.1生产者和消费者 1.2 Connection和Channel 1.3 Virtual host 1.4 Queue 1.5 Exchange 1.6 RabbitMO工作流程 2. AMQP 3.RabbitMO快速入门 3.1.引入依赖 3.2.编写生产者代码 ​3.3.编写消费者代码 4.源码 1. RabbitMQ 核心概念 在安装…

Blender软件三大渲染器Eevee、Cycles、Workbench对比解析

Blender 是一款强大的开源3D制作平台&#xff0c;提供了从建模、雕刻、动画到渲染、后期制作的一整套工具&#xff0c;广泛应用于电影、游戏、建筑、艺术等领域。 渲染101云渲染云渲6666 相比于其他平台&#xff0c;如 Autodesk Maya、3ds Max 或 Cinema 4D&#xff0c;Blende…