資訊專(zhuān)欄INFORMATION COLUMN
摘要：測(cè)試用例輸入輸入輸入負(fù)數(shù)的輸入平方根為正整數(shù)的輸入平方根為小數(shù)的代碼實(shí)現(xiàn)寫(xiě)二分查找代碼需要注意的三點(diǎn)循環(huán)退出條件。使用二分查找之前，判斷問(wèn)題是否滿足二分查找的要求。
Time：2019/4/17
Title: sqrt(x)
Difficulty: Easy
Author: 小鹿
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
實(shí)現(xiàn) int sqrt(int x) 函數(shù)。計(jì)算并返回 x 的平方根，其中 x 是非負(fù)整數(shù)?！浮?/p>
由于返回類(lèi)型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。
Example 1:
Input: 4 Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
Solve:
1）根據(jù)題目要求，求一個(gè)指定樹(shù)的平方根，第一要想到的是開(kāi)平方根是沒(méi)有規(guī)律可循的，可能想到一個(gè)暴力破解法，從 1 開(kāi)始遍歷，直到滿足 k^2 < x 且 (k+1)^2 > x 為止。2) 你可能想到這種方法效率太低，需要從 1 開(kāi)始，如果 x 很大，豈不是需要遍歷很多？能不能規(guī)定一個(gè)范圍，在這個(gè)范圍中查找開(kāi)平方根呢？你會(huì)想到，所有數(shù)的開(kāi)平方根得到的值是永遠(yuǎn)小于等于自身的（0 是自身），所以 x 的開(kāi)平方根的值的范圍一定在 0 < k < x 之間。
3）要想在這個(gè)區(qū)間快速定位找到一個(gè)滿足條件的 x ，最高效的方法莫過(guò)于二分查找，但是可能存在小數(shù)，這又涉及到二分查找的四個(gè)變體（二分查找的變形）過(guò)程。如果你之前沒(méi)有連接過(guò)，沒(méi)關(guān)系，請(qǐng)看我之前記載的一篇文章。
4）雖然我們已經(jīng)確定了解題方法，但是這時(shí)候不要著急，想一想這個(gè)問(wèn)題是否滿足二分查找的四個(gè)適用條件？哪四個(gè)條件呢？你需要系統(tǒng)學(xué)習(xí)一下就 ok ！
1）此過(guò)程分為兩種情況，負(fù)數(shù)和正整數(shù)，所以要對(duì)輸入的 x 進(jìn)行判斷。2）然后開(kāi)始根據(jù)二分查找應(yīng)該注意的「三個(gè)重點(diǎn)」寫(xiě)出無(wú) bug 的代碼。
3）對(duì)二分查找進(jìn)行稍微的變體，因?yàn)槲覀兛赡懿檎业臄?shù)并不是一個(gè)正整數(shù)，我們?nèi)≌麛?shù)部分就可以了，小數(shù)部分省略。
1）輸入 02）輸入1
3）輸入負(fù)數(shù)的 x
4）輸入平方根為正整數(shù)的 x
5）輸入平方根為小數(shù)的 x
寫(xiě)二分查找代碼需要注意的三點(diǎn)：1）循環(huán)退出條件。
2）mid 的取值。
3）low 和 hight 的更新。
var mySqrt = function(x) {
let low = 1;
let high = x;
// 如果 x 小于 0 輸出 -1
if(x < 0) return -1;
// 循環(huán)終止條件
while(low <= high){
// mid 取值
let mid = Math.floor(low + ((high - low)/2));
// 判斷平方是否小于等于
if(Math.pow(mid,2) <= x){
// 如果小于等于,如果下一值大于 x 則當(dāng)前值為 x 平方根的最小整數(shù)值
if(Math.pow(mid+1,2) > x || mid === high){
return mid;
}else{
low = mid + 1;
}
}else{
high = mid - 1;
}
}
return 0;
};
暴力破解：
時(shí)間復(fù)雜度：O（n）。你需要從 1 遍歷所有可能的數(shù)據(jù)，所以時(shí)間復(fù)雜度為O（n）。
空間復(fù)雜度：O（1）。不需要額外的內(nèi)存空間。
二分法：
時(shí)間復(fù)雜度：O（n）。每次都折半查找，所以查找一個(gè)元素時(shí)間復(fù)雜度為O（logn）。
空間復(fù)雜度：O（1）。不需要額外的內(nèi)存空間。
通過(guò)這個(gè)題我們可以總結(jié)一下：1）如果問(wèn)題涉及到查找，我們要想到使用二分查找來(lái)提高效率。
2）使用二分查找之前，判斷問(wèn)題是否滿足二分查找的要求。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/103662.html
摘要：如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。也因?yàn)槭桥判虻臄?shù)組，所以可以考慮二分法。計(jì)算并返回的平方根，其中是非負(fù)整數(shù)。輸入輸出說(shuō)明的平方根是由于返回類(lèi)型是整數(shù)，小數(shù)部分將被舍去。是一個(gè)非負(fù)整數(shù)，并且在位有符號(hào)整型的范圍內(nèi)。 有時(shí)候會(huì)抽時(shí)間看看題目，鍛煉一下簡(jiǎn)單記錄下二分查找吧，會(huì)持續(xù)更新的啊哈~~~僅供參考，路過(guò)看下就行，歡迎交流~ 第35題 給定一個(gè)排序數(shù)組和一個(gè)目...
摘要：你只可以看到在滑動(dòng)窗口內(nèi)的數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。返回滑動(dòng)窗口最大值。算法思路暴力破解法用兩個(gè)指針，分別指向窗口的起始位置和終止位置，然后遍歷窗口中的數(shù)據(jù)，求出最大值向前移動(dòng)兩個(gè)指針，然后操作，直到遍歷數(shù)據(jù)完成位置。 Time：2019/4/16Title: Sliding Window MaximumDifficulty: DifficultyAuthor: 小鹿 題目...
摘要：牛頓迭代法的原理很簡(jiǎn)單，其實(shí)是根據(jù)在附近的值和斜率，估計(jì)和軸的交點(diǎn)，因此牛頓迭代法的公式為其實(shí)就是求切線與軸的交點(diǎn)。代碼利用牛頓法進(jìn)行的更新，比直接從開(kāi)始遍歷所作的循環(huán)要少牛頓迭代法的基本原理，請(qǐng)參考牛頓迭代法求開(kāi)平方 描述 Implement int sqrt(int x). Compute and return the square root of x, where x is gu...
摘要：小鹿題目算法思路摩爾投票算法題目的要求是讓我們求數(shù)組中超過(guò)一半數(shù)據(jù)以上相同的元素且總是存在的。 Time：2019/4/4Title: Majority Element 1Difficulty: easyAuthor: 小鹿 題目：Majority Element 1 Given an array of size n, find the majority element. The ...
閱讀 2785·2021-11-04 16:15
閱讀 3458·2021-09-29 09:35
閱讀 4032·2021-09-22 15:45
閱讀 1416·2019-08-30 15:55
閱讀 1688·2019-08-30 15:44
閱讀 2711·2019-08-29 12:56
閱讀 2697·2019-08-26 13:30
閱讀 2169·2019-08-23 17:00
