leetcode刷题日记:69.sqrt(x)
给出一个非负的整数x,返回x的平方根向下取整的结果,这个被返回的数也应该是一个非负的值。
对我们的要求是不能使用任何内置的指数函数与操作,官方还给了我们例子:
在C++种不能使用pow(x, 0.5) 在python不能使用 x**0.5
既然官方已经这样要求了,那么我们就不使用这些操作了.
我最先的思路是这样的从0开始进行枚举,00与x进行比较,如果00小于x,就向后比较11与x的关系,当依次增大直到不符合条件,因为我们设置的是mm<x 则继续进行比较,但是现在mm>=x,所以我们还需要进行判断mm是大于x还是等于x,当大于x时,说明m-1是答案,当等于x时说明m是答案。
int mySqrt(int x){int i = 0;for(;i<=x/2;i++){if(i*i>=x){break;}}if(i*i==x){return i;}return i-1;
}
但是这一种方式太过于耗费时间了,因为它从0开始进行枚举,这样就太过多了其实如果能建立二叉树就能以O(logn)的时间复杂度进行平方根的查找。我们这一次不用二叉树进行查找,我是用两个变量记录查询的上下界,这样不断的进行将查询区间进行二分,最终也能实现O(logn)时间复杂度。这一个问题其实是一个二分查找的问题。
int sqrt(int x){int left = 0;int right = x;int middle = (left+right)/2;while(left<right){if(middle*middle<x){left = middle+1;}else if(middle*middle>x){right = middle - 1;}else{return middle; // 如果是整数之一,就会直接返回,而不会跳出循环,如果跳出循环,说明只有一个近似的根,无整数平方根}middle = (right + left)/2; }return right; // 从循环跳出这一种情况,数x的平方根取整后一定是right,这一个可以自行验证
}
运行结果截图:

相关文章:
leetcode刷题日记:69.sqrt(x)
给出一个非负的整数x,返回x的平方根向下取整的结果,这个被返回的数也应该是一个非负的值。 对我们的要求是不能使用任何内置的指数函数与操作,官方还给了我们例子: 在C种不能使用pow(x, 0.5) 在python不能使用 x**0.5 既然官方已经…...
[尚硅谷React笔记]——第9章 ReactRouter6
目录: 课程说明一级路由重定向NavLink高亮useRoutes路由表嵌套路由路由的params参数路由的search参数路由的state参数编程式路由导航useRouterContextuseNavigationTypeuseOutletuseResolvedPath()总结项目地址 1.课程说明 概述 React Router以三个不同的包发布…...
强大的pdf编辑软件:Acrobat Pro DC 2023中文
Acrobat Pro DC 2023是一款强大的PDF编辑和管理软件,它提供了广泛的功能,使用户能够轻松创建、编辑、转换和共享PDF文档。通过直观的界面和先进的工具,用户可以快速进行文本编辑、图像调整、页面管理等操作,同时支持OCR技术&#…...
玩一下Spring Boot
文章目录 1 开发环境1.1 JDK1.2 IntelliJ IDEA2 Spring Boot2.1 创建项目2.2 创建模板页面2.3 创建控制器2.4 启动项目2.5 访问页面1 开发环境 1.1 JDK 安装JDK21 配置环境变量 在命令行查看JDK版本 玩一玩jshell...
一个高性能类型安全的.NET枚举实用开源库
从零构建.Net前后端分离项目 枚举应该是我们编程中,必不可少的了,今天推荐一个.NET枚举实用开源库,它提供许多方便的扩展方法,方便开发者使用开发。 01 项目简介 Enums.NET是一个.NET枚举实用程序库,专注于为枚举提…...
c#字符串格式化
字符串格式化是一种将变量的值插入到字符串中的方法。它允许我们创建动态的字符串,其中包含变量的值。 string.Format 通过在字符串中使用占位符{0},{1}等,我们可以指定要插入的变量的位置。然后,通过在string.Format方法的参数…...
AMD老电脑超频及性能提升方案及实施
收拾电子元件的时候找到了若干古董的CPU 其中有一个X3 440 是原来同学主板烧了之后给我的,我从网上配了AM2 昂达主板,然后又买了AMD兼容内存,组成了win7 64位电脑,用起来非常不错,我把硬件配置和升级过程说明下&#x…...
Github 自动化部署到GitHub Pages
1.准备工作 新建仓库 新建项目 配置 vite.config.ts base: ./,部署应用包时的基本URL,例:vue-cli 5.x 配置 publicPath 推送到远程仓库 2.配置 GitHub Token 点击 Settings -> Actions -> General 找到 Workflow permissions,选中第…...
Golang 串口通信
简介 串口通信是一种常见的硬件通信方式,用于在计算机和外部设备之间传输数据。Golang(Go语言)作为一种高效、可靠的编程语言,提供了丰富的库和工具用于串口通信。本文将介绍如何使用Golang进行串口通信,包括串口配置…...
项目管理之如何识别并应对项目风险
项目风险管理是项目管理中不可忽视的环节,如何识别并应对项目的风险对于项目的成功实施至关重要。本文将介绍风险管理的流程、风险分解结构、定性及定量风险评估方法,以及消极和积极的风险应对策略,旨在帮助读者更好地理解和应对项目风险。 …...
vue封装独立组件:实现手写签名功能
目录 第一章 效果展示 第二章 准备工作 2.1 使用的工具vue-sign 2.1.1 安装 2.1.2 了解 2.1.3 参数说明 第三章 源代码 第一章 效果展示 第二章 准备工作 2.1 使用的工具vue-esign 2.1.1 安装 npm install vue-esign --save 2.1.2 了解 兼容pc端和移动端有对应的参…...
图及谱聚类商圈聚类中的应用
背景 在O2O业务场景中,有商圈的概念,商圈是业务运营的单元,有对应的商户BD负责人以及配送运力负责任。这些商圈通常是一定地理围栏构成的区域,区域内包括商户和用户,商圈和商圈之间就通常以道路、河流等围栏进行分隔。…...
npx 和 npm 区别
文章目录 背景作用执行流程 背景 解决 npm 之前的执行包中的命令行需要先下载的问题,如果有多个不同版本的包就需要下载多次比如已经装了全局的 webpack 1.x 版本并且还要继续使用,还需要装个 webpack 4.x 使用的其相应功能,这个时候可以不装在全局&…...
HTML_案例1_注册页面
用纯html页面,不用css画一个注册页面。 最终效果如下: html页面代码如下: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>注册页面</title> </head>…...
Adobe After Effects 2024(Ae2024)在新版本中的升级有哪些?
After Effects 2024是Adobe公司推出的一款视频处理软件,它适用于从事设计和视频特技的机构,包括电视台、动画制作公司、个人后期制作工作室以及多媒体工作室。通过After Effects,用户可以高效且精确地创建无数种引人注目的动态图形和震撼人心…...
超越 GLIP! | RegionSpot: 识别一切区域,多模态融合的开放世界物体识别新方法
本文的主题是多模态融合和图文理解,文中提出了一种名为RegionSpot的新颖区域识别架构,旨在解决计算机视觉中的一个关键问题:理解无约束图像中的各个区域或patch的语义。这在开放世界目标检测等领域是一个具有挑战性的任务。 关于这一块&…...
webgoat-(A1)injection
SQL Injection (intro) SQL 命令主要分为三类: 数据操作语言 (DML)DML 语句可用于请求记录 (SELECT)、添加记录 (INSERT)、删除记录 (DELETE) 和修改现有记录 ÿ…...
51单片机-中断
文章目录 前言 前言 #include <reg52.h> #include <intrins.h>sbit key_s2P3^0; sbit flagP3^7;void delay(unsigned int z){unsigned int x,y;for(xz;x>0;x--)for(y114;y>0;y--); }void int_init(){EA1;EX11;IT11;}void main(){int_init();while(1){if (key…...
Canvas 梦幻树生长动画
canvas可以制作出非常炫酷的动画,以下是一个梦幻树的示例。 效果图 源代码 <!DOCTYPE> <html> <head> <meta http-equiv"Content-Type" content"text/html; charsetutf-8" /> <title>梦幻数生长动画</title&…...
Unity之UI、模型跟随鼠标移动(自适应屏幕分辨率、锚点、pivot中心点)
一、效果 UI跟随鼠标移动, 动态修改屏幕分辨率、锚点、pivot等参数也不会受到影响。同时脚本中包含3d物体跟随ui位置、鼠标位置移动 二、屏幕坐标、Canvas自适应、锚点、中心点 在说原理之前我们需要先了解屏幕坐标、Canvas自适应、锚点、中心的特性和之间的关系。 1.屏幕坐标…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
