用Python作答的LeetCode做题记录
我的 LeetCode 做题记录,使用 Python 语言作答。
Python 其它杂项
共1107Star
详细介绍
LeetCode-Solution-in-Good-Style
项目更名说明
- 在这里,特别感谢 @AbbyDeng 同学的更名建议;
- 我个人觉得代码的可读性是非常重要的,代码可读的前提是「格式良好」,在 Intellij Idea、PyCharm、CLion 中,我使用最多的快捷键就是
⌥ + ⌘ + L
(Reformate Code),希望看到这个项目的朋友们,即使是刷题这种纯粹是「自娱自乐」的项目,也能够做到格式良好,方便他人和自己阅读。
项目说明
-
本代码仓库是我在学习《算法与数据结构》的时候,在 LeetCode(力扣) 上做的练习 ;刷题以 Java 语言为主,Java 是我的编程入门语言,Python 是学习人工智能以后学习的语言,C++ 就只是在刷题的时候用,因为有 Java 的基础,边写边学;
-
所有的代码都是通过 LeetCode(力扣) 在线测评系统检测的,至少是正确的代码,但本人水平有限,所在代码仅供参考,欢迎您与我交流;
-
建议您安装 Octotree 插件,以获得最佳的阅读体验。
编码依据
在代码编写的过程中,我比较注意的地方有:
- 格式良好;
- 遵循代码规范。
我遵守的代码规范和使用的工具如下:
编程语言 | 代码规范 | 工具 |
---|---|---|
Java | 阿里巴巴 Java 开发手册 | Alibaba Java Coding Guidelines |
Python | PEP 8 -- Style Guide for Python Code | autopep8、 black |
C++ | Google Style Guides、Google 开源项目风格指南 (中文版) |
个人建议
- 编码规范的遵守依照「就近原则」,如果程序员所处团队指定了编码规范,则团队内部代码规范优先;
- 遵守格式良好和编码规范是一件很繁琐的事情,我们可以借助工具帮助我们完成,在 IDE 中安装上述插件,这些插件会对编码不规范的地方进行提示,并给出修改建议,能够帮助程序员养成良好的编码习惯。
使用的集成开发环境
使用 Jetbrains 公司开发的 IDE 工具。主要是为了使用代码格式化和扫描编码规范的插件:
- Java:Intellij Idea(Ultimate)
- Python:PyCharm(Ultimate)
- C++:CLion、Visual Studio Code(开源)
学习资源
我个人学习的资源如下,仅供大家参考。
1、书本
-
《算法 4》:一本颜值很高的书,使用 Java 编写,示例清楚,配图优雅。很适合新手学习。缺点是:翻译欠缺,给出的示例代码不规范,阅读起来让人觉得很困惑;
-
《算法导论》:当做工具书学习,其中的「动态规划」、「贪心算法」、「计数排序」、「基数排序」、「循环不变量」、「KMP」算法是讲解很细致的。缺点就是过于学术,不太适合算法和数据结构的入门教程。
2、网课与自媒体
- 慕课网 liuyubobobo 老师的算法与数据结构系列课程。我本人就是学习刘老师的课程入坑算法与数据结构的。(刘老师的课程是精心准备过,且是收费的,请大家自行判断是否需要购买。)
- 可以在哔哩哩哔和 youtub 上搜索一些优秀的自媒体,听他们讲题也是很不错的学习途径,我常收看的自媒体有:花花酱,程序员刀刀,一俩三四五、lee215215、胡小旭-_-、喂你脚下有坑、代码会说话等。
3、优秀的博客、公众号
- 在 2018 年,有一个制作算法动画的项目和公众号火了起来,让人耳目一新。公众号的名字叫「五分钟学算法」,博主叫「程序员吴师兄」,我在这个公众号上学习了很多东西,我现在的博客模板也是在吴师兄原来用的模板基础上做了修改。“程序员吴师兄”在很多平台上都可以搜索到他,欢迎大家关注。
4、加入一个学习团队,找到一两个小伙伴,刷题不会孤单
- 本人有幸加入了一个刷题 QQ 群(群号:812791932),如果刷题刷得比较烦躁,可以来群里和大家聊聊天,吹吹牛啥的。在群里提问,会有大佬、巨佬、巨巨佬回答你的哟;
- 最近「力扣」网站举办了「每日一题」,习惯用微信的朋友可以点击网址:https://ojeveryday.com/#/check,加群主微信,这个网页还会显示大家打卡的情况。
刷题建议
没有什么很特别的建议,但本人的确是通过以下的方式学习的。(仅供参考,本人只是个初学者。)
- 先学习,有一些预备知识以后,再做题
有些算法题做不出来很正常,那是因为自己的知识储备还不够。所以要么看书、看视频学习,要么就把这个不会做的问题当做知识点进行学习。一开始抄代码我觉得都是可以的,抄完代码要删掉了以后,自己再写几遍。
实在想了很久还想不出来的问题,就看题解和别人的视频学习哈。
- 要多做几遍,尝试做总结和分类
一道题,特别是经典的问题,要尝试多做几遍,作总结。有些问题的思想是通用的,而且技巧也是相对固定的,需要不断练习巩固和体会。
- 尝试一题多解,不要忽视暴力解法
一题多解,有些时候就相当于做了几遍了。“暴力解法”通常是进阶解法的基础,由“暴力解法”开始分析缺点,然后改进和优化,去理解这道题的解法通常是很自然的。
- 尝试输出,分享出去
较多程序员(包括我本人)相对欠缺的能力是语言表达和书面表达。而输出就是一个比较好的锻炼自己的方式,写博客写题解可以帮助到别人,也可以帮助自己整理思路,还可以交朋友。
我写题解以后,有很多朋友给出提出了建议,指出了错误,让我受益匪浅。有一些朋友加了我微信和 QQ,我很高兴与它们交流,成为朋友。
- 参加竞赛,练手
前面的题目可能就像课后练习一样,你做不做它就在那里,就有那么多,还可以看答案,做起来没什么动力。想模拟面试和笔试的感觉,就可以参加竞赛哦。
我最近两个月开始参加「力扣」的周赛和双周赛。刚开始的时候,因为有一些事情脱不开身,就只是打了个卡,一道题都没做。现在基本上 2 道题到 3 道题还是可以做出来的。难题赛后会进行学习,做一个笔记。
参加竞赛是一个很不错的学习途径,培养自己独立思考的能力,还可以与他人互动。
如果是已经工作的朋友,竞赛的第 4 题可以不做,竞赛是一个查缺补漏的过程,有些知识可能目前或者是一辈子都用不到的知识,可以不用掌握。
希望我们程序员都能够通过自己的努力,实现自己的理想;
希望我们程序员不再是别人眼里的刻板印象,我们也是艺术家;
希望我们大家都能在自己的工作领域里有所成绩。很高兴和大家成为朋友。
「力扣」2020 年 4 月每日一题做题记录
「力扣」2020 年 5 月每日一题做题记录
日期 | 题目 | 难度 | 题解 |
---|---|---|---|
5 月 1 日 | 21. 合并两个有序链表 | 简单 | |
5 月 2 日 | 3. 无重复字符的最长子串 | 中等 | |
5 月 3 日 | 53. 最大子序和 | 中等 | |
5 月 4 日 | 45. 跳跃游戏 II | 困难 | |
5 月 5 日 | 98. 验证二叉搜索树 | 中等 | |
5 月 6 日 | 983. 最低票价 | 中等 |
我在「力扣」圈子里回答的问题
[在java和c#中Am-1]=A[m-- - 1];而在C中A[m-1]!=A[m-- - 1];
题解分类(正在更新)
排序
「力扣」第 912 题:排序数组 的题解:复习基础排序算法(Java)总结了排序问题的一些要点和学习资料,可以从排序问题开始学习算法。
数组
数组的问题可以作为「新手场」,因为这些问题只需要掌握编程语言的基础知识就可以完成。
以下这些问题都是很容易想到思路的问题,即使没有学习过相关的数据结构和算法知识。
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
26. 删除排序数组中的重复项(简单) | |||
27. 移除元素(简单) | |||
66. 加一(简单) | 常规问题,纯粹考察编程基本功。 | ||
88. 合并两个有序数组 | 从后向前归并 | 常规操作,常考问题,注意这里从后向前归并。 | |
189. 旋转数组 | 记住这个旋转三次的操作。 | ||
215. 数组中的第K个最大元素(中等) | 很常见的问题,多次出现,一定要掌握。 | ||
451. 根据字符出现频率排序(中等) | 和排序相关的经典问题,做法不唯一。 | ||
912. 排序数组(中等) | 可以用于学习排序问题。 |
循环不变量
循环不变量用于证明算法的有效性,也是编码正确的理论依据。
循环不变量定义帮助分清先加还是先赋值,还有一些边界条件。定义清楚循环不变量以后,代码的编写就会很轻松。
建议把「循环不变量」作为注释写在代码里,以方便自己调试和他人阅读。
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
26. 删除排序数组中的重复项(简单) | |||
27. 移除元素(简单) | |||
75. 颜色分类(中等) | 快速排序 partition 过程(重点在设计循环不变量) | 著名的「荷兰国旗」问题。 | |
215. 数组中的第K个最大元素(简单) | 通过 partition 减治 + 优先队列 | 常考的高频问题,一定要会做,重点掌握思想。 | |
283. 移动零(简单) | 掌握循环不变式,编写代码更加容易。 |
双指针
「双指针」问题其实来自于最朴素算法的优化,一下子排序掉很多不符合题意的解,「滑动窗口」技巧也是这样的。
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
11. 盛最多水的容器(中等) | |||
15. 三数之和(中等) | |||
16. 最接近的三数之和(中等) | 双指针对撞 | ||
42. 接雨水(困难) | 暴力解法、以空间换时间、双指针、单调栈 | ||
167. 两数之和 II - 输入有序数组(简单) | 双指针对撞 + 二分法 |
滑动窗口
- 滑动窗口写法。
public class Solution {
public String minWindow(String s, String t) {
// 起始的时候,都位于 0,同方向移动
int left = 0;
int right = 0;
while (right < sLen) {
if ( 在右移的过程中检测是否满足条件 ) {
// 对状态做修改,好让程序在后面检测到满足条件
}
// 右边界右移 1 格
right++;
while ( 满足条件 ) {
// 走到这里是满足条件的,左边界逐渐逐渐左移,可以取最小值
if ( 在左移的过程中检测是否不满足条件 ) {
// 对状态做修改,好让程序在后面检测到不满足条件
}
// 左边界左移 1 格
left++;
}
// 走到这里是不满足条件的,右边界逐渐右移,可以取最大值
}
return 需要的结果变量;
}
}
练习题:
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
3. 无重复字符的最长子串(中等) | 非常经典的问题。 | ||
76. 最小覆盖子串(困难) | 非常经典的问题。 | ||
209. 长度最小的子数组(中等) | 非常经典的问题。 | ||
239. 滑动窗口最大值(中等) | |||
424. 替换后的最长重复字符(中等) | |||
567. 字符串的排列(中等) | |||
643. 子数组最大平均数 I(简单) | |||
978. 最长湍流子数组(中等) | |||
992. K 个不同整数的子数组(困难) |
链表
题目序号 | 题解 | 知识点 |
---|---|---|
61. 旋转链表 | 穿针引线 | 穿针引线 |
下面的两题考察了「双向链表」的应用。
题目 | 难度 | 题解 |
---|---|---|
460. LFU缓存 | 困难 | 哈希表 + 双向链表(Java) |
146. LRU缓存机制 | 中等 | 哈希表 + 双向链表(Java) |
二分查找
知识点讲解:用“排除法”(减治思想)写二分查找问题、与其它二分查找模板的比较、哔哩哔哩
栈
单调栈
序号 | 题目 | 题解 |
---|---|---|
1 | 739. 每日温度(中等) | 【程序员的自我修养】739. Daily Temperatures(我看这篇题解学会的)、暴力解法 + 单调栈 |
2 | 496. 下一个更大元素 I(简单) | 暴力解法、单调栈 |
3 | 503. 下一个更大元素 II(中等) | (我暂时没有写) |
4 | 901. 股票价格跨度(中等) | LeetCode 第 901 题:股票价格跨度(单调栈) |
5 | 84. 柱状图中最大的矩形(困难) | 暴力解法、栈(哨兵技巧) |
6 | 42. 接雨水(困难) | 暴力解法、栈(哨兵技巧) |
队列
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
621. 任务调度器(中等) | |||
622. 设计循环队列(中等) | |||
641. 设计循环双端队列(中等) | |||
1306. 跳跃游戏 III(中等) |
优先队列
注意:了解「堆」作为「优先队列」的实现是有必要的,这样才会理解 remove
、replace
这些编码的细节,使用堆的时候才会更加有效。
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
215. 数组中的第K个最大元素 | 通过 partition 减治 + 优先队列(Java、C++、Python) | 减而治之、堆 | |
295. 数据流的中位数(困难) | |||
347. 前 K 个高频元素(中等) | |||
703. 数据流中的第K大元素(简单) | |||
973. 最接近原点的 K 个点(中等) | |||
1296. 划分数组为连续数字的集合(中等) |
树
(待添加)
哈希表
题目 | 难度 | 题解 |
---|---|---|
49. 字母异位词分组 | 中等 | 自定义字符串的哈希规则,使用质数作为乘法因子(Java) |
回溯算法
题型 1:基本回溯问题,在数组上进行搜索
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
46. 全排列(中等) | 从全排列问题开始理解“回溯搜索”算法 | ||
47. 全排列 II(中等) | 回溯搜索 + 剪枝 | 理解深度优先遍历,发现剪枝条件。 | |
39. 组合总和 | 回溯算法 + 剪枝 | 画树形图。 | |
40. 组合总和 II | 回溯算法 + 剪枝 | 画树形图。 | |
78. 子集 | 回溯 + 位掩码 | 经典问题。 | |
90. 子集 II | 经典问题。 | ||
77. 组合 | 回溯算法 + 剪枝 |
题型 2:字符串上的回溯问题
重点理解:由于字符串每次都生成新字符,无须状态重置。
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
17 .电话号码的字母组合 | 回溯搜索(无显式回溯)、广度优先遍历 | 字符串的回溯问题。 | |
22. 括号生成 | 回溯算法(深度优先遍历)+ 广度优先遍历 | 字符串的回溯问题。 | |
93. 复原IP地址 | 回溯算法(画图分析剪枝条件) | 字符串的回溯问题。 | |
784. 字母大小写全排列 | 在隐式树上做深度优先遍历 | 字符串的回溯问题。 |
题型 3:二维平面上的回溯问题
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
79. 单词搜索(中等) | 在二维平面上使用回溯法 |
题型 4:一些游戏问题
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
51. N皇后 | 根据第 46 题“全排列”的“回溯算法”思路编写“N 皇后”问题 | 经典问题,掌握「空间换时间」技巧。 | |
37. 解数独(困难) | |||
36. 有效的数独(中等) | 这里用到的是哈希表。 |
题型 5:巧用剪枝
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
60. 第k个排列 | 深度优先遍历 + 剪枝、双链表模拟 | 可以基于第 46 题做,剪枝直接来到枝叶。 |
动态规划
一个「动态规划」问题的分类:https://zhuanlan.zhihu.com/p/126546914?utm_source=wechat_session&utm_medium=social&utm_oi=27134168924160。
知识点讲解:在「力扣」第 5 题题解。
第 1 部分:「动态规划」基本问题
- 递归 + 记忆化:记忆化递归(记忆化搜索),这是「自上而下」的思路;
- 掌握「自底向上」递推求解问题的方法;
- 理解「重复子问题」、「最优子结构」、「无后效性」;
- 掌握「状态定义」、「状态转移方程」
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
509. 斐波那契数(简单) | 递归做一定要加缓存。 | ||
70. 爬楼梯(简单) | CSDN | 和斐波拉契数是同一道问题。 |
第 2 部分:最优子结构
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
279. 完全平方数(中等) | |||
322. 零钱兑换(中等) | 动态规划、使用「完全背包」问题思路、图的广度优先遍历 | ||
343. 整数拆分(中等) | “贪心选择”性质的简单证明、记忆化搜索、动态规划 (Python、Java) |
第 3 部分:无后效性
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
198. 打家劫舍(简单) | 二维状态消除后效性 | ||
62. 不同路径(中等) | |||
63. 不同路径 II(中等) |
第 4 部分:经典问题(1)
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
53. 最大子序和 | 动态规划、分治法、CSDN | 1、经典动态规划问题;2、分治 | |
300. 最长上升子序列 | 动态规划 、贪心算法 + 二分 | ||
5. 最长回文子串 | Manacher 算法 + 动态规划 (Java、C++、Python) | 使用动态规划的方法得到子串的回文性质 | |
72. 编辑距离 | 动态规划(Java)、CDSN | ||
120. 三角形最小路径和(中等) | |||
10. 正则表达式匹配(困难) |
第 5 部分:经典问题(2)背包问题
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
416. 分割等和子集 | 动态规划(0-1 背包问题) | 很重要的动态规划模型,必须掌握 | |
518. 零钱兑换 II | 动态规划(套用完全背包问题模型) | ||
322. 零钱兑换(中等) | 动态规划、使用「完全背包」问题思路、图的广度优先遍历 | ||
377. 组合总和 Ⅳ | 动态规划 | ||
494. 目标和 | 0-1 背包问题 | ||
474. 一和零 | 动态规划(转换为 0-1 背包问题) |
第 6 部分:经典问题(3)股票问题
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
121. 买卖股票的最佳时机(简单) | 暴力枚举 + 动态规划 + 差分思想、CSDN | ||
122. 买卖股票的最佳时机 II(简单) | 暴力搜索 + 贪心算法 + 动态规划、CSDN | ||
123. 买卖股票的最佳时机 III(困难) | 动态规划、CSDN | 1、从后向前写可以把状态压缩到一维;2、分解成两个 121 题。 | |
188. 买卖股票的最佳时机 IV(困难) | 动态规划 | ||
309. 最佳买卖股票时机含冷冻期(中等) | 动态规划 | ||
714. 买卖股票的最佳时机含手续费(中等) | 动态规划 |
贪心算法
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
12. 整数转罗马数字(中等) | |||
452. 用最少数量的箭引爆气球(中等) | |||
455. 分发饼干(中等) | |||
122. 买卖股票的最佳时机 II(简单) |
并查集
第 1 部分:基础且常见的问题
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
547. 朋友圈(中等) | 并查集(Python 代码、Java 代码) | ||
990. 等式方程的可满足性(中等) | 使用并查集处理不相交集合问题 | ||
200. 岛屿数量(中等) | DFS + BFS + 并查集(Python 代码、Java 代码) | ||
684. 冗余连接 | |||
1319. 连通网络的操作次数(中等) | 并查集 |
第 2 部分:带权值的并查集问题
题目序号 | 题解 | 知识点 | 代码 |
---|---|---|---|
128. 最长连续序列(困难) | |||
399. 除法求值(中等) | |||
685. 冗余连接 II | |||
721. 账户合并 | |||
765. 情侣牵手(困难) | |||
952. 按公因数计算最大组件大小(困难) | 并查集(Java、Python) |
配套资源
- 发布在 LeetCode 中文版上的题解配图使用的 PPT,传送门:https://github.com/liweiwei1419/LeetCode-Solution-PPT
说明:做了 PPT 或者动画的题目,一般在 LeetCode 中文版的题解区都能看到我写的题解。
刷题过程中形成的文章(待更新)
- 目前更新在网站。