yoruru的努力日記

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

 

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

 

Constraints:

• 0 <= x <= 231 - 1

---

SOL：

round down是無條件捨去的意思，例如2.8->2。

Note: 看到題目想五分鐘，自己想不出來就去找解題思路來實現。

最直接簡單的解題思路就是使用暴力法了，for loop i從1到x，甚至是x/2(?)，若過程中i相乘(i*i)超過x，那i-1就是答案了。

一開始知道可以用Binary Search來解，但沒有想法，於是直接去看了別人的解題思路。(Note: code不要細看，知道解法要自己能夠在一小時內實現)

Binary Search的解題思路如下：

int start = 1

int end = x

int mid = (1+x)/2

因為我是用python，所以不會特別注意到mid應該要是整數，但題目只要整數，用小數去算會無窮無盡。

接著就是search了，若 mid*mid=x, return mid

若 mid*mid>x, 更新 end

若 mid*mid<x, 更新 start

透過一直限縮 start 跟 end 的過程中，將答案找出來。

此外，第一次提交後，沒有考慮到x=0，因此沒過。

最後我的版本長這樣。

比對一下跟別人的差異。

發現在更新 start 跟 end 的時候，若能直接用 mid+1, mid-1，應該可以更有效率。

因為while的中止條件不同，右邊是start<=end，所以最後會return end。

然後python因為不用宣告類型，所以可以用 // 來向下取整，比較安全。

 

Reference：

1. LeetCode-69. Sqrt(x)

2. LeetCode 解題筆記 (Binary Search類型題目)
-> 目前初學，預計照著這個分類往下練習(?)，下一題解278，不過都是easy，之後可能需要調整來刷高頻題。

3. Find Square Root of a Number (sqrt(x)) | Binary Search | Programming Tutorials

-> 我的解題思路來源，以及對照版code

4. 花花酱 LeetCode. 69 Sqrt(x)

5. python中的除法，取整和求模

6. LeetCode - Binary Search tags

7. Leetcode面试高频题分类刷题总结