LeetCode solution (C++ and Python)
- 1. 《剑指offer》习题一刷 (19年11月10日完成)
- 2. 按Tag整理习题
- 对常用的数据结构、方法、套路进行整理
- 3. 《剑指offer》二刷 (43/66)
- 4. Leetcode Hot 100 + Top (45/156/245) (上传/完成/总数)
- 5. 对2020/12/28上传的./python/*.py刷题记录进行整理，更新到本Readme中
| Leetcode | Solution | Basic idea |
|---|---|---|
| 001 Two Sum | C++, Python | 1. Hashtable store the index |
| 002 Add Two Numbers | C++ | |
| 003 Longest Substring without Repeating Characters | C++ | HastTable + TwoPointer |
| 005 Longest Palindromic Substring | C++ | 1. 中心扩展 |
| 010 Regular Expression Matching | C++ | 1. 二维布尔型数组，dp[i][j]表示s[i:]与p[j:]匹配 |
| 019 Remove Nth Node From End of List | C++ | |
| 021 Merge Two Sorted Lists | C++ | |
| 028 Implement Strstr | C++ | 1. 基础字符串匹配，O(mn)，超时 2. KMP |
| 034 Find First and Last Position of Element in Sorted Array | C++ | 1. 两次二分，分别返回 不大于/大于 target的第一个位置。需要注意两次二分的细节差异和确定返回位置是否在数组范围内。 |
| 046 Permutations (unique number) | C++ | 1. DFS+标记 |
| 047 Permutations ii (maybe duplicate) | C++ | 1. DFS+标记+剪枝 |
| 050 Pow(x, n) | C++ | 1. 注意考虑特殊情况和溢出 |
| 053 Maximum Subarray | C++ | 1. DP |
| 054 Spiral Matrix | C++ | 1. 死循环依次缩减四个边界(up, right, bottom, left)并添加元素，边界越界退出循环 |
| 062 Unique Paths | Python | 1. DP |
| 064 Minimum Path Sum | C++ | 1. DP |
| 070 Climbing Stairs | C++ | 1. DP |
| 079 Word Search | C++ | 1. DFS+Backtracking |
| 091 Decode Ways | C++ | 1. DP |
| 101 Symmetric Tree | C++ | 1. 递归辅助函数isMirror(root, root) |
| 102 Binary Tree Level Order Traversal | C++ | 1. 配合队列做呗，加两个计数器变量，一个比较队列是否输出了这一层的所有结点，一个用于记录下一层共有多少结点 |
| 103 Binary Tree Zigzag Level Order Traversal | C++ | 1. 同102 |
| 104 Maximum Depth Of Binary Tree | C++ | 1. 递归，两行即可 |
| 105 Construct Binary Tree from Preorder and Inorder Traversal | C++ | 1. 根据前序的第一个元素中序中确定根的位置，从而得到左右子树的元素数量，于是将前序和中序分为左右子树。再对左右子树递归此过程 |
| 121 Best Time To Buy And Sell Stock | C++ | 1. DP 2. 遍历数组时维护最小价格，并判断价差是否产生更大收益 |
| 122 Best Time To Buy And Sell Stock II | C++ | 1. DP 2. 逐步更新收益 |
| 138 Copy List with Random Pointer | C++ | 1. 三步走（详见代码内步骤说明）：1) 在每个结点后新增其copy节点；2）对copy节点的random指针赋值；3）分离copy结点 |
| 139 Word Break | C++ | 1. DP, dp[i] = dp[i-ws] && s[i-ws:i] == word, (ws: word.size()) |
| 142 Linked List Cycle II | C++ | 1. 第一步，快慢指针判断有无环，若无环则直接返回； 第二步，若有环，则复位快指针至头结点，然后快慢指针等速向前，必相遇于入环节点。 |
| 152 Maximum Product Subarray | C++ | 1. DP (Update cur_max and cur_min, when meeting a negative number, exchange this two number before updating) |
| 155 Min Stack | C++ | 1. 维护两个栈，一个正常存数据，另一个存当前最小数值 |
| 169 majority element | C++ | 1. （基础）排序+中位数，复杂度O(n*logn) 2. 维护两个变量：某数的出现次数与某数，若出现次数为零，则下一个数来时更新某数，O(n) 3. 基于Partition找到中位数，时间复杂度O(n) |
| 179 Largest Number | C++, Python | [](string a, string b) {return a+b > b+a;} 另外注意一下细节问题，比如答案为00的情况，和string如何去除第一个元素 |
| 188 Best Time To Buy And Sell Stock IV | C++ | 1. DP Table/State Machine |
| 191 Number of 1 Bits | C++ | 1. n &= (n-1) 能够将最右一位1置零 |
| 198 House Robber | C++ | 1. DP |
| 206 Reverse Linked List | C++,Python | |
| 208 Implement Trie Prefix Tree | C++ | 1. 前缀树 = 26个子树+1个is_end标记 |
| 215 Kth Largest Element in an array | C++ | 1. 基本方法，排序，O(n) 2. 修改partition函数，每次以k作为输入参数pivot_ix 3. 建立最大堆，返回第k次弹出的元素 |
| 221 Maximal Square | C++ | 1. DP dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1 表示(r,c)处的最大边长 |
| 226 Invert Binary Tree | C++ | 1. 递归 2. 循环，需配合队列 |
| 237 Delete Node in a Linked List | C++ python | |
| 240 Search a 2D Matrix II | C++ | 1. 自右上向左或向下移动指针，直到找到目标或者退出循环 |
| (Primer) 255 Verify Preorder Sequence of a Binary Tree | C++ | 1. |
| 268 Missing Number | C++ | 1. 两遍XOR，剩余的就是答案； 2. 数学方法，利用求和公式减去实际和 |
| 279 Perfect Squares | C++ | 1. DP (Bottom-Up faster) |
| 287 Find the Duplicate Number | C++ | 1. 排序+逐个比较，能过，但不符合要求 2. 对数值进行二分，统计[l,m]和(m,h]中数字的数量，重复数在大于标准值(m-l+1或h-m)的那一半里 |
| 295 Find Median From Data Stream | C++ | 1. 二分法插入，通过随机访问返回，O(logn)。不推荐，随机访问快的数据结构在中间插入这个操作上耗时。 2. 维护较小半组数的最大堆和较大半组数的最小堆。总插入时间复杂度O(nlogn)，查询时间复杂度O(1) |
| 297 serialize and deserialize binary tree | C++ | 1. 利用istringstream自动根据空格分隔字符串的特点，将一颗中序为213的简单二叉搜索树编码成"2 1 # # 3 # #" |
| 300 Longest Increasing Subsequence | C++ | 1. DP O(n^2) 2. DP + Binary Searcy O(nlogn) |
| 309 Best Time To Buy And Sell Stock With Cooldown | C++ | 1. DP 2. 有限状态机（rest, hold, sold) |
| 322 Coin Change | C++ | 1. DP (Bottom-Up) |
| 337 House Robber III | C++ | 1. 树型DP，子函数返回{MaxWithCurrNode, MaxWithoutCurrNode} |
| 338 Counting_Bits | C++ | 1. 偶数的1的个数与其一半有关，奇数的1的个数与前一个数有关 |
| 340 Longest Substring With At Most K Distinct Characters | C++ | 滑动窗+哈希表（当前子串中各字符的数量）+标识符（存当前子串中有几个不同字符） |
| 343 Interger Break | C++ | 1. 穷举找规律，发现4及以下单独处理，4以上不停地分出3 |
| (Primer) 348 Design Tic Tac Toe | C++ | 空间换时间，维护每行每列的和，落子时以正负1更新，再检查即可 |
| 437 Path Sum III | C++ | 1. 队列+DFS，以每个结点为根DFS，注意：值可能为负，因此搜索时直到叶结点再返回 |
| 461 Hamming Distance | C++ | 1. 位操作，注意不要越界 |
| 543 Diameter Of Binary Tree | C++ | 递归DFS，返回{过该根节点的最大边数（即最大深度），跨该根节点的最大边数} |
| 617 Merge Two Binary Trees | C++ | 1.递归很简单 |
| 647 Palindromic Substrings | C++ | 1. 结合中心展开思想，分别以单中心和双中心展开即可 |
这里按照剑指offer的顺序整理了部分Leetcode的题目，方便直接在Leetcode上刷题。同时，也给出了每题能AC的解法，以C++为主。
Most of leetcode links are based on @yanring's REPO.
| 剑指offer | Leetcode | Solution |
|---|---|---|
| 03 数组中重复的数字 | 官方题解 以原数组做哈希表 | |
| 03_02 不修改数组找出重复的数字 | 287 Find the Duplicate Number | C++ |
| 04 二维数组中的查找 | 240 Search a 2D Matrix II | C++ |
| 05 替换空格 | C++ | |
| 06 从尾到头打印链表 | 1. 利用栈实现（略） 2. 利用递归实现（略） |
|
| 07 重建二叉树 | 105 Construct Binary Tree from Preorder and Inorder Traversal | C++ |
| 08 二叉树的下一个节点 | 510 Inorder Successor in BST II | C++ |
| 09 用两个栈实现队列 | 232 Implement Queue using Stacks | C++ |
| 09_02 用两个队列实现栈 | 225 Implement Stack using Queue | C++ 两个栈实现队列，一个队列实现栈!!! |
| 10 斐波那契数列 | 509 Fibonacci Number | C++ |
| 10_02 青蛙跳台阶 | 70 Climbing Stairs | C++ |
| 11 旋转数组中的最小数字 | 153 Find Minimum in Rotated Sorted Array | C++ 核心是比较nums[m]与nums[r] |
| 12 矩阵中的路径 | 79 Word Search | C++ |
| 13 机器人的运动范围 | 官方题解 亦可参考1219 黄金矿工，也是二维矩阵dfs搜索的问题，而且更难一些 |
|
| （类似）1254 Number Of Closed Islands | C++ 二维矩阵+DFS | |
| 14 剪绳子 | 343 Interger Break | C++ |
| 15 二进制中1的个数 | 191 Number of 1 Bits | C++ |
| (Advanced) 338 Counting_Bits | C++ | |
| 16 数值的整数次方 | 50 Pow(x, n) | C++, Python |
| 17 打印从1到最大的n位数 | ||
| 18_01 在O(1)的时间内删除链表的节点 | 237 Delete Node in a Linked List | C++ python |
| 18_02 删除链表中重复的节点 | 83 Remove Duplicates from Sorted List | C++ |
| 19 正则表达式匹配 | 10 Regular Expression Matching | C++,Python, adapted from offical solution |
| 20 表示数值的字符串 | 65 Valid Number | C++ |
| 21 调整数组顺序使奇数位于偶数前面 | 905 Sort Array By Parity | C++ |
| 22 链表中倒数第k个节点 | 19 Remove Nth Node From End of List | C++ |
| 23 链表中环的入口节点 | 142 Linked List Cycle II | C++ |
| 24 反转链表 | 206 Reverse Linked List | C++,Python |
| 25 合并两个排序的链表 | 21 Merge Two Sorted Lists | C++ |
| 26 树的子结构 | 572 Subtree of Another Tree | C++ |
| 27 二叉树的镜像 | 226 Invert Binary Tree | C++ |
| 28 对称的二叉树 | 101 Symmetric Tree | C++ |
| 29 顺时针打印矩阵 | 54 Spiral Matrix | C++ |
| 30 包含min函数的栈 | 155 Min Stack | C++ |
| 31 栈的压入、弹出序列 | 946 Validate Stack Sequences | C++ |
| 32_01 不分行从上往下打印二叉树 | LC102简化版 | |
| 32_02 分行从上到下打印二叉树 | 102 Binary Tree Level Order Traversal | C++ |
| 32_03 之字形遍历二叉树 | 103 Binary Tree Zigzag Level Order Traversal | C++ |
| 33 二叉搜索树的后序遍历序列 | (Primer) 255 Verify Preorder Sequence of a Binary Tree | C++ |
| 34 二叉树中和为某一值的路径 | 112 Path Sum | C++ |
| 35 复杂链表的复制 | 138 Copy List with Random Pointer | C++ |
| 36 二叉搜索树与双向链表 | (Primer) 426 Convert Binary Search Tree to Sorted Doubly Linked List | C++ 光有思路不行，这题自己写比题解的简洁性差很多 |
| 37 序列化二叉树 | 297 serialize and deserialize binary tree | C++ |
| 38 字符串的排列 | 46 Permutations (unique number) | C++ |
| 47 Permutations ii (maybe duplicate) | C++ | |
| 51 N Queens | ||
| 39 数组中出现次数超过一半的数字 | 169 majority element (appear over 1/2) | C++ |
| 229 majority element ii (appear over 1/3) | ||
| 40 最小的k个数 | 215 Kth Largest Element in an array | C++ |
| 41 数据流中的中位数 | 295 Find Median From Data Stream | C++ |
| 42 连续子数组的最大和 | 53 Maximum Subarray | C++ |
| 43 1-n整数中1出现的次数 | 233 Number of Digit One | C++ |
| 44 数字序列中某一位的数字 | 400 Nth Digit | C++ |
| 45 把数组排成最小的数 | 179 Largest Number | C++, Python |
| 46 把数字翻译成字符串 | 91 Decode Ways | C++ |
| 47 礼物最大值 | 64 Minimum Path Sum | C++ |
| 48 最长不含重复字符的子字符串 | 3 Longest Substring without Repeating Characters | C++ |
| 159 Longest Substring with At Most two Distinct Characters | 直接套用340代码，将输入参数k改为默认2即可 | |
| 340 Longest Substring With At Most K Distinct Characters | C++ | |
| 49 丑数 | 263 Ugly Number | C++ |
| 264 Ugly Number II | C++ | |
| 50_01 字符串中第一个只出现一次的字符 | 387 First Unique Character in A String | C++ |
| 50_02 字符流中第一个只出现一次的字符 | 剑指50和LC340的集合，过于简单，略（ |
|
| 51 求数组中的逆序对的总数 | 与LC493思路基本一致 | |
| (Advanced) 493 Reverse Pairs | C++ | |
| (Advanced Advanced) 315 Count of Smaller Numbers after Self | [C++] | |
| 52 两个链表的第一个公共节点 | 160 Intersection of Two Linked Lists | C++ |
| 53_01 数字在排序数组中出现的次数 | 34 Find First and Last Position of Element in Sorted Array | C++ |
| 53_02 0..N-1中确实的数字 | 268 Missing Number | C++ |
| 53_03 数组中数值和下标相等的元素 | 二分查找，官方题解 | |
| 54 二叉搜索树的第k大节点 | 230 Kth Smallest Element In A Bst | C++ |
| 55_01 二叉树的深度 | 104 Maximum Depth Of Binary Tree | C++ |
| 55_02 平衡二叉树 | 110 Balanced Binary Tree | C++ |
| 56_00 56题的前置 数组中只出现1次的那个数字 | 136 Single Number | C++ XOR for every single number |
| 56_01 数组中只出现1次的2个数字 | 260 Single Number III | C++ 1. XOR. 2. Split to two subarray. 3. XOR for two subarray, resepctively. |
| 56_02 其他数字都出现三次的数字中唯一只出现一次的数字 | 137 Single Number II | C++ SUM all and mod 3 for every single bit |
| 57_01 和为s的数字 | 1 Two Sum | C++ |
| 57_02 和为s的连续正数序列 | 829 Consecutive Numbers Sum | C++ |
| 58_01 翻转单词顺序 | 151 Reverse Words In A String | C++ |
| 58_02 左旋转字符串 | 189 Rotate Array | C++ |
| 59_01 滑动窗口的最大值 | 239 Sliding Window Maximum | C++ |
| 59_02 队列的最大值 | 没找到 | |
| 60 n个骰子的点数 | 1155 Number Of Dice Rolls With Target Sum | C++ |
| 61 扑克牌中的顺子 | 模拟法，注意细节即可 |
|
| 62 圆圈中最后剩下的数字 | 没找到 | |
| 63 股票的最大利润 | 121 Best Time To Buy And Sell Stock | C++ |
| 64 求1+2+..+n | C++ 照着敲了一下第一种方法；补充了一种利用逻辑断路来做的方法。 | |
| 65 不用加减乘除做加法 | C++ | |
| *66 构建乘积数组 | ||
| 67 把字符串转换成整数 | ||
| 68 树中两个节点的最低公共祖先 |
按Tag整理常见解题思路。存放在这里
以 VS Code + Markdown Perview Enhanced 打开会更好。
| Problem | Solution | Comment |
|---|---|---|
| 110 Balanced Binary Tree | C++ | 1. 递归；简单，但最差时间复杂度O(n^2) 2. 自底向上，比较左右子结点的深度，若相差<=1，则返回更大的那个深度，否则返回-1 |
| 203 Remove Linked List Elements | C++ | |
| (Primer) 426 Convert Binary Search Tree to Sorted Doubly Linked List | C++ | （解法太巧，面试时很难想出来）递归中序遍历+中序中访问当前节点时更新结点first一次和lastN次 |
| 829 Consecutive Numbers Sum | C++ | 1. 剑指offer和简单数学枚举法都会超时，需要在等差数列基础上进一步优化约束范围 |