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; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66186.html
摘要:牛頓迭代法的原理很簡單,其實是根據在附近的值和斜率,估計和軸的交點,因此牛頓迭代法的公式為其實就是求切線與軸的交點。代碼利用牛頓法進行的更新,比直接從開始遍歷所作的循環要少牛頓迭代法的基本原理,請參考牛頓迭代法求開平方 描述 Implement int sqrt(int x). Compute and return the square root of x, where x is gu...
摘要:題目思路牛頓迭代法,導數方程,任何函數,求解某個均可以轉化為此后就可以用牛頓迭代法,不斷逼近實際待求值。牛頓迭代共識應用迭代思想,類似于動態規劃思想,,進行動態推斷處理 題目: Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-neg...
摘要:測試用例輸入輸入輸入負數的輸入平方根為正整數的輸入平方根為小數的代碼實現寫二分查找代碼需要注意的三點循環退出條件。使用二分查找之前,判斷問題是否滿足二分查找的要求。 Time:2019/4/17Title: sqrt(x)Difficulty: EasyAuthor: 小鹿 題目:sqrt(x) Implement int sqrt(int x). Compute and retu...
摘要:如果目標值不存在于數組中,返回它將會被按順序插入的位置。也因為是排序的數組,所以可以考慮二分法。計算并返回的平方根,其中是非負整數。輸入輸出說明的平方根是由于返回類型是整數,小數部分將被舍去。是一個非負整數,并且在位有符號整型的范圍內。 有時候會抽時間看看題目,鍛煉一下簡單記錄下二分查找吧,會持續更新的啊哈~~~僅供參考,路過看下就行,歡迎交流~ 第35題 給定一個排序數組和一個目...
閱讀 2061·2021-11-23 09:51
閱讀 2203·2021-09-29 09:34
閱讀 3694·2021-09-22 15:50
閱讀 3556·2021-09-22 15:23
閱讀 2559·2019-08-30 15:55
閱讀 699·2019-08-30 15:53
閱讀 3066·2019-08-29 17:09
閱讀 2624·2019-08-29 13:57