上次刷没刷完整,和李哥做字节的题感觉先前刷的题白刷了,故打算从头到尾完整走一遍。
二分法
1-1.二分查找
给定一个 n
个元素有序的(升序)整型数组 nums
和一个目标值 target
,写一个函数搜索 nums
中的 target
,如果目标值存在返回下标,否则返回 -1
。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示:
- 你可以假设 nums 中的所有元素是不重复的。
- n 将在 [1, 10000]之间。
- nums 的每个元素都将在 [-9999, 9999]之间
class Solution:
def search(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)-1
while l < r:
mid = l + r + 1 >> 1
if nums[mid] > target:
r = mid - 1
else:
l = mid
if nums[l] == target:
return l
return -1
RE了一次,原因是r的右侧初始化写成了len(nums)
1-2.搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)
的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
- 1 <= nums.length <= 1e4
- -1e4 <= nums[i] <= 1e4
- nums 为 无重复元素 的 升序 排列数组
- -1e4 <= target <= 1e4
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)-1
while l<r:
mid = l + r + 1 >> 1
if nums[mid] < target:
l = mid
else:
r = mid - 1
if nums[l] < target:
return l + 1
return l
一直WA,两个板子
第一个板子就是找第一个小于target值的位置,所以位置不能取到外面
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l,r = 0,len(nums)
while l<r:
mid = l + r >> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return l
这里和上面不一样,这里可以取到数组外面,我们找到的是第一个大于等于target的位置,所以可能取到len(nums)
总结:务必考虑清楚找到的是什么,然后敲定范围
1-3.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0
输出:[-1,-1]
提示:
- 0 <= nums.length <= 1e5
- -1e9 <= nums[i] <= 1e9
- nums 是一个非递减数组
- -1e9 <= target <= 1e9
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left,right = -1,-1
if len(nums) == 0:
return [-1,-1]
l,r = 0,len(nums) - 1
while l < r:
mid = l + r >> 1
if nums[mid] >= target:
r = mid
else:
l = mid + 1
if nums[l] == target:
left = l
l,r = 0,len(nums) - 1
while l < r:
mid = l + r + 1 >> 1
if nums[mid] <= target:
l = mid
else:
r = mid - 1
if nums[l] == target:
right = l
return [left,right]
一次AC了,但存在两个编写时的问题
一是一开始left和right搞反了,上面是>=,所以是第一个大于等于target的位置,所以是左侧。相反下面的为右侧。
二是 nums = [], target = 0 RE了,特判一下
1-4.x 的平方根
给你一个非负整数 x
,计算并返回 x
的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
或者 x ** 0.5
。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
- 0 <= x <= 2^31 - 1
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0: return 0
if x <= 3: return 1
l,r = 1, x // 2
while l < r:
mid = l + r + 1 >> 1
if mid * mid > x:
r = mid - 1
else:
l = mid
return l
一次AC了,可能就是要考虑是大于x时才是不可能的完全不可能的情况,平方根乘起来必然<=target
1-5.有效的完全平方数
给定一个 正整数 num ,编写一个函数,如果 num
是一个完全平方数,则返回 true
,否则返回 false
。
进阶:不要使用任何内置的库函数,如 sqrt
。
示例 1:
输入:num = 16
输出:true
示例 2:
输入:num = 14
输出:false
提示:
1 <= num <= 2^31 - 1
class Solution:
def isPerfectSquare(self, num: int) -> bool:
l,r = 1,num//2
while l < r:
mid = l + r + 1>> 1
if mid * mid <= num:
l = mid
else:
r = mid - 1
if l * l == num:
return True
return False
一次AC了,就是上一题
双指针
快慢指针,首尾指针
2-1.移除元素
给你一个数组 nums
和一个值 val
,你需要 原地
移除所有数值等于 val
的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1)
额外空间并 原地
修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。
示例 2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示:
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
l,r = 0,0
while r < len(nums):
if nums[r] != val:
# nums[r],nums[l] = nums[l],nums[r]
nums[l] = nums[r]
l += 1
r += 1
return l
一次AC了,但是注意注释部分,由于只需要保留前面一部分,并且只会以r指针作为判断,所以只需要交换一次
2-2.删除排序数组中的重复项
26. 删除有序数组中的重复项 - 力扣(LeetCode)
给你一个 升序排列 的数组 nums
,请你 原地
删除重复出现的元素,使每个元素 只出现一次
,返回删除后数组的新长度。元素的相对顺序 应该保持一致。
由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k
个元素,那么 nums 的前 k
个元素应该保存最终结果。
将最终结果插入 nums
的前 k
个位置后返回 k
。
不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1)
额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过,那么您的题解将被 通过。
示例 1:
输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2:
输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示:
- 1 <= nums.length <= 3 * 10^4
- -10^4 <= nums[i] <= 10^4
- nums 已按 升序 排列
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
s,t = 0,1
while t < len(nums):
if nums[s] != nums[t]:
s += 1
nums[s] = nums[t]
t += 1
return s + 1
一次AC,但是要注意s,t的初始化,其中较快的t指针如果和较慢的s指针说指向的值不相等的话,就将s指针的下一个位置的值赋新值
2-3.移动零
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
- 1 <= nums.length <= 104
- -231 <= nums[i] <= 231 - 1
进阶:你能尽量减少完成的操作次数吗?
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
s,t = 0,0
while t < len(nums):
if nums[t] != 0:
nums[s],nums[t] = nums[t],nums[s]
s += 1
t += 1
return
将第一题的target指定为0
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
s,t = 0,0
while t < len(nums):
if nums[t] != 0:
nums[s] = nums[t]
s += 1
t += 1
for i in range(s,len(nums)):
nums[i] = 0
return
优化就是第一题加上将后面无用部分直接赋值为0
2-4.比较含退格的字符串
给定 s
和 t
两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true
。#
代表退格字符。
注意:如果对空文本输入退格字符,文本继续为空。
示例 1:
输入:s = "ab#c", t = "ad#c"
输出:true
解释:s 和 t 都会变成 "ac"。
示例 2:
输入:s = "ab##", t = "c#d#"
输出:true
解释:s 和 t 都会变成 ""。
示例 3:
输入:s = "a#c", t = "b"
输出:false
解释:s 会变成 "c",但 t 仍然是 "b"。
提示:
- 1 <= s.length, t.length <= 200
- s 和 t 只含有小写字母以及字符 '#'
进阶:
你可以用 O(n)
的时间复杂度和 O(1)
的空间复杂度解决该问题吗?
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
s = list(s)
t = list(t)
i, j = 0, 0
while j < len(s):
s[i] = s[j]
if s[j] == '#':
if i <= 1:
i = -1
else:
i -= 2
i += 1
j += 1
k, j = 0, 0
while j < len(t):
t[k] = t[j]
if t[j] == '#':
if k <= 1:
k = -1
else:
k -= 2
k += 1
j += 1
if i != k:
return False
# print(s,t)
for n in range(k):
if s[n] != t[n]:
return False
return True
WA了两次,一开始考虑在原始字符串上替换实现,但是python字符串不可变,故实际上不满足。
拆分字符串使用list(s)即可
WA两次的原因:
第一没有考虑倒退“过猛”的情况
"y#fo##f" "y#f#o##f"
第二个字符串由于连续两个#,
if i > 0: i -= 2
会退的太厉害
修改之后还是WA了,原因是修改成
if i <= 1: i = 0
else: i -= 2
这样其实是倒退不足我们后面i必然会+1,所以要多退1个位置
进阶写法:
从后向前遍历,在每个字符串上指定一个遍历指针和一个回退计数值
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
a, b = len(s) - 1, len(t) - 1
sb,tb = 0,0
while a >= 0 or b >= 0 :
while a >= 0:
if s[a] == '#':
sb += 1
a -= 1
else:
if sb > 0:
sb -= 1
a -= 1
else:
break
while b >= 0:
if t[b] == '#':
tb += 1
b -= 1
else:
if tb > 0:
tb -= 1
b -= 1
else:
break
# 都结束了
if a < 0 and b < 0:
return True
# 都没结束
if a >= 0 and b >= 0 and s[a] != t[b]:
return False
# 一个结束了一个没结束
if (a >= 0 and b < 0) or (a < 0 and b >= 0):
return False
a -= 1
b -= 1
# 长度不一样长
if a >= 0 or b >= 0:
return False
return True
WA了两次
第一次是
"bbbextm"
"bbb#extm"
缺少最后长度不同情况下的判断
第二次是
"nzp#o#g"
"b#nzp#o#g"
将最外层循环的or写成了and,使得较长的串无法完全遍历
2-5.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
示例 2:
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
提示:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 已按 非递减顺序 排序
进阶:
请你设计时间复杂度为 O(n) 的算法解决本问题
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
res = []
i, j = 0, len(nums) - 1
while i <= j:
if nums[i] * nums[i] < nums[j] * nums[j]:
res.append(nums[j] * nums[j])
j -= 1
else:
res.append(nums[i] * nums[i])
i += 1
return res[::-1]
一次AC了
要注意是先从大到小插入,中间可能为较小的值。从小到大不行,可能中间的平方比两边小
[-7,-3,2,3,11]
2-6.长度最小的子数组
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其和 ≥ target
的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回 0
。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
提示:
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
进阶:
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
涉及连续子数组的问题,我们通常有两种思路:一是滑动窗口、二是前缀和。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
l, r = 0, 0
s = nums[0]
res = 0
while r < len(nums):
while s < target:
r += 1
if r == len(nums):
break
s += nums[r]
while s >= target:
if res == 0:
res = r - l + 1
else:
res = min(res, r - l + 1)
s -= nums[l]
if l == r:
break
l += 1
return res
WA了两次,主要是看错了题目,题目要求是>=target即可,看成了==target
在对指针做加减时务必留意是否是用变换后的值进行诸如求和之类的计算
上面写的非常膈应,优化如下:
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if not nums:
return 0
l, r = 0, 0
s = 0
res = len(nums) + 1
while r < len(nums):
s += nums[r]
while s >= target:
res = min(res, r - l + 1)
s -= nums[l]
l += 1
r += 1
if res == len(nums) + 1:
return 0
return res
参考官解的简洁写法
首先是优化了res的判断,将它置为长度+1,这是永远不可能出现的情况
接着是循环,设置初始和s为0,每次循环必然加上一次nums[r],去掉一个小于target的判断,我们只用考虑>=的情况,由于r每次都+1,可以遍历完全部可能的情况。
进阶:
利用 nums[i] 的数据范围为1 ~ 10^5,可知前缀和数组满足单调递增。??待补
滑动窗口形式的双指针(前后指针)
2-7.水果成篮
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits
表示,其中 fruits[i]
是第 i
棵树上的水果 种类 。
你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。
给你一个整数数组 fruits
,返回你可以收集的水果的 最大 数目。
示例 1:
输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。
示例 2:
输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。
示例 3:
输入:fruits = [1,2,3,2,2]
输出:4
解释:可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。
示例 4:
输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出:5
解释:可以采摘 [1,2,1,1,2] 这五棵树。
提示:
- 1 <= fruits.length <= 10^5
- 0 <= fruits[i] < fruits.length
不会
转换题意:
给定一个序列,求的是长度最长的,最多只包含两个不同元素的区间的长度
使用双指针,首先明确两个指针的定义
i为较快的那个指针,j为距离i最远的那个使得区间仅包含两个不同元素的指针。
使用双指针时要证明其单调性,反证法百试不厌。如果i往后移动到i',j往前移动是j',那么在i时就应该是j',矛盾。
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
i, j = 0, 0
cnt = collections.defaultdict(int)
s = 0
res = 0
while i < len(fruits):
cnt[fruits[i]] += 1
if cnt[fruits[i]] == 1:
s += 1
while s > 2:
cnt[fruits[j]] -= 1
if cnt[fruits[j]] == 0:
s -= 1
j += 1
res = max(res, i - j + 1)
i += 1
return res
可以看到写法与上一题的基本一致,先写后面指针的变化,再根据根据条件判断前面指针的变动
2-8.最小覆盖子串
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 ""
。
注意:
对于 t
中重复字符,我们寻找的子字符串中该字符数量必须不少于 t
中该字符数量。
如果 s
中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
示例 2:
输入:s = "a", t = "a"
输出:"a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。
提示:
- 1 <= s.length, t.length <= 10^5
- s 和 t 由英文字母组成
进阶:你能设计一个在 o(n)
时间内解决此问题的算法吗?
class Solution:
def minWindow(self, s: str, t: str) -> str:
cnt = collections.defaultdict(int)
res = collections.defaultdict(int)
for a in t:
cnt[a] += 1
n = len(t)
m = 0
i, j = 0, 0
ans = ''
while i < len(s):
res[s[i]] += 1
if cnt[s[i]] >= res[s[i]]:
# 有效增加
m += 1
while j <= i and res[s[j]] > cnt[s[j]]:
res[s[j]] -= 1
j += 1
if m == n:
if len(ans) > (i - j + 1) or ans == '':
ans = s[j: i + 1]
i += 1
return ans
写不出来
和上面几题一个思路,就是如何知道使用hash,如何判定两个hash相同
首先用两个hash相对来说比较方便
其次是判断的话由于我们固定了一个hash表,另一个待比较的hash表在超过这个固定hash的值时我们可以认为他是无效的。
最后是j如何前进,我们的j位置多余时才能前进,也就时hash值比固定的多的时候
需要注意的是j变化需要设置j <= i,否则RE
i的更新我们可以认定为必然更新。
模拟
3-1.螺旋矩阵 II
给你一个正整数 n
,生成一个包含 1
到 n^2
所有元素,且元素按顺时针顺序螺旋排列的 n x n
正方形矩阵 matrix
。
示例 1:
输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]
示例 2:
输入:n = 1
输出:[[1]]
提示:
- 1 <= n <= 20
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
ans = [[0 for i in range(n)] for i in range(n)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
i, j = 0, 0
cnt = 1
index = 0
while cnt <= n * n:
ans[i][j] = cnt
ti = i + dx[index]
tj = j + dy[index]
if ti >= 0 and ti < n and tj >= 0 and tj < n and ans[ti][tj] == 0:
i = ti
j = tj
else:
index = (index + 1) % 4
i += dx[index]
j += dy[index]
cnt += 1
return ans
一次AC了,要注意向右是y变换,向下是x变换
边界判断不妨先假设成立,在判断是否成立,不成立再修改
3-2.螺旋矩阵
给你一个 m
行 n
列的矩阵 matrix
,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
示例 1:
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
示例 2:
输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]
提示:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 10
- -100 <=
matrix[i][j]
<= 100
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
ans = [[0 for i in range(n)] for i in range(n)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
i, j = 0, 0
cnt = 1
index = 0
while cnt <= n * n:
ans[i][j] = cnt
ti = i + dx[index]
tj = j + dy[index]
if ti >= 0 and ti < n and tj >= 0 and tj < n and ans[ti][tj] == 0:
i = ti
j = tj
else:
index = (index + 1) % 4
i += dx[index]
j += dy[index]
cnt += 1
return ans
一次AC,与上题反过来
小结
可以看出二分和滑动窗口多半是套路
纯双指针需要考虑使用什么样的指针
模拟题考虑怎么模拟
标签:target,nums,int,代码,示例,随想录,len,数组 From: https://www.cnblogs.com/ydssx7/p/16642223.html