資訊專(zhuān)欄INFORMATION COLUMN
摘要：前言今天心血來(lái)潮想做一下題目，就選了一道關(guān)于二分查找的題目的平方根實(shí)現(xiàn)函數(shù)。計(jì)算并返回的平方根，其中是非負(fù)整數(shù)。示例輸入輸出示例輸入輸出說(shuō)明的平方根是由于返回類(lèi)型是整數(shù)，小數(shù)部分將被舍去。
前言
今天心血來(lái)潮想做一下題目，就選了一道關(guān)于二分查找的題目x的平方根：
解題思路實(shí)現(xiàn)int sqrt(int x)函數(shù)。
計(jì)算并返回 x 的平方根，其中 x 是非負(fù)整數(shù)。
由于返回類(lèi)型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。
示例 1:輸入: 4 輸出: 2示例 2:
輸入: 8 輸出: 2 說(shuō)明: 8 的平方根是 2.82842..., 由于返回類(lèi)型是整數(shù)，小數(shù)部分將被舍去。
一開(kāi)始我是直接用二分查找的做法來(lái)進(jìn)行解題，但是其中一個(gè)測(cè)試用例為2147395599,進(jìn)行平方的時(shí)候溢出導(dǎo)致結(jié)果錯(cuò)誤。后面在網(wǎng)上找到一個(gè)關(guān)于平方的特性：
對(duì)于一個(gè)非負(fù)數(shù)n，它的平方根m不會(huì)大于（n/2+1），即m<=(m^2)/2+1
利用這個(gè)特性縮小了二分查找的范圍最終完成解題。
public int mySqrt(int x) {
//為了防止溢出，選擇用長(zhǎng)整型
long left=0;
//對(duì)于一個(gè)非負(fù)數(shù)n，它的平方根不會(huì)大于 n/2+1
long right=x/2+1;
while(left<=right){//二分查找
long middle = (left + right)/2;
long middleSqrt=middle*middle;
if(middleSqrt>x){
right=middle-1;
}else if(middleSqrt
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77017.html
摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時(shí)我在談啥狀態(tài)碼詳解無(wú)狀態(tài)協(xié)議和請(qǐng)求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場(chǎng)景說(shuō)說(shuō)你常用的命令為什么要有包裝類(lèi)面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計(jì)工程在線診斷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時(shí)我在談啥？...
摘要：題目給定一個(gè)文檔的完全路徑，請(qǐng)進(jìn)行路徑簡(jiǎn)化。例如，邊界情況你是否考慮了路徑的情況在這種情況下，你需返回。此外，路徑中也可能包含多個(gè)斜杠，如。文化和社會(huì)被恐懼所塑造，在將來(lái)這無(wú)疑也不會(huì)消失。 題目 給定一個(gè)文檔 (Unix-style) 的完全路徑，請(qǐng)進(jìn)行路徑簡(jiǎn)化。 例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 邊界情況:...
摘要：題目給定一個(gè)文檔的完全路徑，請(qǐng)進(jìn)行路徑簡(jiǎn)化。例如，邊界情況你是否考慮了路徑的情況在這種情況下，你需返回。此外，路徑中也可能包含多個(gè)斜杠，如。文化和社會(huì)被恐懼所塑造，在將來(lái)這無(wú)疑也不會(huì)消失。 題目 給定一個(gè)文檔 (Unix-style) 的完全路徑，請(qǐng)進(jìn)行路徑簡(jiǎn)化。 例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 邊界情況:...
摘要：簡(jiǎn)介關(guān)于的商標(biāo)和，官方源碼中是這樣說(shuō)的在行中文的意思是不要?jiǎng)h除標(biāo)志或版權(quán)聲明。根據(jù)第節(jié)的通用公共許可證版本，這些適當(dāng)?shù)姆陕暶鞅仨毐Ａ麸@示的標(biāo)志和版權(quán)聲明。上面的這段進(jìn)制字符串用相應(yīng)的方法轉(zhuǎn)換成正常的字符串就可以看到了。 1：簡(jiǎn)介 關(guān)于Zurmo的商標(biāo)和Logo，官方源碼中是這樣說(shuō)的：在 zurmo/app/protected/modules/zurmo/views/FooterVie...
閱讀 3581·2023-04-26 02:10
閱讀 1343·2021-11-22 15:25
閱讀 1684·2021-09-22 10:02
閱讀 920·2021-09-06 15:02
閱讀 3480·2019-08-30 15:55
閱讀 613·2019-08-30 13:58
閱讀 2788·2019-08-30 12:53
閱讀 3068·2019-08-29 12:38
