Functions — github.com/EndlessCheng/codeforces-go

hub / github.com/EndlessCheng/codeforces-go / functions

Functions8,098 in github.com/EndlessCheng/codeforces-go

⨍ Functions 8,098◇ Types & classes 911

MethodsecondDiameter

非严格次长直径 https://ac.nowcoder.com/acm/contest/9557/C

copypasta/graph_tree.go:372

FunctionsecondMinimum

* BFS 求次短路，附详细注释 */ github.com/EndlessCheng/codeforces-go

leetcode/weekly/263/d/d.go:7

MethodsegProperIntersection

线段规范相交 CCW (counterclockwise)

copypasta/geometry.go:438

FunctionsequentialDigits

(low int, high int)

leetcode/weekly/167/b/b.go:5

(grid [][]int, k int)

leetcode/weekly/163/main.go:41

FunctionshiftGrid

(grid [][]int, k int)

leetcode/weekly/163/a/a.go:3

FunctionshipWithinDays

github.com/EndlessCheng/codeforces-go

leetcode/weekly/128/c/c.go:6

FunctionshortestAlternatingPaths

(n int, redEdges [][]int, blueEdges [][]int)

leetcode/weekly/146/b/b.go:3

MethodshortestCycleBFS

BFS 应用：求无向无权图最小环长度好题 https://codeforces.com/problemset/problem/1325/E

copypasta/graph.go:467

MethodshortestCycleFloydWarshall

最小环传入邻接矩阵 weights weights[v][w] == inf 表示没有 v-w 边 https://oi-wiki.org/graph/min-circle/#floyd NOTE: 无权图的情况见 shortestCycleBFS

copypasta/graph.go:1382

FunctionshortestDistanceColor

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/8/c/c.go:6

FunctionshortestPath

(g [][]int, kk int)

leetcode/weekly/167/d/d.go:3

MethodshortestPathDijkstra2

另一种 Dijkstra 写法适用于稠密图 O(n^2)

copypasta/graph.go:1158

MethodshortestPathFloydWarshall

任意两点最短路 Floyd-Warshall O(n^3) 本质是求 Min-plus matrix multiplication 传入邻接矩阵 dist dist[v][w] == inf 表示没有 v-w 边 https://en.wikipedia.org/wiki/Floyd%E2%8

copypasta/graph.go:1317

MethodshortestPathJohnson

任意两点最短路 Johnson O(nmlogm) 若有负环返回 nil https://en.wikipedia.org/wiki/Johnson%27s_algorithm https://oi-wiki.org/graph/shortest-path/#johnson 模板题 https://

copypasta/graph.go:1417

Functionshuffle

(a []int, n int)

leetcode/weekly/192/a/a.go:3

FunctionsimplifiedFractions

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/26/b/b.go:6

FunctionsimulatedAnnealing

* 随机化技巧 https://oi-wiki.org/misc/rand-technique/ https://codeforces.com/problemset/problem/995/C https://codeforces.com/problemset/problem/1314/D 推荐

copypasta/rand.go:36

FunctionsimulatedAnnealingWithinTimeLimit

另一种写法（利用时限）此时 alpha 可以设大点，例如 0.999

copypasta/rand.go:53

FunctionsingleNonDuplicate

LC 540 有序数组中的单一元素

leetcode/main.go:1341

FunctionsingleNumber

https://halfrost.com/go_s2_de_bruijn/ LC137 https://leetcode-cn.com/problems/single-number-ii/ 除了某个元素只出现一次以外，其余每个元素均出现了三次。返回只出现了一次的元素定义两个集合 ones 和

copypasta/bits.go:565

github.com/EndlessCheng/codeforces-go

leetcode/weekly/212/a/a.go:4

FunctionsmallerNumbersThanCurrent

(a []int)

leetcode/weekly/178/a/a.go:3

FunctionsmallestChair

事件扫描线+堆 github.com/EndlessCheng/codeforces-go

leetcode/biweekly/57/b/b.go:11

FunctionsmallestCommonElement

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/9/c/c.go:6

FunctionsmallestDivisor

(nums []int, threshold int)

leetcode/weekly/166/c/c.go:5

FunctionsmallestEnclosingDisc

最小圆覆盖 Welzl's algorithm 随机增量法，期望复杂度 O(n) 详见《计算几何：算法与应用（第 3 版）》第 4.7 节 https://en.wikipedia.org/wiki/Smallest-circle_problem https://oi-wiki.org/geomet

copypasta/geometry.go:606

FunctionsmallestEqual

github.com/EndlessCheng/codeforces-go

leetcode/weekly/265/a/a.go:4

FunctionsmallestMissingValueSubtree

github.com/EndlessCheng/codeforces-go

leetcode/weekly/258/d/d.go:4

FunctionsmallestRangeII

github.com/EndlessCheng/codeforces-go

leetcode/weekly/103/c/c.go:6

FunctionsmallestStringWithSwaps

(s string, pairs [][]int)

leetcode/weekly/155/c/c.go:5

FunctionsmallestStringWithSwapsCC

(s string, pairs [][]int)

leetcode/weekly/155/c/c.go:45

FunctionsmallestSubsequence

github.com/EndlessCheng/codeforces-go

leetcode/weekly/261/d/d.go:6

FunctionsmallestSubsequence

github.com/EndlessCheng/codeforces-go

leetcode/weekly/140/d/d.go:4

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6629/a/a.go:4

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/10167/c/c.go:4

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6357/a/a.go:48

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6357/b/b.go:4

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6383/c/c.go:9

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6383/b/b.go:6

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6778/a/a.go:4

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6778/b/b.go:9

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6489/a/a.go:4

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6913/a/a.go:9

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6913/c/c.go:4

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6218/b/b.go:4

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6384/a/a.go:6

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6384/b/b.go:4

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6219/c/c.go:30

Functionsolve

(n int, a [][]int)

misc/nowcoder/10325/c/c.go:17

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/9557/b/b.go:6

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/9887/b/b.go:4

Functionsolve

github.com/EndlessCheng/codeforces-go

misc/nowcoder/6916/a/a.go:9

Methodsolve2SAT

Gabow's algorithm 常数比 Kosaraju 大 https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/GabowSCC.java.html 2-Satisfiability (2-SAT) https://oi-wik

copypasta/graph.go:2839

FunctionsolveSudoku

LC 37

leetcode/main.go:81

Functionsolve_bangbang

github.com/EndlessCheng/codeforces-go

misc/nowcoder/9716/b/b.go:5

FunctionsortByBits

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/20/a/a.go:9

MethodsortBytes

https://codeforces.com/problemset/problem/558/E

copypasta/odt_bst.go:52

FunctionsortCollections

(n, m int, group []int, beforeItems [][]int)

leetcode/weekly/155/d/d.go:24

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/52/a/a.go:9

FunctionsortString

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/21/a/a.go:4

FunctionsparseTableCollections

* 稀疏表 Sparse Table st[i][j] 对应的区间是 [i, i+2^j) https://oi-wiki.org/ds/sparse-table/ https://codeforces.com/blog/entry/66643 Tarjan RMQ https://codeforc

copypasta/sparse_table.go:19

FunctionspecialArray

github.com/EndlessCheng/codeforces-go

leetcode/weekly/209/a/a.go:4

Methodsplit

EXTRA: 线段树分裂将区间 [l,r] 从 o 中分离到 b 上 https://www.luogu.com.cn/blog/cyffff/talk-about-segument-trees-split https://www.luogu.com.cn/problem/P5494 rt, rt

copypasta/segment_tree.go:504

Methodsplit

分裂子树 o，把 o 的前 k 小个节点放在 lo 子树，其他的放在 ro 子树（lo 节点为 o 的第 k 小节点） 0 < k <= o.size()，取等号时 ro 为 nil

copypasta/splay.go:99

FunctionsplitArray

(a []int)

leetcode/season/2020spring2/d/d.go:3

FunctionsplitPainting

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/57/c/c.go:6

FunctionsplitString

github.com/EndlessCheng/codeforces-go

leetcode/weekly/239/b/b.go:9

MethodspreadAll

EXTRA: 适用于需要提取所有元素值的场景

copypasta/segment_tree.go:305

FunctionsqrtDecompositionCollections

* 分块思想 Sqrt Decomposition 一种技巧：组合两种算法从而降低复杂度 O(n^2) -> O(n√n) 参考 Competitive Programmer’s Handbook Ch.27 题目花样很多，下面举个例子有 n 个对象，每个对象有一个「关于其他对象的统计量」ci（

copypasta/sqrt_decomposition.go:53

Functionstick

github.com/EndlessCheng/codeforces-go

misc/nowcoder/9224/a/a.go:4

FunctionstoneGame

github.com/EndlessCheng/codeforces-go

leetcode/weekly/95/b/b.go:4

FunctionstoneGameIII

(a []int)

leetcode/weekly/183/d/d.go:3

FunctionstoneGameIX

(stones []int)

leetcode/weekly/261/c/c.go:33

FunctionstoneGameV

github.com/EndlessCheng/codeforces-go

leetcode/weekly/203/d/d.go:4

FunctionstoneGameVI

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/41/c/c.go:6

FunctionstoneGameVII

github.com/EndlessCheng/codeforces-go

leetcode/weekly/219/c/c.go:4

FunctionstoneGameVIII

github.com/EndlessCheng/codeforces-go

leetcode/weekly/242/d/d.go:4

FunctionstrWithout3a3b

bugfree 的写法

leetcode/weekly/121/a/a.go:4

FunctionstrWithout3a3b_

较麻烦的写法

leetcode/weekly/121/a/a.go:29

MethodstrictlySecondMST

严格次小生成树 Second best Minimum Spanning Tree https://oi-wiki.org/graph/mst/#_13 https://cp-algorithms.com/graph/second_best_mst.html 模板题（严格）https://www.l

copypasta/graph.go:1738

Functionstring2

github.com/EndlessCheng/codeforces-go

misc/nowcoder/9716/a/a.go:6

FunctionstringCollection

* 字符串问题的特殊性：不同子串之间会共享一些局部信息，巧妙地利用这些局部信息可以设计出更加高效的算法。 todo NOI 一轮复习 II：字符串 https://www.luogu.com.cn/blog/ix-35/noi-yi-lun-fu-xi-ii-zi-fu-chuan 金策字符串

copypasta/strings.go:27

FunctionstringMatching

(a []string)

leetcode/weekly/184/a/a.go:10

FunctionstringMatchingSA

O(∑len(a[i]))

leetcode/weekly/184/a/a.go:23

Methodsub

(b matrix)

copypasta/math_matrix.go:144

FunctionsubArrayRanges

github.com/EndlessCheng/codeforces-go

leetcode/weekly/271/b/b.go:91

FunctionsubArrayRanges2

* 从 O(n^2) 到 O(n)：单调栈+计算每个元素对答案的贡献 #### 方法一：暴力枚举所有子数组写一个二重循环，外层循环枚举子数组的左边界，内层循环枚举子数组的右边界，同时维护当前子数组的最小值和最大值。 ```go func subArrayRanges(nums []int)

leetcode/weekly/271/b/b.go:75

FunctionsubarrayBitwiseORs

github.com/EndlessCheng/codeforces-go

leetcode/weekly/100/c/c.go:4

copypasta/geometry.go:184

← previous next →7,901–8,000 of 8,098, ranked by callers