代码拉取完成，页面将自动刷新
作者： Jam
- 个人简介： 化工行业转行计算机全靠自学，目前在国内大厂工作，在力扣上传了数百道问题的解法，本仓库主要是为了总结算法套路与帮助和我一样转行，以及想深入学习算法有大厂梦的兄弟和姐妹们。
算法题分类思维导图：
本仓库的 leetcode 文件夹下都是基于 LeetCode 的题目，涵盖了所有题型和技巧，而且一定要做到举一反三，通俗易懂，算法体系化学习书籍和面试题有相关算法系统学习书籍和题目推荐。
20 个最常用的、最基础数据结构与算法，都已经总结在 算法题模板分类
10 个必考数据结构模板：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树。
10 个必会算法模板：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
1. 滑动窗口
- 大小为 K 的子数组的最大和
- Best Time to Buy and Sell Stock
- Longest Substring Without Repeating Characters
- Sliding Window Maximum
- 剑指 Offer 57 - II. 和为s的连续正数序列
# 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，反正一般都是头尾各一个指针，然后根据条件移动。
- Two Sum（# 也可以用map的方式做）
- Two Sum II - Input array is sorted
- Squares of a Sorted Array (很像merge sort里的merge）
- Move Zeroes
- Remove Element
- Remove Duplicates from Sorted Array
- 3Sum Closest
- 4Sum
- Partition List
- Container With Most Water
- Trapping Rain Water
- Sort Colors
- 剑指 Offer 04. 二维数组中的查找
- 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
# 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个元素。
- Linked List Cycle
- Linked List Cycle II
- Palindrome Linked List
- Rotate List
- 剑指 Offer 18. 删除链表的节点 JZ56 删除链表中重复的结点
- 剑指 Offer 22. 链表中倒数第k个节点
- 剑指 Offer 52. 两个链表的第一个公共节点
4. 原地链表翻转
- Palindrome Linked List
- Reverse Linked List
- Reverse Nodes in k-Group
- Reverse Linked List II
5. 区间合并
区间合并的问题，通常是重新把区间按照start和end排序，重新组合区间。
- Merge Intervals
- Interval List Intersections
- Insert Interval
6. 无序限定范围的数组元素查找O(N）
要求 inplace， 通常是采用正负反转的做法
- First Missing Positive
- Find All Numbers Disappeared in an Array 剑指 Offer 03. 数组中重复的数字
7. BFS
BFS 通常采用queue 来实现
- Binary Tree Level Order Traversal
- Binary Tree Zigzag Level Order Traversal
- Serialize and Deserialize Binary Tree
- Word Ladder I
- Course Schedule【拓扑排序】
8. 树的DFS
通常采用递归 111. Minimum Depth of Binary Tree
- Path Sum
- Path Sum II（和剑指 Offer 34. 二叉树中和为某一值的路径一样）
- Path Sum III
- Same Tree
- Symmetric Tree
- Maximum Depth of Binary Tree
- Balanced Binary Tree
- 剑指 Offer 26. 树的子结构
- 剑指 Offer 33. 二叉搜索树的后序遍历序列
- 剑指 Offer 54. 二叉搜索树的第k大节点(inorder)
9. DFS/递归/回溯法
对于排列和组合的题目，需要主要判断是否会有重复数字，如有重复，需要先进行sort，而且需要进行剪枝。
- Subsets
- Subsets II
- Permutations
- Permutations II
- Combination Sum
- Coin Change
- Coin Change 2
- Combination Sum II
- Palindrome Partitioning !
- Letter Combinations of a Phone Number (differ from 91. Decode Ways)
- Word Search(same as 剑指 Offer 12. 矩阵中的路径)
- 剑指 Offer 13. 机器人的运动范围
- 双堆模式 295 Find-Median-from-Data-Stream
- Sliding Window Median
- Min Stack
- 剑指 Offer 09. 用两个栈实现队列
11. 二分法与二分法变种
当你需要解决的问题的输入是排好序的数组，链表，或是排好序的矩阵，要求咱们寻找某些特定元素。这个时候的不二选择就是二分搜索。
- Search Insert Position
- Find First and Last Position of Element in Sorted Array
- Search in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II(same as [剑指 Offer 11. 旋转数组的最小数字])
- Find Peak Element
- Single Element in a Sorted Array
- 剑指 Offer 16. 数值的整数次方(2分法)
12. 前K大的数模式HEAP
采用priority queue 或者 说在python 中的heapq 求top k 采用最小堆（默认） 采用最大堆的时候可以采用push 负的value
- Kth Largest Element in an Array
- Top K Frequent Elements
- Find K Pairs with Smallest Sums
13. K路归并
K路归并能帮咱们解决那些涉及到多组排好序的数组的问题。
- Merge k Sorted Lists
- Merge Two Sorted Lists
14. DP 动态规划
- Longest Increasing Subsequence
- Longest Common Subsequence
- Edit Distance
- Wildcard Matching
- Regular Expression Matching
- Triangle
- Maximum Subarray
- Maximum Product Subarray
- Super Egg Dropref
- House Robber
- House Robber II (两个dp）
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock IV
- Best Time to Buy and Sell Stock III ref
- Best Time to Buy and Sell Stock with Transaction Fee
- Best Time to Buy and Sell Stock with Cooldown
- Longest Palindromic Subsequence !
- Longest Palindromic Substring
- Partition Equal Subset Sum
- Coin Change
- Coin Change 2
- Decode Ways
- 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. 树和链表结合
- 二叉搜索树与双向链表
- Convert Sorted List to Binary Search Tree
- Flatten Binary Tree to Linked List
17. 树的重新构建
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
- Construct String from Binary Tree
- Construct Binary Search Tree from Preorder Traversal
- Construct Binary Tree from Preorder and Postorder Traversal
18. 位运算
- Single Number
- Single Element in a Sorted Array
- Reverse Bits
- 剑指 Offer 15. 二进制中1的个数
- 剑指 Offer 56 - I. 数组中数字出现的次数
- 剑指 Offer 56 - II. 数组中数字出现的次数 II
19. 字符串
一般都有很多corner cases 需要考虑
- String to Integer (atoi)
- 剑指 Offer 20. 表示数值的字符串
- 剑指 Offer 58 - I. 翻转单词顺序(2次翻转）
- 剑指 Offer 58 - II. 左旋转字符串
20. stack
- 剑指 Offer 31. 栈的压入、弹出序列
21. math
- Factorial Trailing Zeroes
- Implement Rand10() Using Rand7()
22. array
- 剑指 Offer 66. 构建乘积数组
23. 二叉搜索树
- 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
- 剑指 Offer 68 - II. 二叉树的最近公共祖先
- 二叉树的下一个结点
- 算法图解.pdf 百度云下载链接 密码:lk0v
- 算法第四版.pdf 百度云下载链接 密码:gsjc
- 算法导论第三版.pdf 百度云下载链接 密码:qans
- 数据结构与算法经典问题解析Java语言描述.pdf 百度云下载链接 密码:m7ef
- 数据结构与算法分析:C语言描述_原书第2版.pdf 百度云下载链接 密码:1w5g
- 大话数据结构.pdf 百度云下载链接 密码:h5du
- 编程之美——微软技术面试心得.pdf 百度云下载链接 密码:rcpv
- 编程之法.pdf 百度云下载链接 密码:0cv3
- 背包九讲.pdf 百度云下载链接 密码:he90
- 啊哈算法.pdf 百度云下载链接 密码:h89a
- Algorithms, 4th Edition(算法，第四版).pdf 百度云下载链接 密码:ipni
- 《LeetCode101（谷歌师兄刷题笔记）》百度网盘链接 密码: 14fn
- 《第二份谷歌刷题笔记》 百度网盘链接 密码: k70j
- 阿里霜神-《LeetCode刷题手册》 百度网盘链接 密码: fwtn
如果本仓库对你有帮助，可以请作者喝杯速溶咖啡,给大家推荐个Google大佬的算法课程。
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。