参加了下2023届秋招，不得不感叹leetcode&lintcode的题目实在太多了（也很难），特别对于我这种非科班生而言，感觉有必要分类整理一下，以便以后在工作中更好的应用。花了点时间刷了下二分查找的相关题目，刷的越多，反而越不会了，先把目前遇到的几个题目总结下吧。
隐藏有序序列的数学类型题目主要是与平方根有关系，给定的数字是序列的最大值，目标值是该数的平方根（整数部分），判断给定的数字是否是完全平方数，平方根的整数部分也常常会作为特定题目用于双指针法求解的边界，从而降低算法复杂度。
'''
69. x 的平方根
题目描述：给你一个非负整数 x ，计算并返回x的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
题眼：隐藏有序数组且无重复：0、1、2...x-1、x，
思路：二分查找。相当于是“35. 搜索插入位置”的升级版，在隐藏有序序列中寻找平方根的整数部分，完全平方数就返回平方根，否则返回循环结束的right值，
'''
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 0, x # 这里right取值应该是x，因为x<=1时，均方根是x本身
while left <= right:
mid = left + (right - left) // 2
if mid * mid > x:
right = mid - 1
elif mid * mid < x:
left = mid + 1
else:
return mid
return right # 掌握循环跳出时的临界状态
if __name__ == '__main__':
obj = Solution()
while True:
try:
num = int(input().strip().split()[-1])
print(obj.mySqrt(num))
except EOFError:
break
'''
367. 有效的完全平方数
题目描述：给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1:
输入：num = 16
输出：true
题眼：隐藏有序数组且无重复：1、2...x-1、x
思路：二分查找 —— 和 “69. x 的平方根”题目一样
'''
class Solution:
def isPerfectSquare(self, num: int) -> bool:
left, right = 1, num
while left <= right:
mid = left + (right - left) // 2
if mid * mid > num:
right = mid - 1
elif mid * mid < num:
left = mid + 1
else:
return True
# 在序列中，但是找不到target
return False
if __name__ == '__main__':
obj = Solution()
while True:
try:
num = int(input().strip().split()[-1])
print(obj.isPerfectSquare(num))
except EOFError:
break
'''
633. 平方数之和
题目描述：给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1:
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5
题眼：隐藏有序数组且无重复：0、1、2...c-1、c
思路：这道题最核心的就是要想到 双指针法 的下边界是int(sqrt(c))——也可以直接调用sqrt函数，否则会超时
'''
import math
class Solution:
def judgeSquareSum(self, c: int) -> bool:
# 第一步，二分查找找到c的 平方根的整数部分
# sqrtV = self.searchSqrt(c)
sqrtV = int(math.sqrt(c))
# 第二步，双指针法判断c是否是两个平方数之和
left, right = 0, sqrtV
while left <= right:
if left * left + right * right > c:
right -= 1
elif left * left + right * right < c:
left += 1
else:
return True
return False
# def searchSqrt(self, c: int) -> int:
# left, right = 0, c
# while left <= right:
# mid = left + (right - left) // 2
# if mid * mid > c:
# right = mid - 1
# elif mid * mid < c:
# left = mid + 1
# else:
# return mid
# return right # 掌握循环跳出时的临界状态
if __name__ == '__main__':
obj = Solution()
while True:
try:
num = int(input().strip().split()[-1])
print(obj.judgeSquareSum(num))
except EOFError:
break
个人总结体会
1、对于 隐藏有序序列的数学类型 的二分法的使用，同时把target值也隐藏了，目前遇到的题目都是把target默认为均方根值，在明白到这一点之后，继续根据二分查找（Binary Search）（一、基于索引（定义域）的类型）掌握的关键点：准确把握循环终止时的状态，即left和right指针的相对位置关系（左闭右闭区间法则下是left-right=1），就能轻松应对这类题目。
2、对于"633. 平方数之和"这种复合型的题目，第一步用二分法找到均方根值（边界位置）、第二步用双指针判断是否是平方数，思路上不是一下子就能想到，还是要多加练习…
