✏️ Leetcode Solutions with Python

• 身份：某大学硕士研究生在读；

• 坐标：上海；

• 目的：为了一年以后的竞争，现开始系统的刷题；

• 时间：2020.1.17～

以前使用Java刷过近200题，但时间太久都遗忘了，故令开一个LeetCode号，重新开始，使用现在自己最常用的Python语言。记录每道题的题解、反思等。

阶段性总结

1～100题：

• 未作出的Medium：15、31、95、96；【双指针】【数组】【线索二叉树】
• 重新回顾：28、40、53、55、58、60、62、79、81、89、94、98；
• Hard题等刷到200题之后再回过来做；

Debug：相关类或函数

因为使用Sublime作为编辑器，故没有调试功能，自己写了一些类或函数方便调用进行调试；

单链表创建

class ListNode:
	def __init__(self, x):
		self.val = x
		self.next = None

创建单链表

from singly_linked_list import ListNode

# 创建单链表
def create_list(nums):
	L = ListNode(0)
	l = L
	for i in nums:
		l.next = ListNode(i)
		l = l.next
	return L.next

# 输出单链表的值
def print_list_val(l):
	while l != None:
		print(l.val, end='')
		l = l.next
		if l != None:
			print('->', end='') 
	print()

单链表转置

from singly_linked_list import ListNode

# 单链表的转置
def reverse(l: ListNode) -> ListNode:
	l1 = l
	former = None
	while l1 != None:
		later = l1.next
		l2 = l1
		l2.next = former
		former = l2
		l1 = later
	return former

树的创建

class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

如何引入

例：

import sys
sys.path.append('../functions/')
from singly_linked_list import ListNode

Python包：特殊的函数或用法

1. ord()，它以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值；chr()：ASCII转字符

2. str = str.rstrip()，去除字符串右端的空格；

3. 遍历字典的四种方式：

   • 遍历键：for key in hashmap:
   • 遍历值：for value in hashmap.values():
   • 遍历键、值：for key, value in hashmap:
   • 遍历项：for item in hashmap.items():

4. 重复字符串只需乘以数字即可："a" * 2

5. 关于2 ** 31，可以用位运算符，1<<31

6. 排序，sorted(nums, key= lambda x: x[1])，按照每一个迭代对象的第2个值进行排序

7. 创建二维数组：[[0] * n for i in range(n)]

8. 向后遍历：for i in range(len(nums)-1,-1,-1)

9. 字符串判断：

   • 是否为数字："".isdigit() # 无法判断负数;
   • 是否为字母："".isalpha();
   • 是否为数字字母："".isalnum();

10. 申明全局变量：nonlocal

11. 有序字典

    from collections import OrderedDict()
    
    dict = OrderedDict()
    # 插入
    dict.put(key, value)
    # 获取值
    dict.get(key)
    # 移动到最后一个
    dict.move_to_end(key)
    # 删除某个键对应的值
    dict.pop(key)
    # 删除最后一个
    dict.popitem()
    # 删除第一个
    dict.popitem(last=False)

12. -1 // 6 = 1； int(-1 / 6) = 0

列表

#	Title	Type	Source Code	Difficulty	Time	Solved
1	两数之和	哈希表	Python	Easy	2020/1/17	Y
2	两数相加	单链表、数学	Python	Medium	2020/1/17	Y
3	无重复字符的最长子串	滑动窗口	Python	Medium	2020/1/17	Y
4	寻找两个有序数组的中位数	二分查找、分治算法	Python	Hard	2019/11/4	N
5	最长回文子串	字符串	Python	Medium	2020/1/22	Y
6	Z字形变换	字符串	Python	Medium	2020/1/21	Y
7	整数反转	数学	Python	Easy	2020/1/17	Y
8	字符串转整数(atoi)	数学、字符串、正则表达式	Python	Medium	2020/1/22	Y
9	回文数	数学	Python	Easy	2020/1/17	Y
11	盛最多水的容器	双指针	Python	Medium	2020/1/23	Y
12	整数转罗马数字	字符串、哈希表	Python	Medium	2020/1/21	Y
13	罗马数字转整数	哈希表	Python	Easy	2020/1/17	Y
14	最长公共前缀	分治算法	Python	Easy	2020/1/18	Y
15	三数之和	数组、双指针	Python	Medium	2020/1/24	N
16	最接近的三数之和	数组、双指针	Python	Medium	2020/1/25	Y
17	电话号码的字母组合	字符串、回溯算法	Python	Medium	2020/1/23	Y
18	四数之和	数组、双指针	Python	Medium	2020/1/25	Y
19	删除链表的倒数第N个节点	单链表	Python	Medium	2020/1/23	Y
20	有效的括号	栈、哈希表	Python	Easy	2020/1/18	Y
21	合并两个有序链表	单链表、递归	Python	Easy	2020/1/18	Y
22	括号生成	字符串、回溯算法	Python	Medium	2020/1/25	Y
24	两两交换链表中的节点	单链表	Python	Medium	2020/1/25	Y
26	删除排序数组中的重复项	双指针	Python	Easy	2020/1/18	Y
27	移除元素	双指针	Python	Easy	2020/1/19	Y
28	实现strStr()	KMP	Python	Easy	2020/1/19	Y
29	两数相除	数学、移位运算	Python	Medium	2020/1/26	Y
31	下一个排列	数组	Python	Medium	2020/1/29	N
33	搜索旋转排序数组	二分查找	Python	Medium	2020/1/26	Y
34	在排序数组中查找元素的第一个和最后一个位置	二分查找	Python	Medium	2020/1/26	Y
35	搜索插入位置	二分查找	Python	Easy	2020/1/19	Y
36	有效的数独	哈希表	Python	Medium	2020/1/29	Y
38	外观数列	递归	Python	Easy	2020/1/19	Y
39	组合总和	回溯算法	Python	Medium	2020/1/28	Y
40	组合总和II	回溯算法、剪枝	Python	Medium	2020/1/28	Y
43	字符串相乘	字符串	Python	Medium	2020/1/27	Y
46	全排列	DFS	Python	Medium	2020/1/29	Y
47	全排列II	回溯算法、剪枝	Python	Medium	2020/1/29	Y
48	旋转图像	数组	Python	Medium	2020/1/28	Y
49	字母异位词分组	哈希表	Python	Medium	2020/1/27	Y
50	Pow(x, n)	数学	Python	Medium	2020/1/28	Y
53	最大子序和	分治算法、动态规划	Python	Easy	2020/1/20	Y
54	螺旋矩阵	数组	Python	Medium	2020/1/30	Y
55	跳跃游戏	贪心算法	Python	Medium	2020/1/30	Y
56	合并区间	数组、排序	Python	Medium	2020/1/30	Y
58	最后一个单词的长度	字符串	Python	Easy	2020/1/20	Y
59	螺旋矩阵II	数组	Python	Medium	2020/1/31	Y
60	第k个排列	数学	Python	Medium	2020/1/31	Y
61	旋转链表	单链表	Python	Medium	2020/1/31	Y
62	不同路径	动态规划	Python	Medium	2020/2/1	Y
63	不同路径II	动态规划	Python	Medium	2020/2/1	Y
64	最小路径和	动态规划	Python	Medium	2020/2/1	Y
66	加一	逻辑	Python	Easy	2020/1/20	Y
67	二进制求和	双指针	Python	Easy	2020/1/20	Y
69	x的平方根	二分查找、牛顿法	Python	Easy	2020/1/21	Y
70	爬楼梯	斐波那契、动态规划	Python	Easy	2020/1/20	Y
71	简化路径	字符串、栈	Python	Medium	2020/2/9	Y
73	矩阵置零	数组	Python	Medium	2020/2/2	Y
74	搜索二维矩阵	数组、二分查找	Python	Medium	2020/2/2	Y
75	搜索二维矩阵	数组	Python	Medium	2020/2/2	Y
77	组合	回溯算法	Python	Medium	2020/2/3	Y
78	子集	回溯算法	Python	Medium	2020/2/3	Y
79	单词搜索	回溯算法	Python	Medium	2020/2/3	Y
80	删除排序数组中的重复项II	数组	Python	Medium	2020/2/4	Y
81	搜索旋转排序数组II	二分查找	Python	Medium	2020/2/4	Y
82	删除排序链表中的重复元素II	单链表	Python	Medium	2020/2/4	Y
83	删除排序链表中的重复元素	单链表	Python	Easy	2020/1/20	Y
86	分隔链表	单链表	Python	Medium	2020/2/5	Y
88	合并两个有序数组	双指针	Python	Easy	2020/1/20	Y
89	格雷编码	回溯算法	Python	Medium	2020/2/5	Y
90	子集II	回溯算法	Python	Medium	2020/2/5	Y
91	解码方法	字符串、动态规划	Python	Medium	2020/2/6	Y
92	反转链表II	单链表	Python	Medium	2020/2/6	Y
93	复原IP地址	回溯算法	Python	Medium	2020/2/6	Y
94	二叉树的中序遍历	二叉树	Python	Medium	2020/2/7	Y
95	不同的线索二叉树II	二叉搜索树	Python	Medium	2020/2/9	N
96	不同的线索二叉树	动态规划、二叉搜索树	Python	Medium	2020/2/7	N
98	验证二叉线索树	DFS、二叉搜索树	Python	Medium	2020/2/8	Y
100	相同的树	二叉树	Python	Easy	2020/1/20	Y
101	对称二叉树	二叉树、DFS、栈	Python	Easy	2020/2/10	Y
102	二叉树的层次遍历	二叉树、BFS	Python	Medium	2020/2/18	Y
103	二叉树的锯齿形层次遍历	二叉树、BFS	Python	Medium	2020/2/18	Y
104	二叉树的最大深度	二叉树、DFS	Python	Easy	2020/2/10	Y
105	从前序与中序遍历序列构造二叉树	二叉树、DFS	Python	Medium	2020/2/19	Y
106	从中序与后序遍历序列构造二叉树	二叉树、DFS	Python	Medium	2020/2/19	Y
107	二叉树的层次遍历II	二叉树、BFS	Python	Easy	2020/2/10	Y
108	将有序数组转化为二叉搜索树	二叉搜索树、DFS	Python	Easy	2020/2/11	Y
109	有序链表转换二叉搜索树	二叉树、DFS、快慢指针	Python	Medium	2020/2/19	Y
110	平衡二叉树	平衡二叉树、DFS	Python	Easy	2020/2/11	Y
111	二叉树的最小深度	二叉树、BFS、DFS	Python	Easy	2020/2/10	Y
112	路径总和	二叉树、DFS	Python	Easy	2020/2/12	Y
113	路径总和II	二叉树、DFS	Python	Medium	2020/2/20	Y
114	二叉树展开为链表	二叉树、非递归	Python	Medium	2020/2/20	Y
116	填充每个节点的下一个右侧节点指针	二叉树、BFS	Python	Medium	2020/2/20	Y
117	填充每个节点的下一个右侧节点指针II	二叉树、BFS	Python	Medium	2020/2/20	Y
118	杨辉三角	数组	Python	Easy	2020/2/12	Y
119	杨辉三角II	数组	Python	Easy	2020/2/12	Y
120	三角形最小路径和	动态规划、数组	Python	Medium	2020/2/21	Y
121	买卖股票的最佳时机	动态规划	Python	Easy	2020/2/13	Y
122	买卖股票的最佳时机II	动态规划	Python	Easy	2020/2/13	Y
125	验证回文串	字符串	Python	Easy	2020/2/13	Y
127	单词接龙	图、BFS	Python	Medium	2020/2/29	Y
129	求根到叶子节点数字之和	二叉树、DFS	Python	Medium	2020/2/21	Y
130	被围绕的区域	图、DFS	Python	Medium	2020/2/22	Y
131	分割回文串	回溯算法	Python	Medium	2020/2/23	Y
133	克隆图	图、DFS	Python	Medium	2020/2/23	N
134	加油站	贪心算法	Python	Medium	2020/2/27	Y
136	只出现一次的数字	哈希表、位操作	Python	Easy	2020/2/13	Y
137	只出现一次的数字II	位运算	Python	Medium	2020/2/24	N
138	复制带随机指针的链表	链表	Python	Medium	2020/2/24	Y
139	单词拆分	动态规划	Python	Medium	2020/2/28	Y
141	环形链表	单链表	Python	Easy	2020/2/4	Y
142	环形链表II	单链表、Floyd算法	Python	Medium	2020/2/23	Y
143	重排链表	单链表、递归	Python	Medium	2020/2/24	Y
144	二叉树的前序遍历	二叉树、非递归	Python	Medium	2020/2/21	Y
146	LRU的缓存机制	设计	Python	Medium	2020/2/25	Y
147	对链表进行插入排序	单链表	Python	Medium	2020/2/26	Y
148	排序链表	单链表、归并	Python	Medium	2020/2/27	Y
150	逆波兰表达式求值	数学	Python	Medium	2020/2/25	Y
151	翻转字符串	字符串	Python	Medium	2020/3/1	Y
152	乘积最大序列	动态规划	Python	Medium	2020/3/2	Y
153	寻找排序数组中的最小值	二分查找	Python	Medium	2020/3/4	Y
155	最小栈	栈、设计	Python	Easy	2020/2/14	Y
160	相交链表	单链表、哈希表、双指针	Python	Easy	2020/2/14	Y
162	寻找峰值	二分查找	Python	Medium	2020/3/5	Y
165	比较版本号	字符串	Python	Medium	2020/3/7	Y
167	两数之和 II - 输入有序数组	数组、哈希表、双指针	Python	Easy	2020/2/14	Y
168	Excel表列名称	数学	Python	Easy	2020/2/15	Y
169	多数元素	分治、投票	Python	Easy	2020/2/15	Y
171	Excel表列序号	数学	Python	Easy	2020/2/16	Y
172	阶乘后的零	数学	Python	Easy	2020/2/17	Y
189	旋转数组	数组	Python	Easy	2020/2/17	Y
190	颠倒二进制位	位运算	Python	Easy	2020/2/17	Y
191	位1的个数	位运算	Python	Easy	2020/2/17	Y
198	打家劫舍	动态规划	Python	Easy	2020/2/17	Y
199	二叉树的右视图	二叉树、BFS	Python	Medium	2020/3/12	Y