Press "Enter" to skip to content

Posts tagged as “newton”

花花酱 LeetCode. 69 Sqrt(x)

题目大意:让你实现开根号函数,只需要返回整数部分。

Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Example 2:

 

 

Solution 1: Brute force

Time complexity: sqrt(x)

C++

C++ div

Java

Python3 TLE

Solution 2: Binary search

Time complexity: O(logn)

C++

Java

Python3

Solution 3: Newton’s method

C++ / float

C++ / int

Java

Python3