資訊專欄INFORMATION COLUMN
Problem
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.
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.
Solution
start <= end / start < end / start + 1 < end
class Solution {
public int sqrt(int x) {
if (x < 1) return 0;
int start = 1;
int end = x;
while (start < end) {
int mid = start + (end-start)/2;
if (mid <= x/mid && mid+1 > x/(mid+1)) {
return mid;
} // The key to success
if (mid <= x/mid) start = mid;
else end = mid;
}
return start;
}
}
start+1 < end
class Solution {
public int sqrt(int x) {
if (x < 1) return 0;
int start = 1, end = x/2+1;
while (start+1 < end) {
int mid = start+(end-start)/2;
if (mid <= x/mid) start = mid;
else end = mid;
}
return start;
}
}
update 2018-11
class Solution {
public int mySqrt(int x) {
if (x < 0) return -1;
int left = 1, right = x;
while (left <= right) {
int mid = left+(right-left)/2;
if (mid <= x/mid) {
if (mid+1 > x/(mid+1)) return mid;
else left = mid+1;
} else {
right = mid-1;
}
}
return 0;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66186.html
摘要：牛頓迭代法的原理很簡(jiǎn)單，其實(shí)是根據(jù)在附近的值和斜率，估計(jì)和軸的交點(diǎn)，因此牛頓迭代法的公式為其實(shí)就是求切線與軸的交點(diǎn)。代碼利用牛頓法進(jìn)行的更新，比直接從開始遍歷所作的循環(huán)要少牛頓迭代法的基本原理，請(qǐng)參考牛頓迭代法求開平方 描述 Implement int sqrt(int x). Compute and return the square root of x, where x is gu...
摘要：題目思路牛頓迭代法，導(dǎo)數(shù)方程，任何函數(shù)，求解某個(gè)均可以轉(zhuǎn)化為此后就可以用牛頓迭代法，不斷逼近實(shí)際待求值。牛頓迭代共識(shí)應(yīng)用迭代思想，類似于動(dòng)態(tài)規(guī)劃思想，，進(jìn)行動(dòng)態(tài)推斷處理 題目： Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-neg...
摘要：測(cè)試用例輸入輸入輸入負(fù)數(shù)的輸入平方根為正整數(shù)的輸入平方根為小數(shù)的代碼實(shí)現(xiàn)寫二分查找代碼需要注意的三點(diǎn)循環(huán)退出條件。使用二分查找之前，判斷問(wèn)題是否滿足二分查找的要求。 Time：2019/4/17Title: sqrt(x)Difficulty: EasyAuthor: 小鹿 題目：sqrt(x) Implement int sqrt(int x). Compute and retu...
摘要：如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。也因?yàn)槭桥判虻臄?shù)組，所以可以考慮二分法。計(jì)算并返回的平方根，其中是非負(fù)整數(shù)。輸入輸出說(shuō)明的平方根是由于返回類型是整數(shù)，小數(shù)部分將被舍去。是一個(gè)非負(fù)整數(shù)，并且在位有符號(hào)整型的范圍內(nèi)。 有時(shí)候會(huì)抽時(shí)間看看題目，鍛煉一下簡(jiǎn)單記錄下二分查找吧，會(huì)持續(xù)更新的啊哈~~~僅供參考，路過(guò)看下就行，歡迎交流~ 第35題 給定一個(gè)排序數(shù)組和一個(gè)目...
閱讀 2069·2021-11-23 09:51
閱讀 2213·2021-09-29 09:34
閱讀 3704·2021-09-22 15:50
閱讀 3564·2021-09-22 15:23
閱讀 2590·2019-08-30 15:55
閱讀 708·2019-08-30 15:53
閱讀 3079·2019-08-29 17:09
閱讀 2635·2019-08-29 13:57
