# leetcode

**Repository Path**: pedro240034/leetcode

## Basic Information

- **Project Name**: leetcode
- **Description**: python 数据结构与算法 leetcode 算法题与书籍 刷算法全靠套路！Crack LeetCode, not only how, but also why.
- **Primary Language**: Python
- **License**: MPL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2022-03-06
- **Last Updated**: 2022-03-06

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## Leetcode -- 一步一步成为 offer 收割机 (算法全都是套路，牢记算法模板，offer拿到手软)

> 作者： Jam
> + 个人简介： 化工行业转行计算机全靠自学，目前在国内大厂工作，在力扣上传了数百道问题的解法，本仓库主要是为了总结算法套路与帮助和我一样转行，以及想深入学习算法有大厂梦的兄弟和姐妹们。

**算法题分类思维导图：**
![image](https://user-images.githubusercontent.com/33345911/155837010-d97e1df7-0261-4099-8039-6b31cf567b70.png)

本仓库的 leetcode 文件夹下都是基于 LeetCode 的题目，涵盖了所有题型和技巧，而且一定要做到**举一反三，通俗易懂**，[算法体系化学习书籍和面试题](https://github.com/ls1248659692/leetcode/tree/master/book)有相关算法系统学习书籍和题目推荐。

## Leetcode [算法题刷题科学刷题总结](https://zhuanlan.zhihu.com/p/96883783)
1. 职业训练：拆分知识点、刻意练习、总结
2. 五步刷题法（五毒神掌）
3. 做算法的最大误区：只刷一遍
4. 新手建议先从简单题开始刷起，从30min/题 提升到 5min/题 就可以开始挑战刷中等难度题
5. 大厂面试只要你能不看答案刷中等难度题，基本国内大厂随便进



### 面试技巧：
1. 确定和面试官沟通的是否一致，问清楚，题目要看清楚
2. 想所有可能的解法，找时间最优解法
3. coding（多写）
4. test cases（测试样例）

### 五毒神掌内功心法
#### 第一遍：
1. 读题：5分钟读题+思考
2. 直接看解法（理解多个解法）
3. 背诵默写
#### 第二遍：
1. 马上自己写，提交lc（leetcode）
2. 多种解法比较，体会->优化（执行时间和ac）
#### 第三遍：（24小时之后）
1. 过了一天再重复做题
2. 不同熟悉的解法程度->专项训练
#### 第四遍：（1周后）
1. 过了一周：再反复练习相同题目
2. 专项训练
#### 第五遍：（面试前一周）
1. 面试前一周恢复训练
2. 面试前一周复习算法模板与相应分类出现的题目


## 算法题汇总

20 个最常用的、最基础数据结构与算法，都已经总结在 [算法题模板分类](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates)

10 个必考数据结构模板：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树。

10 个必会算法模板：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

### 不同算法类型
>1. [滑动窗口](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/sliding_window)
>2. [双指针](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/two_pointers)
>3. [快慢指针链表](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/linked_list)
>4. [集合查找](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/union_find)
>5. [二叉树](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/trie_tree)
>6. [字符串](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/string)
>7. [DFS](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/dfs)
>8. [BFS](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/bfs)
>9. [回溯法](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/backtracking)
>10. [双堆模式](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/heap)
>11. [二分法与二分法变种](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/binary_search)
>12. [前K大的数模式HEAP](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/heap)
>13. [分治思想](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/divide_conquer)
>14. [DP 动态规划](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/dynamic_programming)
>15. [排序算法](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/sort)
>16. [链表](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/linked_list)
>17. [二叉搜索树的构建](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/binary_tree)
>18. [位运算](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/bit_manipulation)
>19. [dict](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/dict)
>20. [stack](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/stack)/[queue](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/queue)
>21. [math](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/match)
>22. [array](https://github.com/ls1248659692/leetcode/blob/master/algorithm_templates/array/array_examples.py)
>23. [图](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/graph)
>24. [贪婪算法](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/greedy)
>25. [matrix](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/matrix)
>26. [一般算法题模板](https://github.com/ls1248659692/leetcode/tree/master/algorithm_templates/common)

## 题型汇总

### `1. 滑动窗口`
>53. 大小为 K 的子数组的最大和
>121. Best Time to Buy and Sell Stock
>3. Longest Substring Without Repeating Characters
>239. Sliding Window Maximum
>* 剑指 Offer 57 - II. 和为s的连续正数序列
```python3
# Sliding windows code template is most used in substring match or maximum/minimum problems.
# It uses two-pointer as boundary of sliding window to traverse, and use a counter(dict) maintain current state,
# and a count as condition checker, update it when trigger some key changes.
#
# Time:  O(n)
# Space: O(k) k = len(set(p))
from collections import Counter

# s - target sequence, p - pattern or restrict sequence
def sliding_window_template_with_examples(s, p):
    # initialize the hash map here
    # counter is used to record current state, could use defaultdict in some situation, for example, no p restrict
    counter = Counter(p)

    # two pointers, boundary of sliding window
    start, end = 0, 0
    # condition checker, update it when trigger some key changes, init value depend on your situation
    count = 0
    # result, return int(such as max or min) or list(such as all index)
    res = 0

    # loop the source string from begin to end
    while end < len(s):
        counter[s[end]] += 1
        # update count based on some condition
        if counter[s[end]] > 1:
            count += 1
        end += 1

        # count condition here
        while count > 0:
            '''
            update res here if finding minimum
            '''

            # increase start to make it invalid or valid again
            counter[s[start]] -= 1
            # update count based on some condition
            if counter[s[start]] > 0:
                count -= 1
            start += 1

        '''
        update res here if finding maximum
        '''
        res = max(res, end - start)

    return res

# refer to https://leetcode.com/problems/minimum-window-substring/discuss/26808/here-is-a-10-line-template-that-can-solve-most-substring-problems
```

### `2. 双指针`
>双指针通常用在排好序的数组或是链表中寻找对子, 或者是merge 或者是排序，或者去除element，反正一般都是头尾各一个指针，然后根据条件移动。

>1. Two Sum（# 也可以用map的方式做）
>167. Two Sum II - Input array is sorted
>977. Squares of a Sorted Array (很像merge sort里的merge）
>283. Move Zeroes
>27. Remove Element
>26. Remove Duplicates from Sorted Array
>16. 3Sum Closest
>18. 4Sum
>86. Partition List
>11. Container With Most Water
>42. Trapping Rain Water
>75. Sort Colors
>* 剑指 Offer 04. 二维数组中的查找
>* 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
```python3
# two pointers scenario, famous applications such as binary search, quick sort and sliding window.

'''
Classification:
1. old & new state: old, new = new, cur_result
2. slow & fast runner: slow-> fast->->
3. left & right boundary or index: left-> <-right
4. p1 & p2 from two sequences: p1-> p2->
5. start & end sliding window boundary: start-> end->
'''


# old & new state: old, new = new, cur_result
def old_new_state(self, seq):
    # initialize state
    old, new = default_val1, default_val2
    for element in seq:
        '''
        process current element with old state
        '''
        old, new = new, self.process_logic(element, old)


# slow & fast runner: slow-> fast->->
def slow_fast_runner(self, seq):
    # initialize slow runner
    slow = seq[0]   # for index: slow = 0
    # fast-runner grows each iteration generally
    for fast in range(seq):     # for index: range(len(seq))
        '''
        slow-runner grows with some restrictions
        '''
        if self.slow_condition(slow):
            slow = slow.next    # for index: slow += 1
        '''
        process logic before or after pointers movement
        '''
        self.process_logic(slow, fast)


# left & right boundary or index: left-> <-right
def left_right_boundary(self, seq):
    left, right = 0, len(seq) - 1
    while left < right:
        '''
        left index moves when satisfy the condition
        '''
        if self.left_condition(left):
            left += 1

        '''
        right index move when satisfy the condition
        '''
        if self.right_condition(right):
            right -= 1

        '''
        process logic before or after pointers movement
        '''
        self.process_logic(left, right)


# p1 & p2 from two sequences: p1-> p2->
def pointers_from_two_seq(self, seq1, seq2):
    # init pointers
    p1, p2 = 0, 0       # or seq1[0], seq2[0]

    # or other condition
    while p1 < len(seq1) and p2 < len(seq2):
        '''
        p1 index moves when satisfy the condition
        '''
        if self.p1_condition(p1):
            p1 += 1         # or p1 = next(seq1)

        '''
        p2 index move when satisfy the condition
        '''
        if self.p2_condition(p2):
            p2 += 1         # or p2 = next(seq2)

        '''
        process logic before or after pointers movement
        '''
        self.process_logic(p1, p2)


# start & end of sliding window: |start-> ... end->|
# more details in sliding windows templates, here is just about two-pointers part
def start_end_sliding_window(self, seq):
    start, end = 0, 0

    while end < len(seq):
        # end grows in the outer loop
        end += 1

        # start grows with some restrict
        while self.start_condition(start):
            '''
            process logic before pointers movement
            '''
            self.process_logic1(start, end)

            # start grows in the inner loop
            start += 1

        '''
        or process logic after pointers movement
        '''
        self.process_logic2(start, end)
```

### `3. 快慢指针/ 链表题目`
>快慢指针是处理linked list常用的套路，通常是用来判断成环以及环的入口，或者是寻找 list中第k个元素。

>141. Linked List Cycle
>142. Linked List Cycle II
>234. Palindrome Linked List
>61. Rotate List
>* 剑指 Offer 18. 删除链表的节点
>JZ56 删除链表中重复的结点
>* 剑指 Offer 22. 链表中倒数第k个节点
>* 剑指 Offer 52. 两个链表的第一个公共节点

### `4. 原地链表翻转`
>234. Palindrome Linked List
>206. Reverse Linked List
>25. Reverse Nodes in k-Group
>92. Reverse Linked List II

### `5. 区间合并`
>区间合并的问题，通常是重新把区间按照start和end排序，重新组合区间。

>56. Merge Intervals
>986. Interval List Intersections
>57. Insert Interval

### `6. 无序限定范围的数组元素查找O(N）`
>要求 inplace， 通常是采用正负反转的做法

>41. First Missing Positive
>448. Find All Numbers Disappeared in an Array
>剑指 Offer 03. 数组中重复的数字

### `7. BFS`
>BFS 通常采用queue 来实现

>102. Binary Tree Level Order Traversal
>103. Binary Tree Zigzag Level Order Traversal
>297. Serialize and Deserialize Binary Tree
>127. Word Ladder I
>207. Course Schedule【拓扑排序】

### `8. 树的DFS`
>通常采用递归 111. Minimum Depth of Binary Tree

>112. Path Sum
>113. Path Sum II（和剑指 Offer 34. 二叉树中和为某一值的路径一样）
>437. Path Sum III
>100. Same Tree
>101. Symmetric Tree
>104. Maximum Depth of Binary Tree
>110. Balanced Binary Tree
>* 剑指 Offer 26. 树的子结构
>* 剑指 Offer 33. 二叉搜索树的后序遍历序列
>* 剑指 Offer 54. 二叉搜索树的第k大节点(inorder)

### `9. DFS/递归/回溯法`
>对于排列和组合的题目，需要主要判断是否会有重复数字，如有重复，需要先进行sort，而且需要进行剪枝。

>78. Subsets
>90. Subsets II
>46. Permutations
>47. Permutations II
>39. Combination Sum
>322. Coin Change
>518. Coin Change 2
>40. Combination Sum II
>131. Palindrome Partitioning !
>17. Letter Combinations of a Phone Number (differ from 91. Decode Ways)
>79. Word Search(same as 剑指 Offer 12. 矩阵中的路径)
>* 剑指 Offer 13. 机器人的运动范围
>10. 双堆模式
>295 Find-Median-from-Data-Stream
>480. Sliding Window Median
>155. Min Stack
>* 剑指 Offer 09. 用两个栈实现队列

### `11. 二分法与二分法变种`
>当你需要解决的问题的输入是排好序的数组，链表，或是排好序的矩阵，要求咱们寻找某些特定元素。这个时候的不二选择就是二分搜索。

>35. Search Insert Position
>34. Find First and Last Position of Element in Sorted Array
>33. Search in Rotated Sorted Array
>153. Find Minimum in Rotated Sorted Array
>154. Find Minimum in Rotated Sorted Array II(same as [剑指 Offer 11. 旋转数组的最小数字])
>162. Find Peak Element
>540. Single Element in a Sorted Array
>* 剑指 Offer 16. 数值的整数次方(2分法)

### `12. 前K大的数模式HEAP`
>采用priority queue 或者 说在python 中的heapq 求top k 采用最小堆（默认） 采用最大堆的时候可以采用push 负的value

>215. Kth Largest Element in an Array
>347. Top K Frequent Elements
>373. Find K Pairs with Smallest Sums

### `13. K路归并`
>K路归并能帮咱们解决那些涉及到多组排好序的数组的问题。

>23. Merge k Sorted Lists
>21. Merge Two Sorted Lists

### `14. DP 动态规划`
>300. Longest Increasing Subsequence
>1143. Longest Common Subsequence
>72. Edit Distance
>44. Wildcard Matching
>10. Regular Expression Matching
>120. Triangle
>53. Maximum Subarray
>152. Maximum Product Subarray
>887. Super Egg Dropref
>198. House Robber
>213. House Robber II (两个dp）
>121. Best Time to Buy and Sell Stock
>122. Best Time to Buy and Sell Stock II
>188. Best Time to Buy and Sell Stock IV
>123. Best Time to Buy and Sell Stock III ref
>714. Best Time to Buy and Sell Stock with Transaction Fee
>309. Best Time to Buy and Sell Stock with Cooldown
>516. Longest Palindromic Subsequence !
>5. Longest Palindromic Substring
>416. Partition Equal Subset Sum
>322. Coin Change
>518. Coin Change 2
>91. Decode Ways
>139. Word Break
>* 剑指 Offer 10- I. 斐波那契数列
>* 剑指 Offer 10- II. 青蛙跳台阶问题
>矩形覆盖
>变态跳台阶
>* 剑指 Offer 14- I. 剪绳子
>* 剑指 Offer 46. 把数字翻译成字符串
>* 剑指 Offer 47. 礼物的最大价值
>* 剑指 Offer 49. 丑数
>* 剑指 Offer 60. n个骰子的点数

### `15. 排序算法`

>* Selection Sort
>* Heapsort
>* Mergesort
>* Insertion Sort
>* Shell's Sort
>* Quicksort
>* Bubblesort
>* Linear Sorting

### `16. 树和链表结合`
>36. 二叉搜索树与双向链表
>109. Convert Sorted List to Binary Search Tree
>114. Flatten Binary Tree to Linked List

### `17. 树的重新构建`
>105. Construct Binary Tree from Preorder and Inorder Traversal
>106. Construct Binary Tree from Inorder and Postorder Traversal
>606. Construct String from Binary Tree
>1008. Construct Binary Search Tree from Preorder Traversal
>889. Construct Binary Tree from Preorder and Postorder Traversal

### `18. 位运算`
>136. Single Number
>540. Single Element in a Sorted Array
>190. Reverse Bits
>* 剑指 Offer 15. 二进制中1的个数
>* 剑指 Offer 56 - I. 数组中数字出现的次数
>* 剑指 Offer 56 - II. 数组中数字出现的次数 II

### `19. 字符串`
>一般都有很多corner cases 需要考虑
 
>8. String to Integer (atoi)

>* 剑指 Offer 20. 表示数值的字符串
>* 剑指 Offer 58 - I. 翻转单词顺序(2次翻转）
>* 剑指 Offer 58 - II. 左旋转字符串

### `20. stack`

>* 剑指 Offer 31. 栈的压入、弹出序列

### `21. math`
> 172. Factorial Trailing Zeroes
> 470. Implement Rand10() Using Rand7()

### `22. array`
>* 剑指 Offer 66. 构建乘积数组

### `23. 二叉搜索树`

>* 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
>* 剑指 Offer 68 - II. 二叉树的最近公共祖先
>* 二叉树的下一个结点


### 算法和数据结构(学习相关书籍推荐)

>- 算法图解.pdf  [百度云下载链接](https://pan.baidu.com/s/1dhEy_uvJYoqehdvYnHzoBg)  密码:lk0v
>- 算法第四版.pdf  [百度云下载链接](https://pan.baidu.com/s/1b89HDicDLsCC_qg894FUvA)  密码:gsjc
>- 算法导论第三版.pdf  [百度云下载链接](https://pan.baidu.com/s/1ljP9Qwg5RqL_4LzrYK9jrA)  密码:qans
>- 数据结构与算法经典问题解析Java语言描述.pdf  [百度云下载链接](https://pan.baidu.com/s/1cXLrpad3Z-huk5otPVMMjg)  密码:m7ef
>- 数据结构与算法分析:C语言描述_原书第2版.pdf  [百度云下载链接](https://pan.baidu.com/s/1MudCT3RNO9I991surooqgg)  密码:1w5g
>- 大话数据结构.pdf  [百度云下载链接](https://pan.baidu.com/s/1dyH64h2603-ag8Yk6UM94w)  密码:h5du
>- 编程之美——微软技术面试心得.pdf  [百度云下载链接](https://pan.baidu.com/s/1r1VkAgh03G5Zfha35coyrg)  密码:rcpv
>- 编程之法.pdf  [百度云下载链接](https://pan.baidu.com/s/1jbypY-mQxJ1M1Hz97ptFjQ)  密码:0cv3
>- 背包九讲.pdf  [百度云下载链接](https://pan.baidu.com/s/13-ov__8xJ_SSxCmhkP4iSQ)  密码:he90
>- 啊哈算法.pdf  [百度云下载链接](https://pan.baidu.com/s/1vO9c3T3v89krlMsWEGDQCw)  密码:h89a
>- Algorithms, 4th Edition(算法，第四版).pdf  [百度云下载链接](https://pan.baidu.com/s/1ugDCe6ISRoa1Zi3UGW5Ncw)  密码:ipni
>- 《LeetCode101（谷歌师兄刷题笔记）》[百度网盘链接](https://pan.baidu.com/s/1PERa4bL7K-FoXit5440YNQ)  密码: 14fn
>- 《第二份谷歌刷题笔记》 [百度网盘链接](https://pan.baidu.com/s/1HMJvHjB964OpwtHAJQrPQw)  密码: k70j
>-  阿里霜神-《LeetCode刷题手册》 [百度网盘链接](https://pan.baidu.com/s/1817n69g0eOj7fptRpdR3kQ)  密码: fwtn


### Donate

如果本仓库对你有帮助，可以请作者喝杯速溶咖啡,给大家推荐个Google大佬的算法课程。