目录

[Easy]LeetCode#69. x 的平方根

Resowolf 收录于 LeetCode

2019-05-21 约 263 字预计阅读 1 分钟

https://img.cdn.resowolf.com/static/LeetCode_easy.png

目录

[Easy]LeetCode#69. x 的平方根

题目原地址

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:

1
2
输入: 4
输出: 2

示例 2:

1
2
3
4
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

基本算法，这个easy，比较简单就是二分的查找到这个整数就行

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func mySqrt(x int) int {
    mMap := make(map[int]int)
	res := 0
	s := 1
	e := x
	n := 0
	for n < x {
		m := (s + e) / 2
		n = m * m
		if mMap[m] > 0 {
			break
		}
		mMap[m]++
		if n == x {
			res = m
			break
		} else if n < x {
			res = m
			s = m
		} else {
			e = m
			n = 0
		}
	}
	return res
}