常用算法整理

原创

王磊-字节跳动

修改于 2019-08-20 21:52:23

1.3K0

修改于 2019-08-20 21:52:23

文章被收录于专栏：01ZOO

由于无法发送超过5万字文章，内容见附件

leetcode算法笔记.pdf

概念和理论
- 主定理
基础数据结构
- 栈
  - 例子：转逆波兰式
  - 例子：132 Pattern
  - 例子：# Lexicographical Numbers
  - 例子： Shortest Unsorted Continuous Subarray
- 最小/最大堆
  - 例子：最小堆的实现
  - 例子：Merge k Sorted Lists
  - 例子：Find Median from Data Stream
  - 例子：窗口下的最大值
  - 例子：Bathroom Stalls
- 链表
  - 链表问题的技巧
  - 链表相交的问题:
  - 例子：Palindrome Linked List
- 重要：树的分类、概念和性质
  - AVL树
  - 例子：Verify Preorder Serialization of a Binary Tree
- 字典树（前缀树）
  - 例子：前缀树实现
  - 例子：## Maximum XOR of Two Numbers in an Array
  - 例子：Prefix and Suffix Search
- 线段树/Segment Tree
  - 例子：My Calendar III
- Binary Indexed Tree
- 哈夫曼（huffman）树和哈夫曼编码
  - 例子：石堆合并问题全部相加（add all）
- 哈希表
  - 例子：和为0的4个值
- 数据结构设计
  - 例子: # Insert Delete GetRandom O(1)
  - 例子：Random Pick with Blacklist
  - 例子: Maximum Frequency Stack
- 并查集 Union Find
  - 例子：Bricks Falling When Hit
- Python Library
图
- 图的遍历
  - 例子：Pacific Atlantic Water Flow
  - 例子：Concatenated Words
  - 例子：Cat and Mouse
  - 例子： K-Similar Strings
- 欧拉回路
  - 例子: Reconstruct Itinerary
  - 例子: Cracking the Safe
- 强连通分支
- 最短路径问题
  - 例子：Evaluate Division
  - 例子：几种算法实现对比
回溯和枚举
- 例子：Sudoku Solver
- 例子：N-Queens
- 例子：Wildcard Matching
- 例子：Expression Add Operators
- 例子：环形跑道
- 例子：# 最优账户平衡
- 例子：Matchsticks to Square
- 例子：Zuma Game
遍历/剪枝技巧
- Largest Rectangle in Histogram
- Unique Substrings in Wraparound String
- Container With Most Water
- 例子：# Trapping Rain Water II
- 例子：UVa 1442 Cave
- Maximum Subarray
- Minimum Window Substring
- Candy
- 例子：House Robber
- 例子：# Longest Consecutive Sequence
- Search a 2D Matrix II
- 例子：# Longest Substring with At Least K Repeating Characters
- 例子：Count Binary Substrings
- 例子： Stamping The Sequence
- KMP算法
  - shortest-palindrome
  - 例子：# Repeated Substring Pattern
  - 判断旋转词
贪心算法 Greedy
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock IV
- 例子（重要）：Longest Increasing Subsequence
- 例子： Patching Array
- 例子：Course Schedule III
- 例子：Split Array into Consecutive Subsequences
递归/Divide And Conquer
- 例子：Copy List with Random Pointer
- 例子：Remove Duplicate Letters
- 例子：# Split Array Largest Sum
- 例子：# Super Egg Drop
- 例子：Scramble String
- 例子：Special Binary String
- 例子：# K-th Smallest Prime Fraction
- 例子：Find K-th Smallest Pair Distance
- 例子：Rotated Digits
- 例子：抄书
- 例子：# Create Maximum Number
- 例子：# Elimination Game
- 例子：# Beautiful Array
- 例子：# Bit Party
计算几何
- 点
  - 例子：Perfect Rectangle
- 面
经典算法
- 卡特兰数问题的变种
  - Generate Parentheses
- FindTarget/LowerBound/UpperBound
  - Find First and Last Position of Element in Sorted Array
- MinMax Problem
- 总结：# Sliding Window Problem
  - [Find All Anagrams in a String](https://leetcode.com/problems/find-all-anagrams-in-a-string/description/)
  - [Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/description/)
  - [Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)
  - [Substring with Concatenation of All Words](https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/)
  - [Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/)
- 蓄水池抽样
- 布隆过滤器
- Boyer-Moore Majority Vote
  - 例子：Majority Element II
- Manacher算法：求最大长度回文字串的线性算法
- Next Permutation
- 几何经典算法
  - 找fence: Monotone_Chain_Convex_Hull
- 图着色问题
  - 例子：Is Graph Bipartite
- 随机洗牌算法
  - 例子: # Random Flip Matrix
- 三色旗问题
- 二分图匹配-匈牙利算法
Brain Storm
- 例子：Transform to Chessboard
- 例子：Orderly Queue
- 例子: Roller Coaster Scheduling
- 例子：Couples Holding Hands
- 例子：Number of Subarrays with Bounded Maximum