69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

求一个数的平方根，并向下取整。

public int mySqrt(int x) { if (x < 2) return x; // 注意全部为long 不然 越界 long low = 1; // 平方根的值按规律发现不会大于它的中值+1。这样每个查找就少了一次 long high = x / 2 + 1; long mid; long temp; while (low <= high) { mid = (low + high) / 2; temp = mid * mid; if (temp > x) { high = mid - 1; } else if (temp < x) low = mid + 1; else return (int) mid; } // 二分查找。注意结果不是整数时应返回整数部分。 return (int) high; }

public int mySqrt1(int x) { if (x < 2) { return x; } int low = 1; // 平方根的值按规律发现不会大于它的中值+1。这样每个查找就少了一次 int high = x / 2 + 1; int mid = 0; // 记录最后一次中间结果 int lastMid = 0; while (low <= high) { mid = (low + high) / 2; if (x / mid > mid) { low = mid + 1; lastMid = mid; } else if (x / mid < mid) { high = mid - 1; } else { return mid; } } // 二分查找。注意结果不是整数时应返回整数部分。 return lastMid; }

367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16 Returns: True

Example 2:

Input: 14 Returns: False 题目大意：判断所给的数是否正好是某数的平方

public class Solution { public boolean isPerfectSquare(int num) { long low = 0; long high = num / 2 + 1; long middle = Integer.MIN_VALUE; while (low <= high) { middle = low + (high - low) / 2;// 避免溢出 if (middle * middle == num) return true; else if (middle * middle < num) low = middle + 1; else high = middle - 1; } return false; } } 第二种方法：

public class Solution { public boolean isPerfectSquare(int num) { for (int i = 1; i <= num / i; i++) { if (i * i == num) return true; } return false; }