LeetCode-Py
仓库中包含2大内容. (持续更新中)- 算法库:
leetcode-alg
. - 大量基于
leetcode-alg
的leetcode(python)题目的解答(将会收集1k题以上, 目前处于开发中).
- 算法库:
LeetCode-Py
的习题解答的风格是在最优复杂度的前提下, 写出最简洁的代码, 不做过多细节的优化. 旨在将最优雅的python代码放入answer/
文件夹内.leetcode-alg
是针对leetcode解题的数据结构和算法库, 其设计哲学是: 以通用性为核心, 并以最大可能进行性能优化.
- 性能:
answer/
中time击败:- 100%: 1, 11, 16, 18, 39, 42, 46, 57, 72, 77, 78, 84, 85, 146, 167, 200, 215, 300, 354, 416, 435, 518, 1143, 1349, 2096, 2171, 2203
- 95%: 2, 22, 28, 31, 40, 47, 51, 52, 56, 90, 102, 107, 112, 113, 124, 153, 204, 207, 210, 239, 307, 322, 454, 496, 503, 704, 875, 1044, o51
- 85%: 4, 15, 19, 92, 208, 876, 1584, o40
- 60%:
- 其他:
- 已有的功能: (持续更新中)
- 算法:
- array: unique, partition, partition2, merge, merge2, diff, quick_select, two_sum, reverse, next_permutation, subsets, subsets2
- dp: LIS, LIS2, LCS, LCS2, LCS3, edit_distance, matrix_chain, matrix_chain2
- heapq: nlargest_, nsmallest_, nlargest2, nsmallest2, merge_heapq_
- graph: dijkstra, dijkstra2, dijkstra3, kruskal, prim, prim2, topo_sort, Dinic, hungarian
- greed: merge_intervals, merge_intervals2
- knapsack: knapsack, knapsackV, knapsackC, knapsackCV
- linkedlist: reverse_list, find_mid_node, find_last_kth_node
- math: is_prime, find_primes
- monotone_deque: monotone_deque
- monotone_stack: monotone_stack, monotone_stack2, monotone_stack3, largest_rect, largest_rect2
- search: lower_bound, upper_bound, n_queens
- string: build_nextval, kmp
- tree: find_path, find_common_ancestor, preorder_traversal, preorder_traversal2, inorder_traversal, inorder_traversal2, postorder_traversal, postorder_traversal2, level_order_traversal
- unimportant:
- array: euclidean_dist, manhattan_dist
- bisect: bisect_left_, bisect_right_, binary_search
- itertools: accumulate_, product_, permutations_, permutations2, combinations_, combinations2, combinations_with_replacement_, combinations_with_replacement2
- math: gcd_, lcm_, fast_pow
- random: randperm
- sort: quick_sort, merge_sort, heap_sort, heap_sort2
- 数据结构:
- binary_indexed_tree: BinaryIndexedTree, BinaryIndexedTree2
- heap: Heap, Heap2
- linkedlist: LinkedListNode, LinkedList
- segment_tree: SegmentTree, SegmentTree2
- sorted_list: SimpleSortedList
- string_hasher: StringHasher
- trie: TrieTreeNode, Trie
- union_find: UnionFind
- unimportant:
- ordered_dict: OrderedDict_
- LeetCode Tools:
- 数据结构: ListNode, TreeNode
- tools: to_linkedlist, from_linkedlist, to_tree, from_tree, call_callable_list
- 算法:
- todo
- 算法:
- monotone_deque: next_ge_k_len, prev_le_k_len
- monotone_stack: next_ge_min
- string_op: string_add, string_mul
- tree: bst_min, bst_max
- unimportant:
- math: int2str, prime_factor, BigInteger
- 数据结构:
- sorted_list: SortedList
- extension: BBST, HuffmanTree, RBTree, SkipList
- 算法:
-
安装:
# (推荐)将此仓库下载的本地, 进入setup.py所在目录, 输入以下命令 pip install . # or 从pypi下载 pip install leetcode-alg -U
-
使用: 例子可以查看
answer/
from leetcode_alg import *
- 线段树: 307
- Lazy:
- 离散化: o51
- -(易混淆): 2021
- 树状数组: 307
- 变体:
- 离散化: o51
- SortedList: o51
- 哈希表: 1143, 2183, 416
- N数: 1, 15, 454
- 链表:
- 前向链表: 2, 19, 21, 23, 24, 25, 92, 876, 2181
- 双向循环链表: OrderedDict, 146(LRU)
- 单调栈/队列
- 单调栈: 496, 503
- 双向: 42, 84, 85
- 单调队列: 239
- 单调栈: 496, 503
- 前缀树(Trie): 208
- -(易混淆): 14
- 栈: 20
- 堆: 23, 215, o40
- 可动态修改的堆(Heap2): dijkstra, prim
- UnionFind: kruskal, 200
- 分治法:
- 2路: 常见2路递归(merge sort, quick_sort, 树的dfs等), 23(相关题: n路归并)
- 二分查找:
- 自己设计cond:
- lower_bound: 4, 153, 875
- upper_bound:
- 直接调用bisect: 704
- LIS: 300, 354, 435(非递减), 1143(LCS)
- 自己设计cond:
- 滑动窗口: 3
- 搜索:
- 链:
- 回溯: 17, 22, 37, 51, 52
- 子集: 39, 40, 78, 90
- 组合: 77
- 排列: 31(相关题), 46, 47, 679
- 回溯: 17, 22, 37, 51, 52
- 树:
- 回溯: 113
- dfs: 112, 124
- 公共祖先: 2096
- 迭代式dfs: 112
- bfs: 102, 107
- 图:
- dfs: 200
- bfs: 200
- 链:
- 图算法:
- dijkstra: 2203(重边的处理)
- kruskal(稀疏图): 1584
- prim(稠密图): 1584
- 拓扑排序: 207, 210
- dinic: 1349
- 匈牙利算法: 1349
- DP(or memo-dfs):
- nums[i..j]: 5
- nums[..i]: 300, 435
- s[..i], s[..j]: 72, 1143
- 双dp: 42, 2167
- 背包: 39, 322, 416, 518
- 双指针: 11, 42
- N数: 15, 16, 18, 167
- 贪心: 11, 12, 42, 2037, 2038, 2182
- 区间贪心: 56, 57, 435
- 位运算: 2166
- 字符串:
- 字符串哈希: 28, 1044
- kmp: 28
- 中心法: 双向单调栈, 5, 2171, 2203
- 去重: 40, 47, 90
- N数: 15, 16, 18
- 排序: 去重, 离散化, kruskal, 2171
- map有序化: 2021, 2165, 2170, 2183
- with贪心: 区间贪心, 2037
- -(非显式的sort): 12, 2182
- 桶排序: 215
- int溢出: 7, 8
- 分类讨论:
- 次大/小: 2170, 2182
- 不以0开头: 7, 8, 2165
- 其他: 线段树的query_range, 4, find_common_ancestor(2096)
- 次大/小: 2170, 2182
- 随机算法: 215, o40, quick_sort
- 数学:
- gcd: 2183
- 质数: 204
- 日期:
- 暴力: 2180
- 过于简单: 2022, 2164, 2169
- 6, 9, 13, 2043