- 来源于leetcode题库
11,15,75,287
11.盛最多水的容器
-
题目描述
- 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
- 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
-
示例
image.png -
题解
- 来自于题解区大佬
krahets，如有侵扰烦请联系删除
- 来自于题解区大佬
class Solution:
def maxArea(self, height: List[int]) -> int:
'''
双指针i,j分别位于两端，根据规则移动指针，更新最大值res
每次移动将两指针所在位置的短板向内收一格
因为面积是由短板决定的，不论短板移动还是长板移动j-i都会缩小1
但是短板内收一格后，min(height[i],height[j])可能会变大或不变
而长板内收一格后，min(height[i],height[j])只可能变小或不变
所以短板内收一格不会错过最大面积
'''
# i，j为双指针下标，res初始值为0
i, j, res = 0, len(height) - 1, 0
#只要双指针没有相交
while i < j:
# 面积由短板决定，所以面积=min(height[i],height[j]) * (j-i)
if height[i] < height[j]:
res = max(res, height[i] * (j - i))
i += 1 # 内收短板
else:
res = max(res, height[j] * (j - i))
j -= 1 # 内收短板
return res
15.三数之和
-
题目描述
- 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
示例
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
- 题解
- 题解来源于题解去大佬
krahets
- 题解来源于题解去大佬
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
'''
先将nums从小到大进行排序
设定三个指针：
固定最小数字的指针k
指针i,j分别位于(k,len(nums))的两端
'''
nums.sort()
res, k = [], 0
for k in range(len(nums) - 2):
# 数组是有序的，如果第一个数字大于0则直接退出
if nums[k] > 0:
break
# 如果nums[k] == nums[k-1]则跳过此元素，避免重复元素
if k > 0 and nums[k] == nums[k - 1]:
continue
# i，j分别位于k-len(nums)的两端
i, j = k + 1, len(nums) - 1
while i < j: # 循环啊
s = nums[k] + nums[i] + nums[j]
# 如果s<0,则将i+=1使总和变大
if s < 0:
i += 1
# 避免重复元素
while i < j and nums[i] == nums[i - 1]:
i += 1
# 如果s>0,则j-=1使总和减小
elif s > 0:
j -= 1
# 避免重复元素
while i < j and nums[j] == nums[j + 1]:
j -= 1
else:
#如果s=0，记录k,i,j
res.append([nums[k], nums[i], nums[j]])
# i+1,j-1，继续寻找并避免重复元素
i += 1
j -= 1
while i < j and nums[i] == nums[i - 1]: i += 1
while i < j and nums[j] == nums[j + 1]: j -= 1
return res
75.颜色分类
-
题目描述
- 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
- 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
示例
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
- 题解
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
p0, curr, p2 = 0, 0, len(nums) - 1
while curr <= p2:
if nums[curr] == 0: # 为0，做出决策
nums[p0], nums[curr] = nums[curr], nums[p0]
p0 += 1
curr += 1
elif nums[curr] == 2: # 为2，做出决策
nums[p2], nums[curr] = nums[curr], nums[p2]
p2 -= 1
else: # 为1，做出决策
curr += 1
287.寻找重复数
-
题目描述
- 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例
略
- 题解
- 题解来源于题解区大佬
liweiwei1419
- 题解来源于题解区大佬
#使用二分查找法
from typing import List
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
size = len(nums)
left = 1
right = size - 1
while left < right:
mid = left + (right - left) // 2
cnt = 0
for num in nums:
if num <= mid:
cnt += 1
# 根据抽屉原理，小于等于 4 的数的个数如果严格大于 4 个，
# 此时重复元素一定出现在 [1, 4] 区间里
if cnt > mid:
# 重复的元素一定出现在 [left, mid] 区间里
right = mid
else:
# if 分析正确了以后，else 搜索的区间就是 if 的反面
# [mid + 1, right]
left = mid + 1
return left
