69-x的平方根

bergwhite 發布于2019-08-19 11:07 / 2062人閱讀

摘要：前言今天心血來潮想做一下題目，就選了一道關于二分查找的題目的平方根實現函數。計算并返回的平方根，其中是非負整數。示例輸入輸出示例輸入輸出說明的平方根是由于返回類型是整數，小數部分將被舍去。

前言

今天心血來潮想做一下題目，就選了一道關于二分查找的題目x的平方根：

實現int sqrt(int x)函數。
計算并返回 x 的平方根，其中 x 是非負整數。
由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。
示例 1:

輸入: 4
輸出: 2

示例 2:

輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842..., 由于返回類型是整數，小數部分將被舍去。

解題思路

一開始我是直接用二分查找的做法來進行解題，但是其中一個測試用例為2147395599,進行平方的時候溢出導致結果錯誤。后面在網上找到一個關于平方的特性：
對于一個非負數n，它的平方根m不會大于（n/2+1），即m<=(m^2)/2+1
利用這個特性縮小了二分查找的范圍最終完成解題。

實現代碼

    public int mySqrt(int x) {
        //為了防止溢出，選擇用長整型
        long left=0;
        //對于一個非負數n，它的平方根不會大于 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

云服務器 GPU云服務器負數的平方 c語言平方根平方根java javascript平方根

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77017.html

6-9月技術文章匯總

摘要：分布式的管理和當我在談論架構時我在談啥狀態碼詳解無狀態協議和請求支持哪些方法分層協議棧有哪些數據結構運用場景說說你常用的命令為什么要有包裝類面向對象的特征是啥是啥有什么好處系統設計工程在線診斷系統設計與實現索引背后的數據結構及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當我在談論RestFul架構時我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0
【Leetcode】71. 簡化路徑

摘要：題目給定一個文檔的完全路徑，請進行路徑簡化。例如，邊界情況你是否考慮了路徑的情況在這種情況下，你需返回。此外，路徑中也可能包含多個斜杠，如。文化和社會被恐懼所塑造，在將來這無疑也不會消失。題目給定一個文檔 (Unix-style) 的完全路徑，請進行路徑簡化。例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 邊界情況:...

liuchengxu 2019-08-19 11:11 評論0 收藏0
【Leetcode】71. 簡化路徑

摘要：題目給定一個文檔的完全路徑，請進行路徑簡化。例如，邊界情況你是否考慮了路徑的情況在這種情況下，你需返回。此外，路徑中也可能包含多個斜杠，如。文化和社會被恐懼所塑造，在將來這無疑也不會消失。題目給定一個文檔 (Unix-style) 的完全路徑，請進行路徑簡化。例如，path = /home/, => /homepath = /a/./b/../../c/, => /c 邊界情況:...

afishhhhh 2019-07-30 17:50 評論0 收藏0
Zurmo - - 商標及修改

摘要：簡介關于的商標和，官方源碼中是這樣說的在行中文的意思是不要刪除標志或版權聲明。根據第節的通用公共許可證版本，這些適當的法律聲明必須保留顯示的標志和版權聲明。上面的這段進制字符串用相應的方法轉換成正常的字符串就可以看到了。 1：簡介關于Zurmo的商標和Logo，官方源碼中是這樣說的：在 zurmo/app/protected/modules/zurmo/views/FooterVie...

CntChen 2019-07-24 10:41 評論0 收藏0