LeetCode-Go

# LeetCode in Go

English | 中文

[LeetCode Online Judge](https://leetcode.com/) is a website containing many **algorithm questions**. Most of them are real interview questions of **Google, Facebook, LinkedIn, Apple**, etc. and it always help to sharp our algorithm Skills. Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. This repo shows my solutions in Go with the code style strictly follows the [Google Golang Style Guide](https://github.com/golang/go/wiki/CodeReviewComments). Please feel free to reference and **STAR** to support this repo, thank you!

The solution e-book *LeetCode Cookbook*, with Progressive Web App and Dark Mode support — Online Reading

Offline PDF edition of the e-book *LeetCode Cookbook* — Download here

Install the PWA edition of *LeetCode Cookbook* to your home screen from an iOS / Android browser and study anytime.

## Data Structures > Topics marked with ✅ have all their problems completed; those without the mark still have problems left to solve. * [Array](#array) * [String](#string) * [✅ Two Pointers](#two-pointers) * [✅ Linked List](#linked-list) * [✅ Stack](#stack) * [Tree](#tree) * [Dynamic programming](#dynamic-programming) * [✅ Backtracking](#backtracking) * [Depth First Search](#depth-first-search) * [Breadth First Search](#breadth-first-search) * [Binary Search](#binary-search) * [Math](#math) * [Hash Table](#hash-table) * [✅ Sort](#sort) * [✅ Bit Manipulation](#bit-manipulation) * [✅ Union Find](#union-find) * [✅ Sliding Window](#sliding-window) * [✅ Segment Tree](#segment-tree) * [✅ Binary Indexed Tree](#binary-indexed-tree)

| Data Structure | Variants | Related Problems | Articles | |:-------:|:-------|:------|:------| |Sequential list: vector|||| |Singly linked list|1. Doubly linked list
2. Static linked list
3. Symmetric matrix
4. Sparse matrix||| |Hash table|1. Hash functions
2. Collision resolution / load factor
||| |Stack and queue|1. Generalized stack
2. Deque
||| |Queue|1. Linked-list implementation
2. Circular-array implementation
3. Deque||| |String|1. KMP algorithm
2. Finite-state automaton
3. Pattern-matching finite-state automaton
4. Boyer-Moore (BM) algorithm
5. BM-KMP algorithm
6. Brute-force (BF) algorithm||| |Tree|1. Binary tree
2. Union-Find (disjoint set)
3. Huffman tree||| |Array-based heap|1. Max-heap and min-heap
2. Min-max heap
3. Double-ended heap (deap)
4. d-ary heap||| |Tree-based heap|1. Leftist heap
2. Skew heap
3. Binomial heap
4. Fibonacci heap
5. Pairing heap||| |Search|1. Hash table
2. Skip list
3. Binary search tree
4. AVL tree
5. B-tree / B+ tree / B* tree
6. AA tree
7. Red-black tree
8. Sorted binary heap
9. Splay tree
10. Double-chained tree
11. Trie
12. R-tree||| ## Algorithm | Algorithm | Specific Types | Related Problems | Articles | |:-------:|:-------|:------|:------| |Sorting algorithms|1. Bubble sort
2. Insertion sort
3. Selection sort
4. Shell sort
5. Quicksort
6. Merge sort
7. Heap sort
8. Linear-time sorting
9. Introsort
10. Indirect sort
11. Counting sort
12. Radix sort
13. Bucket sort
14. External sort - k-way merge with a loser tree
15. External sort - optimal merge tree||| |Recursion & divide and conquer||1. Binary search
2. Multiplication of large integers
3. Strassen's matrix multiplication
4. Chessboard covering
5. Merge sort
6. Quicksort
7. Linear-time selection
8. Closest pair of points
9. Round-robin tournament scheduling
|| |Dynamic programming||1. Matrix-chain multiplication
2. Longest common subsequence
3. Maximum subarray sum
4. Optimal triangulation of a convex polygon
5. The polygon game
6. Image compression
7. Circuit wiring
8. Flow-shop scheduling
9. 0-1 knapsack / the "nine knapsack lectures"
10. Optimal binary search tree
11. DP speed-up principles
12. Tree DP
|| |Greedy||1. Activity-selection problem
2. Optimal loading
3. Huffman coding
4. Single-source shortest paths
5. Minimum spanning tree
6. Multi-machine scheduling
|| |Backtracking||1. Loading problem
2. Batch-job scheduling
3. Sign-of-triangle problem
4. n-queens problem
5. 0-1 knapsack
6. Maximum-clique problem
7. Graph m-coloring problem
8. Traveling-salesman problem
9. Circle-arrangement problem
10. Circuit-board placement problem
11. Consecutive-postage problem
|| |Search|1. Enumeration
2. DFS
3. BFS
4. Heuristic search
||| |Randomization|1. Random numbers
2. Numerical randomized algorithms
3. Sherwood algorithm
4. Las Vegas algorithm
5. Monte Carlo algorithm
|1. Computing the value of π
2. Computing definite integrals
3. Solving nonlinear systems
4. Linear-time selection
5. Skip list
6. n-queens problem
7. Integer factorization
8. Majority-element problem
9. Primality testing
|| |Graph theory|1. Traversal: DFS / BFS
2. AOV / AOE networks
3. Kruskal's algorithm (MST)
4. Prim's algorithm (MST)
5. Borůvka's algorithm (MST)
6. Dijkstra's algorithm (single-source shortest path)
7. Bellman-Ford algorithm (single-source shortest path)
8. SPFA algorithm (single-source shortest path)
9. Floyd algorithm (all-pairs shortest path)
10. Johnson's algorithm (all-pairs shortest path)
11. Fleury's algorithm (Eulerian circuit)
12. Ford-Fulkerson algorithm (max-flow augmenting path)
13. Edmonds-Karp algorithm (max flow)
14. Dinic's algorithm (max flow)
15. Generic push-relabel algorithm
16. Highest-label push-relabel (HLPP) algorithm
17. Primal-Dual algorithm (min-cost flow)18. Kosaraju's algorithm (strongly connected components)
19. Tarjan's algorithm (strongly connected components)
20. Gabow's algorithm (strongly connected components)
21. Hungarian algorithm (bipartite matching)
22. Hopcroft-Karp algorithm (bipartite matching)
23. Kuhn-Munkres algorithm (optimal bipartite matching)
24. Edmonds' Blossom-Contraction algorithm (general graph matching)
|1. Graph traversal
2. Strong/weak connectivity of directed and undirected graphs
3. Cut vertices / cut edges
3. AOV networks and topological sorting
4. AOE networks and the critical path
5. Minimum-cost spanning tree / second-best MST
6. Shortest-path problem / K-th shortest path
7. Maximum-flow problem
8. Minimum-cost flow problem
9. Graph-coloring problem
10. System of difference constraints
11. Eulerian circuit
12. Chinese postman problem
13. Hamiltonian cycle
14. Best edge/vertex cut set / minimum edge/vertex cut set / minimum path cover / minimum vertex cover
15. Edge cover set
16. Bipartite perfect matching and maximum matching
17. Cactus graph
18. Chordal graph
19. Stable-marriage problem
20. Maximum-clique problem
|| |Number theory||1. Greatest common divisor
2. Least common multiple
3. Prime factorization
4. Primality testing
5. Base conversion
6. Arbitrary-precision arithmetic
7. Divisibility
8. Congruences
9. Euler's totient function
10. Extended Euclidean algorithm
11. Permutation groups
12. Generating functions
13. Discrete transforms
14. Cantor expansion
15. Matrices
16. Vectors
17. Systems of linear equations
18. Linear programming
|| |Geometry||1. Convex hull - gift wrapping
2. Convex hull - Graham scan
3. Line-segment problems
4. Problems on polygons and polyhedra
|| |NP-completeness|1. Computation models
2. Class-P and class-NP problems
3. NP-complete problems
4. Approximation algorithms for NP-complete problems
|1. Random-access machine (RAM)
2. Random-access stored-program machine (RASP)
3. Turing machine
4. Non-deterministic Turing machine
5. Class-P and class-NP languages
6. Polynomial-time verification
7. Polynomial-time reduction
8. Cook's theorem
9. CNF satisfiability (CNF-SAT)
10. 3-CNF satisfiability (3-SAT)
11. Clique problem (CLIQUE)
12. Vertex-cover problem (VERTEX-COVER)
13. Subset-sum problem (SUBSET-SUM)
14. Hamiltonian-cycle problem (HAM-CYCLE)
15. Traveling-salesman problem (TSP)
16. Approximation algorithm for vertex cover
17. Approximation algorithm for TSP
18. TSP with the triangle inequality
19. General TSP
20. Approximation algorithm for set cover
21. Approximation algorithm for subset sum
22. Exponential-time algorithm for subset sum
23. Polynomial-time approximation scheme for subset sum
|| ## LeetCode Problems ## 1. Personal Stats | | Easy | Medium | Hard | Total | |:--------:|:--------:|:--------:|:--------:|:--------:| |Optimizing|31|78|43|152| |Accepted|**287**|**484**|**142**|**913**| |Total|600|1305|539|2444| |Perfection Rate|89.2%|83.9%|69.7%|83.4%| |Completion Rate|47.8%|37.1%|26.3%|37.4%| ## 2. Directory 787 problems already have solutions here; another 11 are still being optimized toward beats 100%. | No. | Title | Solution | Acceptance | Difficulty | Frequency | |:--------:|:--------------------------------------------------------------|:--------:|:--------:|:--------:|:--------:| |0001|Two Sum|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0001.Two-Sum)|49.1%|Easy|| |0002|Add Two Numbers|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0002.Add-Two-Numbers)|39.7%|Medium|| |0003|Longest Substring Without Repeating Characters|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0003.Longest-Substring-Without-Repeating-Characters)|33.8%|Medium|| |0004|Median of Two Sorted Arrays|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0004.Median-of-Two-Sorted-Arrays)|35.1%|Hard|| |0005|Longest Palindromic Substring|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0005.Longest-Palindromic-Substring)|32.4%|Medium|| |0006|Zigzag Conversion|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0006.Zigzag-Conversion)|43.0%|Medium|| |0007|Reverse Integer|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0007.Reverse-Integer)|27.2%|Medium|| |0008|String to Integer (atoi)|[Go](https://github.com/halfrost/LeetCode-Go/tree/master/leetcode/0008.String-to-Integer-atoi)|16.6%|Medium|| |0009|Palindrome Number|[Go](htt