平方和平方根系列的几个题，毕业之后，再接触到数学，简直怀疑自己的智商没有下限了，涉及到一些牛顿定律，推导过程分分钟还给了大学老师了，只好用一些具象一些的解释了。
题目一：一个数，求平方根的整数部分
1、题目链接
leetcode No69：https://leetcode.com/problems/sqrtx/
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.
2、Solution
方法一：二分查找，找出0-x中间符合的值
func mySqrt(x int) int {
low := 0
high := x
mid := (low+high)/2
for low <= high {
mid = (low+high)/2
if mid * mid == x {
return mid
}else if mid*mid < x{
low = mid + 1
}else {
high = mid-1
}
}
if mid*mid <x{
return mid
}
return mid-1
}
时间复杂度是O(n),空间复杂度O(1)
方法二：使用牛顿法，r = (r + x/r) / 2
在知乎上看到有一个利用“将长方形变得更像正方形”的思路也可以得到求 A 的算数平方根的迭代公式
首先是考虑√A是面积为A的正方形的边长，如果画一个邻边不等的面积是A长方形，设这个长方形的长为L，宽为A/L，那么怎样能让这个长方形变得更像一个正方形呢？是要把长变得短一点，宽变得长一点，可以用长和宽的平均数(L+A/L)/2来作为新的长Lnew，在面积不变的条件下，新的宽是 A/Lnew。这样不断操作下去，长方形的长和宽会越来越接近，就是一直趋近与√A了。
这里更新长方形长的方法
image.png
image.png
image.png
func mySqrt(x int) int {
r := x
for r*r >x {
r = (r + x/r)/2
}
return r
}
题目二：判断一个数平方根是否是整数
题目描述：
leetcode No367:https://leetcode.com/problems/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
Output: true
Example 2:
Input: 14
Output: false
Solution
func isPerfectSquare(num int) bool {
r := num
for r*r > num {
r = (r+num/r)/2
}
return r*r == num
}
题目三：判断一个数是否是两个平方和的和。
题目描述：
leetcode No633:https://leetcode.com/problems/sum-of-square-numbers/
Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: 3
Output: False
Solution
方法一：两个指针，其实也相当于是暴力解，没有被接受[Time Limit Exceeded]
时间复杂度是O(n^2)运行结果是[Time Limit Exceeded]
func judgeSquareSum(c int) bool {
a := 0
b := c
for a <= b {
if a*a+b*b == c {
return true
}else if a*a+b*b < c{
a = a+1
}else {
b = b-1
}
}
return false
}
方法二：可以转化成判断c-a^2是不是一个平方和，变成上述题目二
func judgeSquareSum(c int) bool {
for a:=0;a*a<=c;a++{
if isPerfectSquare(c-a*a) == true {
return true
}
}
return false
}
func isPerfectSquare(num int) bool {
r := num
for r*r > num {
r = (r+num/r)/2
}
return r*r == num
}
这种方式运行时间比较长。偷懒使用go的math.Sqrt方法，运行时间从116ms变为0ms
func judgeSquareSum(c int) bool {
for a:=0;a*a<=c;a++{
b := int(math.Sqrt( float64(c-a*a)))
if b*b == c-a*a{
return true
}
}
return false
}
方法三：费马定理
详细的理论知识见链接：https://wstein.org/edu/124/lectures/lecture21/lecture21/node2.html
func judgeSquareSum(c int) bool {
for a:=2;a*a<=c;a++{
count:=0
if c % a == 0{
for c%a==0 {
count++
c = c/a
}
if a %4 == 3 && count %2 != 0{
return false
}
}
}
return c%4 != 3
}
题目四：k(k+1)=2*n
题目描述
leetcode No441:https://leetcode.com/problems/arranging-coins/
You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.
Example 1:
n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.
Solution
根据题目可计算，是要求1+2+3+...+k <=n的最大k值，计算可得k(k+1)<=2n
方法一，求2n的最大平方根m，k的取值为k或者k-1
func arrangeCoins(n int) int {
k := int(math.Sqrt( float64(2*n) ))
if k*(k+1) <= 2*n{
return k
}
return k-1
}
方法二，直接(2k+1)^2<=(8n+1)
func arrangeCoins(n int) int {
k := int(math.Sqrt( float64(4*n+1) ))
return (k-1)/2
}
网友评论