leetcode题目按类型
双指针
快慢指针框架
- 判断是否有环
1
2
3
4
5
6
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
- 寻找环的起始节点
- 找到相遇节点
- 让slow指向head
- slow和fast都一次一步
- 相遇节点即为起始节点（又走了k-m步）
滑动窗口框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def slidingWindow(s:str, t:str):
need = set(c)
window = set()
left, right = 0, 0
valid = 0 # 注意
while right < len(s):
# 增大窗口
c = s[right]
window.add(s[right])
right += 1
print("window:", left, right)
while ...: # window needs shrink
# 缩小窗口
d = s[left]
window.remove(s[left])
left += 1
void slidingWindow(string s, string t){
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// 增⼤窗⼝
c = s[right]
window.add(s[right]);
right++;
// 窗口内数据更新
// ...
printf("window:[d%,d%)\n", left, right);
while (window needs shrink) {
// 缩⼩窗⼝
d = s[left]
window.remove(s[left]);
left++;
// 窗口内数据更新
// ...
}
}
}
经典，双指针定义, 典型例题，注意去重操作:
当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N^2) 减少至 O(N)。为什么是 O(N) 呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置(也就是题目中的 b)，而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)。
链接：https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
总结
-
双指针应用有哪些？
- 快慢指针
- 判断链表有环
- 返回环的起始位置
- 找无环单链表中点
- 左右指针
- 二分搜索
- 两数之和
- 反转数组
- 滑动窗口法
- 快慢指针
🚩 3.寻找最长无重复字符串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
1
shi'li：输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
2️⃣
1
# 自己写的s = "abcabcbb"lists = list(s)start = 0end = 0noduplicate = []length_max = 0for i, item in enumerate(lists,1): if item not in noduplicate: length_new = i - start noduplicate.append(item) if length_new > length_max: length_max = length_new else: start += noduplicate.index(item) + 1length_max
1
# 主要思想:滑动窗口 s = "abcabcbb"# s = "abca"# s = "pwwkew"class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: 0 left = 0 lookup = set() n = len(s) max_len = 0 cur_len = 0 for i in range(n): cur_len += 1 while s[i] in lookup: lookup.remove(s[left]) left += 1 cur_len -= 1 if cur_len > max_len:max_len = cur_len lookup.add(s[i]) # 新建了一个滑动窗口 return max_lensolution = Solution() # 实例化!!!!!solution.lengthOfLongestSubstring(s)print((solution.lengthOfLongestSubstring(s)))
✅(20m) 26. 删除排序数组中的重复项
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
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
27
28
29
30
31
32
示例 1:
给定数组 nums = [1,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。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
1
2
3
4
5
6
7
8
9
10
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
l = 1
for i in range(1,len(nums)):
if nums[i] == nums[i-1]:
continue
else:
nums[l] = nums[i]
l += 1
return l
🚩(40m) 15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
1
2
3
4
5
6
7
8
9
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
2️⃣双指针格式
1
2
3
4
5
6
7
8
9
10
11
while :
if
i += 1
if
j -= 1
for i in range():
if :
j -= 1
2️⃣ (90m)
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
27
28
29
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
n = len(nums)
if n < 3: return []
res = []
for i in range(n):
# 如果第一个数都＞0，和不可能==0；
# 保证和上一次枚举数不同(去重)
if i>0 and nums[i] == nums[i-1]:
continue
k = n - 1 # 第三个指针指向最右端
target = -nums[i]
for j in range(i+1, n):
# 保证除了紧邻上一个的位置外，和上一次枚举数不同(去重)
if j > i+1 and nums[j] == nums[j-1]:
continue
# 指针j 在 指针k 左侧
while j < k and nums[j] + nums[k] > target:
k -= 1
if j == k:
break
if nums[j] + nums[k] == target:
res.append([nums[i],nums[j],nums[k]])
return res
1
2
3
4
5
nums = [-1, 0, 1, 2, -1, -4]
solution = Solution()
result = solution.threeSum(nums)
result
1
2
3
a = [1,2]
a.index(2)
a.index?
2️⃣(1.5h)
3️⃣(30m) 模板法
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
27
28
29
30
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
def twoSum(nums,start,target):
res = []
lo, hi = start,len(nums)-1
while lo < hi:
left, right = lo, hi
if nums[lo] + nums[hi] < target:
lo += 1
elif nums[lo] + nums[hi] > target:
hi -= 1
elif nums[lo] + nums[hi] == target:
res.append([nums[lo],nums[hi]])
while lo<hi and nums[lo] == nums[left]:
lo += 1
while lo<hi and nums[hi] == nums[right]:
hi -= 1
return res
nums.sort()
res = []
target = 0
for i in range(len(nums)):
if 0<i<len(nums)-1 and nums[i] == nums[i-1]: # 需要加上i>0 条件，否则会漏掉前两个相同且只有三个元素的情况
continue
result_double = twoSum(nums,i+1,target-nums[i]) # from i-1
for result in result_double:
result.append(nums[i]) # 注意这里的写法
res.append(result[:])
return res
✅(50m) 11. (双指针)盛最多水的容器
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水(表示为蓝色部分)的最大值为 49。
1
2
3
4
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
1
# 动态规划 -- 自己写的，超时class Solution: def maxArea(self, height: List[int]) -> int: dp = [0 for _ in range(len(height))] for i in range(len(height)): if i == 0: continue dp[i] = max(dp[i-1], max(min(height[i], height[j]) * (i-j) for j in range(i))) return dp[-1]
1
# 双指针class Solution: def maxArea(self, height: List[int]) -> int: l, r = 0, len(height) - 1 ans = 0 while l < r: area = min(height[l], height[r]) * (r-l) ans = max(ans,area) if height[l] <= height[r]: l = l+1 else: r = r-1 return ans
2️⃣(20m)
1
# 双指针class Solution: def maxArea(self, height: List[int]) -> int: maxArea = 0 n = len(height) i, j = 0, n-1 while i < j: area = min(height[i], height[j]) * (j-i) maxArea = max(area, maxArea) if height[i] <= height[j]: # 判断哪个要动 i += 1 else: j-=1 return maxArea
1
from typing import Listnums = [1,8,6,2,5,4,8,3,7]solution = Solution()result = solution.maxArea(nums)result
1
✅（困难）(60m) 76. 最小覆盖子串
难度困难906
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
1
输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"
示例 2：
1
输入：s = "a", t = "a"输出："a"
2️⃣
1
class Solution: def minWindow(self, s: str, t: str) -> str: need=collections.Counter(t) window=collections.Counter() left, right = 0, 0 start, minlen = 0, float('inf') valid = 0 while right < len(s): c = s[right] right += 1 # 注意只有等于的时候添加，则不会出现重复添加的情况 if c in need: window[c] += 1 if window[c]==need[c]: valid+=1 # print(left, right) # print(need, window) while valid==len(need): if right-left<minlen: start, minlen = left, right-left d = s[left] left += 1 if d in need: if window[d] == need[d]: valid -= 1 window[d] -= 1 return "" if minlen == float('inf') else s[start: start+minlen]
总结：
- counter是计数器
✅ (20m)567. 字符串的排列
难度中等222
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
1
2
3
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
1
2
输入: s1= "ab" s2 = "eidboaoo"
输出: False
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
27
28
29
30
31
32
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
need=collections.Counter(s1)
window=collections.Counter()
left, right = 0, 0
valid = 0
while right < len(s2):
c = s2[right]
right += 1
# 进行数据更新
if c in need:
window[c] += 1
if window[c] == need[c]:
valid += 1
while right - left >= len(s1):
# if minlen > right - left:
# start = left
# minlen = right - left
if valid == len(need):
return True
d = s2[left]
left += 1
# 进行数据更新
if d in need:
if window[d] == need[d]:
valid -= 1
window[d]-=1
return False
2️⃣
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
need = collections.Counter(s1)
window = collections.Counter
if len(s1)>len(s2):
return False
for i in range(0,len(s2)-len(s1)+1):
print(window(s2[i:i+len(s1)]), need)
if window(s2[i:i+len(s1)]) == need:
return True
return False
✅(20m)438. 找到字符串中所有字母异位词
难度中等450
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 1:
1
2
3
4
5
6
7
8
9
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
示例 2:
1
输入:s: "abab" p: "ab"输出:[0, 1, 2]解释:起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
1
class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: need=collections.Counter(p) window=collections.Counter() left, right = 0, 0 valid = 0 ans = [] while right < len(s): c = s[right] right += 1 # 进行数据更新 if c in need: window[c] += 1 if window[c] == need[c]: valid += 1 while right - left >= len(p): if valid == len(need): ans.append(left) d = s[left] left += 1 # 进行数据更新 if d in need: if window[d] == need[d]: valid -= 1 window[d]-=1 # print("window: [{}, {}], win:{}, res:{}\n".format(left, right, window, ans)) return ans
###
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# if not s: return 0
window=collections.Counter()
left, right = 0, 0
ans = 0
while right < len(s):
c = s[right]
right += 1
# 进行数据更新
# if c in need:
window[c] += 1
print("window: [{}, {}], ans:{}\n".format(left, right, ans))
while window[c] > 1:
d = s[left]
left += 1
# 进行数据更新
window[d]-=1
print("window: [{}, {}], ans:{}\n".format(left, right, ans))
ans = max(ans, right - left) # 注意这个位置，是需要在非window[c]>1的情况下进行
return ans
🚩 6. 最接近的三数之和
难度中等627
给定一个包括 n 个整数的数组 nums _和 一个目标值 target。找出 nums _中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
1
2
3
4
5
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
🚩 (2.5h) 42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。
1
2
3
4
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
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
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
def onelist(self, List):
Dict1 = {}
for i in range(len(List)):
if List[i] not in Dict1:
Dict1[List[i]]=[i]
else:
Dict1[List[i]].append(i)
Dict1 = dict(sorted(Dict1.items(), key=lambda Dict1:Dict1[0], reverse=True)) # 字典排序方法
print(Dict1)
rainNum = 0
p = 0
for num, i in Dict1.items():
for j in i:
print('******\n',num,j)
if j <= p:
continue
count = num*(j-p-1)-sum(List[i] for i in range(p+1,j))
print('p=',p,'count=',count)
p = j
rainNum += count
print('p=',p,'rain=',rainNum)
return rainNum
def trap(self, height):
nums = height
if len(nums)==0: return 0
max_num = max(nums)
i_max = nums.index(max_num)
list1 = nums[:i_max+1]
list1.reverse()
list2 = nums[i_max:]
out1 = self.onelist(list1)
out2 = self.onelist(list2)
return out1 + out2
1
2
3
4
nums = [0,1,0,2,1,0,1,3,2,1,2,1]
solution = Solution()
result = solution.trap(nums)
result
2️⃣
✅ 283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
1
2
3
4
5
6
7
8
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 自己写的,费时 数组操作
class Solution:
def moveZeroes(self, nums) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
count = 0
while True:
try:
nums.remove(0)
count += 1
except:
nums.extend([0]*count)
break
nums = [0,1,0,3,12]
solution = Solution()
result = solution.moveZeroes(nums)
nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 法2: 一次遍历,双指针,检测到0则交换,省时间
class Solution:
def moveZeroes(self, nums) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums:
return 0
j = 0
for i in range(len(nums)):
if nums[i] != 0: # 只有nums[i] != 0 时,j才会加1往前走
nums[j],nums[i] == nums[i],nums[j]
j += 1
nums = [0,1,0,3,12]
solution = Solution()
result = solution.moveZeroes(nums)
nums
✅(30m) 19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：
1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
1
2
输入：head = [1], n = 1
输出：[]
示例 3：
1
2
输入：head = [1,2], n = 1
输出：[1]
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
27
28
29
30
31
32
33
34
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = head
slow = fast = head
for _ in range(n):
if fast:
fast = fast.next
else:
print('there')
return dummy
# 说明删除的是第一个
if not fast:
return dummy.next
else:
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
# slow.val = slow.next.val
# slow.next = slow.next.next
slow.next = slow.next.next
return dummy
# 90.88%
# 92.07%
