这个是我在刷leetcodeTop Interview Questions 150的时候的一些笔记
灵感来自：
顺序刷：https://github.com/qiyuangong/leetcode
分类刷：https://github.com/kamyu104/LeetCode-Solutions
Pythonic：https://github.com/cy69855522/Short-LeetCode-Python-Solutions
这里主要按照两个方向刷题：
1.顺序刷
Top Interview Questions 150 : https://leetcode.com/problemset/top-interview-questions/
2.分类刷
Top Interview Questions：easy | medium | hard ：https://leetcode.com/explore/interview/card/top-interview-questions-easy/
3.其他
Python内置函数的时间复杂度：https://wiki.python.org/moin/TimeComplexity
| # | Title | Solution | Basic idea (One line) | Note | Difficulty |
|---|---|---|---|---|---|
| 1 | 两数之和 | Python | 1. Hash O(n) and O(n) space. 2. 暴力遍历法 O(n^2) and O(1). 3.sort+双指针 >O(n) and O(n) |
没排序的输入，最好使用Hashmap法 | Easy |
| 2 | 两个链表数字之和 | Python | 1.分布遍历两个链表，转成数字，相加，然后转成链表 O(n) and O(n) | Medium | |
| 3 | 最长无重复子字符串 | Python | 1.哈希表+单指针 O(n) and O(1) | Medium | |
| 4 | 两个排序列表的中位数 | Python | 1.常规解法：合并两个列表+sort() O((m+n)log(m+n)) 2.二分查找法 O(log(m+n)) |
二分查找法解析见这里 | Hard |
| 5 | 最长回文子串 | Python | 1.DP: O(n^2) and O(n^2) 2.manacher算法 O(n) and O(n) |
解析请看这里 | Medium |
| 6 | Z字形变换解析 | Python | 1.创建一个list保存，然后打印出来 O(n) and O(n) | 解析见我的博客 | Medium |
| 7 | 反向整数 | Python | 1.str法 24ms 2.除法 24ms 3.str法+abs 36ms |
Easy | |
| 8 | 字符串转整形 | Python | 1.判断法 O(n) and O(1) | Medium | |
| 9 | 回文数字 | Python | 1.str法 76ms | Easy | |
| 10 | 正则表达式匹配 | Python | 1.内置函数 64ms 2.递归 TLE 3.DP O(mn) and O(mn) |
解析见我的博客 | Hard |
| 11 | 大多数水的容器 | Python | 1.双指针 O(n^2) and O(1) | Medium | |
| 12 | 整数转罗马数 | Python | 1.字典法 | 注意：4：不是 IIII 而是 IV | Medium |
| 13 | 罗马数转整数 | Python | 1.字典法 | IV:4 -> IIII IX:9 -> VIIII 就可以方便的使用字典法 | Easy |
| 14 | 最长的共同前缀 | Python | 1.zip(*strs)+set O(n) and O(1) | 记得zip(*strs)用法 | Easy |
| 15 | 三数之和 | Python | 1.三指针 O(n^2) and O(1) | Since sorting is done in O(nlogn),which is less than O(n^2) you can ignore it. Of course only because the total would be the sum O(nlogn + n^2) |
Medium |
| 16 | 三数之和最近 | Python | 1.三指针 O(n^2) and O(1) | Medium | |
| 17 | 电话号码的字母组合 | Python | 1.数组法 O(n*4^(n+1)) and O(n) 2.回溯法 > O(n*4^(n+1)) and O(n) |
Medium | |
| 18 | 四数之和 | Python | 1.递归到2sum O(n^3) and O(n) | 本方法是Nsum递归到2sum的通用解法 解析见这里 |
Medium |
| 19 | 从列表末尾删除第N个节点 | Python | 1.数组遍历法 O(n^2) and O(n) 2.递归法 O(n) and O(1) 推荐 3.快慢指针法 O(n^2) and O(1) 标准解法 |
基础解法是法1；递归法来自这里，很巧妙；标准解法是法3 | Medium |
| 20 | 有效的括号 | Python | 1.字典法 O(n) and O(n) | Easy | |
| 21 | 合并两个排序链表 | Python | 1.迭代 O(n) and O(n) 2.递归 O(n) and O(1) |
Easy | |
| 22 | 生成括号 | Python | 1.递归 O(4^n/(n*sqrt(n))) and O(4^n/(n*sqrt(n))) | 不是特别好理解，需要回来再看 | Medium |
| 23 | 合并k个排序链表 | Python | 1.暴力法 O(nlogn) and O(n) 2.分治法：化解成两个链表合并 O(kn) and O(1) |
Hard | |
| 24 | 成对交换节点 | Python | 1.一行替换 | from pre -> a -> b -> b.next to pre -> b -> a -> b.next | Medium |
| 25 | 翻转k组链表 | Python | 1.暴力方法 O(3N) and O(n) 2.迭代法 O(n) and O(1) |
法2继承24的翻转链表的方法，需要多回头看看 | Hard |
| 26 | 从排序数组中删除重复项 | Python | 1.while del 法 | 注意：这里是内置删除数组，所以不能用for，也不能用pop | Easy |
| 27 | 删除元素 | Python | 1. while del 法 | 方法同26 | Easy |
| 28 | 实现strStr() | Python | 1. O(nk) and O(1) | Easy | |
| 29 | 整数相除 | Python | 1.快速减法 | 解释见代码 | Medium |
| 30 | 具有所有单词串联的子串 | Python | 1.循环s 480ms 2.循环len(words[0]) 44ms |
第二个方法也会遇到"ling mind ra boo fooo..." ["fooo","barr","wing","ding","wing"] 这种不是按照4个一组切分的， 所以，法1循环s的时候不能使用4个一组循环来提速，但是法2却能 |
Hard |
| 31 | 下一个排列 | Python | 1.逆序数字交换再升序 | 解析见博客 | Medium |
| 32 | 最长有效括号 | Python | 1.动态规划 O(n) and O(n) 2.stack O(n) and O(n) |
解析见这里 | Hard |
| 33 | 在旋转排序数组中搜索 | Python | 1.二分法 O(logn) | Medium | |
| 34 | 在排序数组中查找元素的第一个和最后一个位置 | Python | 1.双指针 O(n) and O(1) 2.二分法 O(logn) and O(1) |
Medium | |
| 35 | 搜索插入位置 | Python | 1.二分法 O(logn) and O(1) | Easy | |
| 36 | 有效的数独 | Python | 1.分治法 | Medium | |
| 37 | 解数独 | Python | 1.递归 容易理解版本 2.递归 优化版本 |
1.解析见这里 2.解析见这里,比较难理解，回头再看 |
Hard |
| 38 | 算和说 | Python | 1. O(nk) and O(1) | 解析见这里 | Easy |
| 39 | 组合总和 | Python | 1.dfs | Medium | |
| 40 | 组合总和II | Python | 1.dfs | 注意这个是candidates是可以重复的 | Medium |
| 41 | 第一个缺失的正整数 | Python | 1.O(n) and O(1) 2.i in nums 3.sort() O(nlogn) |
解法1解析在这里 xrange 返回生成器，比range省内存 |
Hard |
| 42 | 诱捕雨水 | Python | 1.双数组 O(n) 2.双指针 O(n) |
解析见这里 | Hard |
| 56 | 合并区间 | Python Java |
1.sort+比大小 O(nlogn+n)=O(nlogn) | sort比较费时 | Medium |
| 213 | 打家劫舍之二 | Python Java |
1.DP O(n) | 解析见这里 | Medium |
| 408 | 有效的单词缩写 | Python Java |
1.双指针 O(n) | Easy |
python笔记:
1.dic.get("a", -1) # 返回dic中“a”的value，如果没有，返回“-1”2.xrange 返回生成器，比range省内存
数组：
1 Two Sum（系列）
57 有序数组中和为s的两个数（
167 Two Sum II - Input array is sorted）
3Sum（系列） + 4sum
Contains Duplicate
3 数组中重复的数字（287. Find the Duplicate Number）
26 Remove Duplicates from Sorted Array
39 数组中出现次数超过一半的数字
53 数字在排序数组中出现的次数
旋转数组（189. Rotate Array）
Intersection of Two Arrays（系列）
228. Summary Ranges
66 构建乘积数组（cnblogs）
21 调整数组顺序使奇数位于偶数前面
61 扑克牌中的顺子
45 把数组排成最小的数
51 数组中的逆序对
Increasing Triplet Subsequence
Plus One
Move Zeroes
Valid Sudoku
Rotate Image
矩阵
4 有序矩阵中的查找（ 74. Search a 2D Matrix ）（系列）
29 顺时针打印矩阵（54. Spiral Matrix）（系列）
Kth Smallest Element in a Sorted Matrix
Set Matrix Zeroes(cnblogs)
位运算
位运算规律总结
15 二进制中1的个数（191. Number of 1 Bits）
56 数组中只出现一次的数字（136. Single Number）（系列）
特殊数与数位
204. Count Primes
263. Ugly Number（系列）
43 1~n整数中1出现的次数 (233. Number of Digit One )
44 数字序列中某一位的数字(400. Nth Digit)
字符串
50 第一个只出现一次的字符（387. First Unique Character in a String）
5 替换空格
Reverse String
Reverse Integer
58 翻转字符串（翻转单词与左旋转字符串）
67 把字符串转成整数
String to Integer (atoi)
Implement strStr()（cnblogs）
38 字符串的排列（全排列问题）
Longest Common Prefix(cnblogs)
Valid Parentheses（括号对）(cnblogs)
Valid Palindrome(回文词系列)
Longest Palindromic Substring
242. Valid Anagram (变位词系列)
48 最长不含重复字符的子字符串（3. Longest Substring Without Repeating Characters）
Count and Say
19 正则表达式匹配（hard，了解即可）
20 表示数值的字符串（了解即可）
栈和队列
9.1 用队列实现栈（225. Implement Stack using Queues）
9.2 用栈实现队列（232. Implement Queue using Stacks）
30 包含min函数的栈（155. Min Stack）
31 栈的压入、弹出序列
59 队列（滑动窗口）的最大值
链表
14 反转链表 206. Reverse Linked List（系列）
6 从尾到头打印链表
18 删除链表中的结点（237. Delete Node in a Linked List）
22 删除链表中倒数第k个结点（19. Remove Nth Node From End of List）(cnblogs)
52 两个链表的第一个公共结点（Intersection of Two Linked Lists）
23 有环链表问题-链表中环的入口结点（141. Linked List Cycle）
25 合并两个排序的链表（系列）（21. Merge Two Sorted Lists）
35 复杂链表的复制（138. Copy List with Random Pointer）
Add Two Numbers
328. Odd Even Linked List
Palindrome Linked List
树
二叉树的遍历总结（前序、中序、后序、层序、 之字形层序、垂直序）
二叉查找树的查找、插入、删除
68 树中两个节点的最低公共祖先
104. Maximum Depth of Binary Tree
110. Balanced Binary Tree
28 对称二叉树（101. Symmetric Tree）
27 二叉树的镜像
26 树的子结构（572. Subtree of Another Tree）
34 二叉树中和为某一值的路径（112. Path Sum）
124. Binary Tree Maximum Path Sum
37 序列化二叉树（297. Serialize and Deserialize Binary Tree）(cnblogs)
7 重建二叉树（系列）
Validate Binary Search Tree
36 二叉搜索树与双向链表
33 判断某序列是否为二叉搜索树的后序序列
Kth Smallest Element in a BST(cnblogs)
Convert Sorted Array to Binary Search Tree(cnblogs)
Populating Next Right Pointers in Each Node
8 二叉树中序遍历的下一个结点
查找与排序
二分查找小结
40 最小的k个数（对应Kth Largest Element in an Array）
41 数据流中的中位数（295. Find Median from Data Stream）
Median of Two Sorted Arrays
Merge Sorted Array
33 Search in Rotated Sorted Array(系列)(cnblogs)
11旋转数组的最小数字（153. Find Minimum in Rotated Sorted Array）（系列）
Search for a Range
Find Peak Element
First Bad Version
Sort Colors(cnblogs)
Top K Frequent Elements
Merge Intervals(cnblogs)
Wiggle Sort（系列）
动态规划与贪婪法
70 Climbing Stairs
14 剪绳子
剑指Offer-46：把数字翻译成字符串
42 连续子数组的最大和（53. Maximum Subarray）
Maximum Product Subarray
《算法导论》动态规划、贪婪法与分治法ppt
47：礼物的最大价值
House Robber（系列）
Unique Paths（系列）
Longest Increasing Subsequence
121. Best Time to Buy and Sell Stock（系列）
Jump Game（系列）
Coin Change（系列）
Burst Balloons
Word Break（系列）
背包问题总结
回溯法和暴力枚举法
排列与组合
12 矩阵中的字符串查找（79. Word Search 系列）
13 机器人的运动范围
Generate Parentheses
Letter Combinations of a Phone Number
Number of Islands
Subsets（系列）
分治法
16 数值的整数次方（50. Pow(x, n)）
42 连续子数组的最大和（53. Maximum Subarray）
Sqrt(x)
发散思维题
17 打印从1到最大的n位数
43 n个骰子的点数
62 圆圈中最后剩下的数字（约瑟夫环问题）
64 求1+2+…+n
65 不用加减乘除做加法
231. Power of Two（系列）
Fizz Buzz(cnblogs)
Roman to Integer
Shuffle an Array