Algorithm templates and LeetCode Solutions

TBD

• Add multi binary search algorithm for leetcode0034
• Add Segment Tree for data structure
• Add union-find algorithm(Disjoint Set Union) for data structure
• Add catalan number
• 全错位排列问题
• LeetCode1467 概率问题

Notes

此处主要加入自己的学习笔记

快速幂/矩阵快速幂

支持向量机

• 还需要补充完善

Buffon’s Needle Problem 一个几何概型问题，以及采样的技巧

组合数学常用公式 总结组合数学常用公式

线性可分感知机及其对偶形式 感知机建模，推导以及Gram矩阵优化

@classmethod 多态 Effective Python 笔记

Design

Circular Queue

LRU Cache LRU缓存, OrderedDict(链表+字典)

De/Serialize Binart Tree 二叉树序列化, 反序列化 BFS

Maths

Catalan Number: O(n) solution use binomial coefficient

compute square root: 计算平方根, 牛顿法

Josephus Problem: 约瑟夫环问题

Bézout's lemma 裴蜀定理/贝祖定理 判断$ax + by = c$ 是否有整数解

快速幂/矩阵快速幂 md

Fast Pow and Matrix Application quick pow algorithm

Greatest Common Divisor(GCD) Euclidean algorithm

**Sieve of Eratosthenes ** 埃拉托斯特尼筛法/埃氏筛 求自然数n以内的所有素数

Buffon’s Needle 布丰问题/几何概型

Reservoir Sampling 蓄水池抽样, 从流数据中等概率采集 k 个样本

Data Structures

Fenwick Tree or Binary Indexed Tree(BIT) 树状数组

Binary Tree 二叉树 深度/遍历/序列化/反序列化等

Linked List 链表 逆序等

Heap 堆(优先队列) 通过heapq实现

Trie Tree 前缀树/字典树 O(M) M是最长字符串的长度

HashSet哈希集合(list + BST)

HashMap 哈希映射 (list + linkedlist)

Geometry

Rectangles in Rectangles 计算一个矩形能否放入另一个矩形中 参考

Check Overlap 判断圆和矩形是否有重叠 参考

Check tow line intersection 判断两个线段是否相交 参考

Maximum Points in A Line 给定一堆点, 判断同一条线上的点的最多数量 参考

Angular Sweep (Maximum points that can be enclosed in a circle of given radius) 给定一堆点, 和一个圆的半径, 判断圆最多能覆盖多少个点 参考

Rotated IoU 计算旋转矩形框的面积

Graph

Dijkstra 最短路径算法 以及 堆优化版本

Kruskal MST 图的最小生成树

Search and Sort

Binary Search Method O(logn) 二分查找代码包括上界和下界搜索

Sorting algorithms 排序算法集合

• 加入快排partition

Boyer-Moore majority vote algorithm 对拼消耗

Quick select 快速选择算法O(n)时间选择出最小的第k的元素

Partitions 不同的partition方式, 对重复/近似排序序列

quickseletc ~O(n) alogrithm for Top-k problem

String

KMP 字符串匹配算法

RE-match 正则表达式匹配

LCS 最长公共子序列

Longest Substring without Repeating Characters 最长无重复字符子序列滑动窗口法

机器学习

precepton 线性感知机对偶形式建模，优化，Gram计算

LeetCode Solutions

TBD:

• LeetCode0004

• LeetCode0010: memorize dp

• LeetCode0030

See LeetCodeList.

剑指Offer

剑指 Offer 所有python题解已全部完成

TBD:

• No_11: add binary search solution

• No_36: add non-recursive solution