备注:
- 每个题解包含含题目、解题思路、python3程序、问题思考与解答
- 🟢表示”简单题“,🟡表示”中等题“,🔴表示”困难题“
-
2023年8月16日:上传了前6题的题解
-
2023年8月17日:
- 上传了0042接雨水的题解
- 笔记目录改为列表的形式
- 题目命名空格改为下划线
- 增加题目难易度
- 找到了一个很棒的力扣刷题插件labuladong 的算法小抄 | labuladong 的算法小抄
-
2023年8月22日:
- 复习0042接雨水的题解
- 之后的题解主要参考算法小抄中的**进行重述,加深印象
- 做了美团20数据岗笔试题寻找最高的山峰
- 滑动窗口开篇,晚上看了算法小抄
-
2023年8月23日:
- 做了滑动窗口0003最长无重复字串
- 更新了题解但是没怎看懂
- 体会:以后每天先一个简单题+一个hot100,要不要没自信了QAQ
-
2023年8月24日:
- 早上研读了算法小抄中关于滑动窗口的解说
- 更新了0009回文数的题解
- 调整项目目录格式
- 新增 收获 栏
- 更新了0438_找到字符串中所有字母异位词的题解
-
2023年8月29日:
- 更新了0013_罗马数字转整数的题解
- 总结了滑动窗口解题模板,还需进一步理解
-
2023年8月30日:
- 更新了0014_最长公共前缀的题解
- 更新了0560_和为K的子数组的题解
-
2023年8月30日:
- 更新了0020_有效的括号的题解
- 滑动窗口最大值问题没有搞明白
- 计划总结括号相关问题的题解
hot100序 | 题解链接 | 解法 | 考察知识 | 难度 | 总序 | 收获 |
---|---|---|---|---|---|---|
01 | 两数之和 | 1.暴力循环``2.哈希表 | 哈希 | 🟢 | 0001 | |
02 | 字母异位词分组 | 1.排序``2.计数 | 哈希 | 🟡 | 0049 | |
03 | 最长连续序列 | 1.哈希表 | 哈希 | 🟡 | 0128 | |
04 | 移动零 | 1.冒泡排序(超时)``2.快慢指针 | 指针 | 🟢 | 0283 | |
05 | 盛水最多的容器 | 1.对撞指针``2.暴力循环(超时) | 指针 | 🟡 | 0011 | |
06 | 三数之和 | 1.对撞指针 | 指针 | 🟡 | 0015 | |
07 | 接雨水 | 1.单调栈``2.韦恩图 | 指针 | 🔴 | 0042 | |
08 | 无重复最长字串 | 1.哈希表 <br> 2.滑动窗口 <br> 3.快慢指针 |
滑动窗口 | 🟡 | 0003 | |
09 | 找到字符串中所有字母异位词 | 1.哈希表 <br> 2.滑动窗口 <br> 3.快慢指针 |
滑动窗口 | 🟡 | 0438 | 1.总结滑动窗口解题模板 |
10 | 和为K的子数组 | 1.哈希表 <br> 2.前缀和 <br> |
字串 | 🟡 | 0560 | 1.定义默认字典a=collections.defaultdict(int)<br> 2.前缀和 |
刷题序 | 题解链接 | 解法 | 考察知识 | 总序 | 收获 |
---|---|---|---|---|---|
01 | 回文数 | 1.数学运算进行整数反转``2.转回字符串进行切片反转 | 数学 | 0009 | 1.取余 %<br> 2.字符串切片反转s [::-1] |
02 | 罗马数字转整数 | 1.哈希表存值,指针遍历累加 | 字符串、指针、哈希表 | 0023 | 1.给定字符串s可以直接取 s[0]<br> 2.字符串切片反转s [::-1] |
03 | 最长公共前缀 | 1.纵向遍历 <br> 2.巧用max/min(字符数组)按字典排序 |
字符数组 | 0014 | 1.max/min(字符数组)按字典排序 |
04 | 有效的括号 | 1.栈 <br> |
哈希表、栈 | 0014 | 1.使用栈进行括号关系判断 <br> 2.使用哈希表记录左右括号的关系 <br> 3.总结括号相关的问题的解法 |
import sys
# 这里写解决问题的代码,和LeetCode就完全一样了
def solve(arr):
pass
if __name__ == '__main__':
# 接收输入的逻辑,这里先把输入接收过来, 两种选择input()和sys.stdin.readline()
group_nums = input() #字符串形式,得转成int
group_nums = int(group_nums)
# 对于每一组
for i in range(group_nums):
# 接收每一组的输入, 这里不同的题目就不一样了,但一定记住我们接收的还是一行,这是一个字符串
arr = sys.stdin.readline().strip().split(' ')
# 元素转成int
arr = list(map(int, arr))
# 输入接收过来之后,这里最好打印下看看接收的是不是正确,这个很重要
# print(arr)
# 处理具体的问题了
res = solve(arr)
# 输出结果
print(res)
参考:我写了首诗,把滑动窗口算法算法变成了默写题 | labuladong 的算法小抄
这个算法技巧的思路非常简单,就是维护一个窗口,不断滑动,然后更新答案么。LeetCode 上有起码 10 道运用滑动窗口算法的题目,难度都是中等和困难。该算法的大致逻辑如下:
left = 0, right = 0
while left < right && right < len(s):
# 增大窗口
while window need shrink:
# 缩小窗口
以找到字符串中的所有字母异位词为例,详细的答题模板如下:
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
# 用合适的数据结构记录窗口中的数据,一般是哈希表,此处以哈希表为例
# 初始化目标字符串与滑动窗口的哈希表,字符做键,字符个数做值
need, window = defaultdict(int), defaultdict(int)
# 将给定字符串的属性赋值到已经初始化好的哈希表中
for c in p:
need[c] += 1
# 初始化快慢指针与返回值
left, right = 0, 0
res = []
'''初始化覆盖程度【本题用】
valid = 0
'''
# 判断是否还需要进行窗口滑动
while right < len(s):
c = s[right] # c是要加进窗口的字符
right += 1 # 扩大窗口
'''进行窗口内一系列数据的更新
if c in need:
window[c] += 1
if window[c] == need[c]:
valid += 1
'''
# 判断左侧窗口是否需要收缩(left < right and window needs shrink(这里是窗口的长度大于给定p的长度))
while right - left >= len(p):
'''当串口符合条件时,将起始索引加入res【本题用】
if valid == len(need):
res.append(left)
'''
d = s[left] # d是将移出窗口的字符
left += 1 # 增大左指针进行窗口收缩
'''进行窗口内一系列数据的更新
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
'''
return res
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
# 初始化目标字符串与滑动窗口的哈希表,字符做键,字符个数做值
need, window = defaultdict(int), defaultdict(int)
# 将给定字符串的属性赋值到已经初始化好的哈希表中
for c in p:
need[c] += 1
# 初始化快慢指针,覆盖程度与返回值
left, right = 0, 0
valid = 0
res = []
# 判断是否还需要进行窗口滑动
while right < len(s):
c = s[right] # c是要加进窗口的字符
right += 1 # 扩大窗口
# 进行窗口内一系列数据的更新
if c in need:
window[c] += 1
if window[c] == need[c]:
valid += 1
# 判断左侧窗口是否需要收缩(窗口的长度大于给定p的长度)
while right - left >= len(p):
# 当串口符合条件时,将起始索引加入res
if valid == len(need):
res.append(left)
d = s[left] # d是将移出窗口的字符
left += 1 # 增大左指针进行窗口收缩
# 进行窗口内一系列数据的更新
if d in need:
if window[d] == need[d]:
valid -= 1
window[d] -= 1
return res
思考:为什么这里不能交换位置?