Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

syx948/Leetcode_Python

Repository files navigation

Introduction:

关于LeetCode的计时,真的有点迷,还是主要看复杂度,不要过度关注计时吧。

刷题链接:

leetcode中文网:https://leetcode-cn.com/
leetcode英文网:https://leetcode.com/
Top100常见题:https://leetcode.com/problemset/top-100-liked-questions/

关于Python的详细题解记录在github,有兴趣的小伙伴可以关注下。 image.png

刷题记录:

题目 难度 时间复杂度 类型 完成度 方法
1.两数之和 Easy $O(n)$ 数组、哈希表 Done key为数,value为index保存字典,判断差是否在字典中出现过
2.两数相加 Medium $O(m+n)$ 链表 No 模拟加法的实现,注意进位
3.无重复字符的最长子串 Medium $O(n)$ 字符串 No 字典保存字符位置,判断是否在字典中出现过
4.两个有序数组的中位数 Medium $O(log(m+n))$ 数学 No 二分法,依次删除不满足条件的k/2个值
5.最长回文子串 Medium $O(n^2)$ 字符串 No 从中心向两边遍历,动态规划
7.整数反转 Easy $O(n)$ 字符串 Done 直接翻转
8.字符串转换整数 (atoi) Medium $O(n)$ 字符串 Done 主要是各种边界条件
9.回文数 Easy $O(n)$ 字符串 Done 翻转后判断是否相等
10.正则表达式匹配 Hard 字符串、递归 No 匹配符号
11.盛最多水的容器 Medium $O(n)$ 数组、双指针 Done 左右双指针谁小谁移动
13.罗马数字转整数 Easy $O(n)$ 数学、字符串 Done 注意需要正负号反转的这个数
14.最长公共前缀 Easy $O(mn)$ 字符串 No 水平或垂直比较
15.三数之和 Medium $O(n^2)$ 数组、双指针、哈希表 Done 排序然后双指针,哈希表判断
16.最接近的三个数之和 Medium $O(n^2)$ 双指针 No 同样是排序后双指针
17.电话号码的字母组合 Medium $O(4^M*3^N)$ 数组、回溯 No 每次对前面的字符串组成的字母组合进行遍历
19.删除链表的倒数第N个节点 Medium $O(n)$ 链表 Done 设置哑结点,快慢指针,遍历到第L-n个结点
20.有效的括号 Easy $O(n)$ 栈、字符串 Done 判断新符号和栈顶元素是否可消掉
21.合并两个有序链表 Easy $O(m+n)$ 链表 Done 递归不断接下一个较小结点
22.括号生成 Medium $O(2^{2N}*N)$ 字符串、回溯 No 左括号数小于n,右括号数小于左括号数
23.合并K个排序链表 Hard $O(kN)$ 链表、分置 No 归并;整个转换成list,排序,然后转变成链表
26.删除排序数组中的重复项 Easy $O(n)$ 数组、双指针 Done 双指针,第一个遍历,第二个保存有多少个重复元素
28.实现strStr() Easy $O(n)$ 字符串 Done 滑窗遍历,KMP
29.两数相除 Meidum 数学 Done 模拟除法的原理
31.下一个排列 Medium $O(n)$ 数组 No 围绕满足nums[k] < nums[k+1]的最大索引
32.最长有效括号 Hard $O(n^2)$ 字符串 No 动态规划
34.在排序数组中查找元素的第一个和最后一个位置 Medium $O(logn)$ 二分查找 No 通过二分查找寻找左右边界
36.有效的数独 Medium $O(1)$ 哈希表、数组 Done 按照定义解决
39.组合总和 Medium 回溯 No 回溯法不断寻找,要固定一个模板
40.组合总和II Medium 回溯 No 后续数组,需要不断更新,去除已经选择的数
42.接雨水 Hard $O(n)$ 数组、双指针 No 寻找左右两边柱子最大高度的最小值
43.字符串相乘 Medium $O(mn)$ 字符串、数学 Done 转换成数字相乘、竖式
45.跳跃游戏II Hard $O(n)$ 贪心,DP No dp[i] = max(dp[i], dp[j]+1) for j in [0,i-1] if nums[j] >= i-j
46.全排列 Medium 回溯 No 深刻理解回溯算法
47.全排列II Medium 回溯 Done 和上述类似,每次添加的时候加一个判断
48.旋转图像 Medium $O(n^2)$ 数组 Done 先翻转(颠倒)然后转置
49.子母异位词分组 Medium $O(nk)$ 哈希表 No 将排序后字符串或统计次数作为key,相同的字符串保存对应key的list中
50.Pow(x,n) Medium $O(logn)$ 二分查找 Done 递归求解,修改函数参数而不是对函数返回值累乘
53.最大子序列和 Easy $O(n)$ 数组、动态规划 Done $f(n) = max(f(n-1)+nums[n], nums[n])$
54.螺旋矩阵 Medium $O(mn)$ 数组 No 迭代m*n次,方向数组控制遍历方向,保存已经遍历过的点坐标
55.跳跃游戏 Medium $O(n)$ 贪心、数字 Done 每次获取当前步所能到达的最远距离
56.合并区间 Medium $O(nlogn)$ 排序、数组 No 按start排序,然后根据是否重叠拼接
59.螺旋矩阵II Medium $O(n^2)$ 数组 Done 方向指针,主要是方向的判断,顺时针遍历
62.不同路径 Meidum $O(1),O(mn)$ 排列组合、动态规划 Done 状态方程为上边和左边的状态求和
63.不同路径II Medium $O(mn)$ 动态规划 No 有障碍物的地方dp[i][j]为0
64.最小路径和 Medium $O(mn)$ DP Done dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
66.加一 Easy $O(n)$ 数学 Done 转换成字符串
69.x的平方根 Easy $(logn)$ 二分查找 No 关键是边界条件
70.爬楼梯 Easy $O(n)$ 数学 Done 斐波那契数列
72.编辑距离 Hard $O(n^2)$ DP No dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
74.搜索二维矩阵 Medium $O(n)$ 数组 Done 从右上遍历到左下
75.颜色分类 Medium $O(m)$ 排序 Done 遍历两次数组
76.最小覆盖子串 Hard $O(m+n)$ 滑窗法 No 移动左右窗口边界
77.组合 Medium 回溯 Done 类似17题,套用回溯模板
78.子集 Medium 回溯(递归) No 依然是回溯的写法吧
79.单词搜索 Medium 回溯,dfs No 遍历每一个点,然后将其作为字符串的起点进行dfs回溯
84.柱状图中最大的矩形 Hard $O(n)$ 栈 No 每次用栈只保存递增序列
88.合并两个有序数组 Easy $O(m+n)$ 归并 Done 归并思想,依次选择较小的元素进行拼接
90.子集II Medium 回溯 Done 回溯模板,判断重复,需要进行剪枝
92.反转链表II Medium $O(n)$ 链表 No 首先结点移动到反转起始位置,然后反转链表,直到反转的截止处
94.二叉树的中序遍历 Medium $O(n)$ 树、DFS Done 递归遍历,依次左根右
96.不同的二叉搜索树 Medium $O(n)$ 二叉树、DP,数学 No $C_0 = 1,C_{n+1} = \frac{2(2n+1)}{n+2}C_n$
98.验证二叉搜索树 Medium $O(n)$ 树、DFS No 中序遍历,判断是否满足递增序列
100.相同的树 Easy $O(n)$ 树、递归 Done 递归遍历判断每一个结点是否相同
101.对称二叉树 Easy $O(n)$ 二叉树 No 递归判断左右子树是否相等
102.二叉树的层次遍历 Medium $O(n)$ 二叉树、队列、BFS Done 分层遍历,循环遍历当前层的所有结点
103.二叉树的锯齿形层次遍历 Medium $O(n)$ DFS、二叉树、队列 Done 相比上一题增加一个奇偶的判断
104.二叉树的最大深度 Easy $O(n)$ 二叉树、递归 Done 递归遍历结点,求左右子树的深度
105.从前序与中序遍历序列构造二叉树 Medium $O(n)$ 二叉树、递归,DFS Done 先获取根结点,然后对左右子树递归调用
106.从中序与后序遍历序列构造二叉树 Medium $O(n)$ 二叉树、递归,DFS Done 同上,主要是中序遍历和后序遍历的识别
108.将有序数组转换为二叉搜索树 Medium $O(n)$ 二叉树、递归 Done 先得到根节点,然后左右子树遍历生成
110.平衡二叉树 Easy $O(n^2)$ 二叉树、递归,DFS No 判断每个结点左右子树的深度差是否小于1
111.二叉树的最小深度 Easy $O(n)$ 二叉树、迭代、BFS Done 类似分层遍历,左右子树均不存在时返回树深
112.路径总和 Easy $O(n)$ 二叉树、迭代、递归 No 遍历每一个结点,然后到叶节点判断sum
113.路径总和II Medium $O(n)$ 二叉树、迭代、递归、树的遍历 No 主要是递归和迭代的套路是啥
114.二叉树展开为链表 Meidum $O(n)$ 二叉树、链表、DFS No 关键是如何原地修改
118.杨辉三角 Easy $O(n^2)$ 数组 Done 根据上一层构建下一层,找到关系式即可
121.买卖股票的最佳时机 Easy $O(n)$ 数组 Done 两个变量,到目前为止的最小价格和最大利润
122.买卖股票的最佳时机II Easy $O(n)$ 数组、贪心 Done 不断添加波谷波峰
123.买卖股票的最佳时机III Medium $O(n)$ 动态规划 No 两次交易,分开简历状态转移方程
124.二叉树的最大路径和 Hard $O(n)$ DFS No 求每个结点作为根节点到叶节点的的最大路径和,不停更新全局变量
128.最长连续序列 Hard $O(n)$ 哈希表 No 将nums保存成set,如果num-1不在set中启动遍历
131.分割回文串 Medium 回溯 No 回溯法,s为空则保存,否则继续遍历,遍历所有头回文串
136.只出现一次的数字 Easy $O(n)$ 数组、哈希表、位运算 Done 统计次数、数学公式、异或
137.只出现一次的数字II Easy $O(n)$ 数组、哈希表、位运算 Done 很迷,此处位运算麻烦些
139.单词拆分 Medium $O(n^2)$ DP Done dp[i] = if dp[j] and s[j:i] in wordDict for j in range(0,i)
141.环形链表 Easy $O(n)$ 链表、双指针 Done 快慢指针或者设置特殊值然后判断
142.环形链表II Medium $O(n)$ 链表,双指针,哈希表 Done 哈希表保存已知结点位置,判断新节点是否在哈希表中
144.二叉树的前序遍历 Easy $O(n)$ 二叉树、DFS Done 递归遍历,根左右结点
145.二叉树的后序遍历 Medium $O(n)$ 二叉树、DFS Done 递归遍历,左右跟结点
146.LRU缓存机制 Medium $O(1)$ 哈希表 No 使用有序字典来实现
148.排序链表 Medium $O(nlogn)$ 链表、排序 Done 先放在一个数组里面排序,然后重新生成链表
151.翻转字符串里的单词 Medium $O(n)$ 字符串 Done split,拆分,倒序,拼接
152.乘积最大子序列 Medium $O(n^3)$ 数组 No $fmax(i) = max(fmax(i-1)*num[i], fmin(i-1)*num[i], num[i]),fmin(i) = min(fmax(i-1)*num[i], min(i-1)*num[i], num[i])$
153.寻找旋转排序数组中的最小值 Medium $O(logn)$ 数组,二分查找 No mid和right比较,截止条件是left<right
154.寻找旋转排序数组中的最小值 II Hard $O(logn)$ 数组、二分查找 Done 和上述类似,只需考虑重复值
155.最小栈 Easy $O(1)$ 栈 Done 建立辅助栈,push的时候和最小栈的栈顶元素比,决定哪个元素入栈
160.相交链表 Easy $O(m+n)$ 链表 Done 长链表先走,然后再一起走
167.两数之和 II-输入有序数组 Easy $O(n)$ 数组、双指针、二分查找 Done 双指针,前后遍历
169.求众数 Easy $O(n)$ 数组、哈希表 Done 哈希表(统计次数),排序返回中间元素
171.Excel表列序号 Easy $O(n)$ 数学 Done 模拟进制转换
172.阶乘后的零 Easy $O(logn)$ 数学 No 求每一部分因子为5的个数
179.最大数 Medium 数组、排序 No 关键是排序规则书写,熟悉key和cmp_to_key
189.旋转数组 Easy $O(1)$ 数组 Done 注意原地操作
190.点到二进制位 Easy $O(n)$ 位运算 Done 转换成二进制,zfill0填充,字符串翻转
191.位1的个数 Easy $O(n)$ 位运算 Done 转换成二进制,统计1的个数即可
198.打家劫舍 Easy $O(n)$ 动态规划 No $f(n) = max(f(n-1), f(n-2)+nums[n])$
200.岛屿数量 Medium $O(mn)$ dfs No 遍历每一个点,令1周围的1都变成0
201.数字范围按位与 Easy $O(n)$ 位运算 No 发现二进制的规律
202.快乐数 Easy 哈希表、数组 No 1-4之间只有1是快乐数,>4的非快乐数都会进入4或者3的循环序列
204.计算质数 Easy $O(n)$ 哈希表、数学 No 设置质数数组,然后让质数的倍数为False
206.反转链表 Easy $O(n)$ 链表 No 修改原链表的结点指向,然后赋值给目标结点
207.课程表 Medium $O(E+V)$ 图 No 拓扑排序
208.前缀树 Medium $O(n)$ 二叉树 No 字典实现这种数据结构
215.数组中的第K个最大的元素 Medium $O(n)$ 数组、堆 Done 利用最小堆实现
216.组合总和III Medium $O(n)$ 回溯 Done 回溯,加一个判断,判断长度
217.存在重复元素 Easy $O(n)$ 哈希表 Done 哈希表判断
219.存在重复元素II Easy $O(n) 哈希表 Done 哈希表保存每个数出现的位置,增加一个条件判断索引
220.存在重复元素III Medium $O(n)$ 桶排序 No 复杂度达不到要求
221.最大正方形 Medium $O(mn)$ DP No dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
225.用队列实现栈 Easy O(n) 队列、栈 No 将队列前面的元素依次出队,然后放在新元素的后面
226.翻转二叉树 Easy $O(n)$ 二叉树、递归 Done 交换左右子树,然后对左右子树递归
229.求众数II Medium $O(n)$ 数组、排序、哈希表 Done 哈希表统计次数
230.二叉搜索树中第k小的元素 Medium $O(n)$ 二叉树、dfs Done 中序遍历,得到排序数组
231.2的幂 Easy $log(n)$ 数学 Done 依次除以2,直到不能整除,判断最后是否是1;二进制1的个数
232.用栈实现队列 Easy O(n) 栈、队列 Done 建立一个辅助栈,stack2为空后将stack1的放进去
234.回文链表 Easy $O(n)$ 链表、指针 Done 转成数组然后判断是否是回文数组
235.二叉搜索树的最低公共祖先 Easy $O(n)$ 二叉树、dfs No 寻找最低的大于左结点小于右节点的结点值
236.二叉树的最低公共祖先 Medium $O(n)$ 二叉树,dfs No 求以node为根结点的子树是否出现过两个结点
237.删除链表中的结点 Easy $O(1)$ 链表 Done 鬼题目,只需分别对val和next赋值
238.除自身以外数组的乘积 Medium $O(n)$ 数组 Done 左右分别累乘,注意边界值
239.滑动窗口最大值 Hard $O(kn)$ 数组、堆、队列 Done 最优解不会
240.搜索二维矩阵II Medium $O(m+n)$ 数组、二分查找 Done 从左上遍历到右下
242.有效的字母异位词 Easy $O(n)$ 哈希表 Done Counter统计每个字符的次数
260.只出现一次的数字III Medium $O(n)$ 数组、哈希表 Done 我佛
263.丑数I Easy 数学 Done while不停判断是否有2,3,5因子,是否为1
264.丑数II Medium $O(1)$ 数组、DP No dp[i] = min(2*dp[p2],3*dp[p3],5*dp[p5])
268.缺失数字 Easy $O(n)$ 数学 Done 公式求解
279.完全平方数 Medium $O(n)$ 数学、DP No 动态规划超时,数学方法最优
283.移动零 Easy $O(n)$ 数组、双指针 Done 移除0,然后append0
287.寻找重复数 Medium $O(n),O(nlogn)$ 二分法、链表 No 同时满足多个条件比较麻烦
289.生命游戏 Medium $O(mn)$ 数组 Done 按照题意遍历既可以,每次判断
292.Nim游戏 Easy $O(1)$ 数学 Done 如果是4的倍数肯定会输
295.数据流中的中位数 Hard $O(n)$ 最小堆,二分 No 二分插入排序,优先队列,双堆
300.最长上升子序列 Medium $O(logn)$ 数组、贪心、DP No 依次添加比较小的数在辅助序列里面
309.最佳买卖股票时机含冷冻期 Medium $O(n)$ 动态规划 No 状态转移方程
312.戳气球 Hard $O(n^3)$ DP No dp[i][j] = max(nums[i]*nums[k] *nums[j]+dp[i][k]+dp[k][j])
315.计算右侧小于当前元素的个数 Medium $O(n)$ 数组 No 。。。
322.零钱兑换 Medium $O(Sn)$ 动态规划 No dp[i] = min(dp[i], dp[i-coin]+1) for coin in coins
326.3的幂 Easy $O(log(n))$ 数学 Done 循环遍历
328.奇偶链表 Medium $O(n)$ 链表 No 奇偶位置,分开保存在两个链表中
334.递增的三元子序列 Medium $O(n)$ 数组 Done 三元组判断
337.打家劫舍III Medium 动态规划、二叉树 No 一个二元数组代表是否包含根节点
338.比特位计数 Medium $O(32n)$ 二进制 Done 和191类似,无差别
343.整数拆分 Medium $O(1)$ 数组、DP No 找规律
344.反转字符串 Easy $O(n)$ 字符串 Done 原地翻转
347.前 K 个高频元素 Medium $O(n)$ 堆、哈希表 No 和215类似,但需要注意更多的地方
350.两个数组的交集II Easy $O(m,n)$ 数组、哈希表 Done Counter转成字典判断,排序后比较
371.两整数之和 Easy $O(n)$ 位运算 No 异或代表求和,与代表进位,二进制来求解
384.打乱数组 Medium $O(n)$ 数组 Done 做拷贝,利用random.shuffle打乱
387.字符串中的第一个唯一字符 Easy $O(n)$ 哈希表 Done 直接统计次数即可
392.判断子序列 Easy $O(n)$ 队列 Done 判断目标字符串,如果能匹配,则删除第一个字符
394.字符串解码 Medium $O(n)$ 栈 No ‘[’:括号外的字符串和出现次数入栈,']':括号内的字符串出栈
395.至少有k个重复字符的最长子串 Medium 递归、分治 No 对原始字符串进行拆解,然后递归调用
399.除法求值 Medium $O(n)$ 图、DFS No 转换成图,然后利用图结构求解
401.二进制手表 Easy $O(1)$ 数位运算 No 遍历所有的时间组合,然后求1的个数
406.根据身高重建队列 Medium $O(nlogn)$ 数组、排序 No 对身高降序排序,人数升序排序
410.分割数组的最大值 Hard $O(nlog(sum/k))$ 二分查找、贪心 No 遍历值,判断和是否存在
412.Fizz Buzz Easy $O(n)$ 数学 Done 直接遍历
416.分割等和子集 Medium $O(ns)$ DP No dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]],(nums[i] <= j)
414.第三大的数 Easy $O(n)$ 数组、堆 Done 和215类似,同时可以用规则
437.路径总和III Easy $O(n)$ 树、栈、递归 No 对题意的理解以及对树深度遍历的把控
438.找到字符串中所有字母异位词 Easy $O(n)$ 哈希表、滑窗法 No 滑窗法,不断移动左右边界来判断
448.找到所有数组中消失的数字 Easy $O(n)$ 数组、哈希表 Done 遍历,然后判断,按索引求反
461.汉明距离 Easy $O(n)$ 位运算 Done 做异或,然后统计1的个数
477.汉明距离总和 Medium $O(36*n)$ 位运算 No 不可两两异或,求每一位1的个数和0的个数,然后相乘求和
494.目标和 Medium $O(n^2)$ 背包问题 No 不懂,不会
496.下一个更大的元素I Easy $O(n)$ 栈、哈希表 Done 类似739题,都是相似的
503.下一个更大的元素II Medium $O(n)$ 栈 Done 和496类似,对nums做一个复制
509.斐波那契数列 Easy $O(n)$ DP Done DP展开
523.连续的子数组和 Medium $O(n^2)$ 数组 Done 和560相似,求子数组和即可
538.把二叉搜索树转换为累加树 Medium 二叉树、递归 No 反向中序遍历,先右子树,然后根节点累加,然后左子树
543.二叉树的直径 Easy $O(n)$ 二叉树、DFS No 和求树的深度一样,路径为L+R+1
557.翻转字符串中的单词III Easy $O(n)$ 字符串 Done 空格划分,然后单词内翻转
559.N叉树的最大深度 Easy $O(n)$ 二叉树 Done 类似普通二叉树的遍历,注意max的list不能为空
560.和为K的子数组 Medium $O(n)$ 哈希表、数组 No 保存累积求和出现的次数
581.最短无序连续子数组 Easy $O(nlogn)$ 数组、排序、栈 Done 先排序,然后比较不同元素的索引
617.合并二叉树 Easy $O(n)$ 二叉树、递归 Done 对每个子节点递归,判断根节点是否为空
647.回文子串 Medium $O(n^2)$ 字符串 Done 中心扩散
654.最大二叉树 Medium 二叉树、递归 Done 对整个数组和左右边数组依次递归调用
668.乘法表中的第k小的数 Hard $O(mlog(mn))$ 二分查找 No 太难了不会
704.二分查找 Easy $O(logn)$ 二分查找 Done 直接上模板
714.买卖股票的最佳时机含手续费 Medium $O(n)$ 数组、动态规划 Done 和122类似,弄懂122
739.每日温度 Medium $O(n)$ 栈 No 根据温度大小关系,不断将其入栈
746.使用最小花费爬楼梯 Easy $O(n)$ DP Done dp[i] = min(dp[i-1],dp[i-2]) + cost[i]
876.链表的中间结点 Easy $O(n)$ 链表,双指针 Done 快慢指针
1047.删除字符串中的所有相邻重复项 Medium $O(n)$ 栈、字符串 Done 新元素和栈顶元素比较
1103.分糖果II Easy $O(max(G,N))$ 数组 Done 依次添加新元素

About

Python刷Leetcode

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Jupyter Notebook 100.0%

AltStyle によって変換されたページ (->オリジナル) /