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

FunctionfindBestValue

github.com/EndlessCheng/codeforces-go

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

FunctionfindCenter

github.com/EndlessCheng/codeforces-go

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

MethodfindCentroid

树的重心性质：以重心为根时，最大子树结点数最少，且所有子树的大小都不超过节点数/2 反之，若存在一颗子树其大小超过节点数/2，则重心在该子树中一棵树最多有两个重心，且相邻拥有奇数个节点的树只有一个重心树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么距离和一样

copypasta/graph_tree.go:418

FunctionfindCriticalAndPseudoCriticalEdges

(n int, edges [][]int)

leetcode/weekly/194/d/d.go:5

MethodfindCutVertices

* Topic - DFS 树讲解+套题 https://codeforces.com/blog/entry/68138 好题：https://codeforces.com/problemset/problem/1325/F */ 割点（割顶） cut vertices / articulatio

copypasta/graph.go:656

FunctionfindDiagonalOrder

(mat [][]int)

leetcode/weekly/186/c/c.go:3

FunctionfindDifferentBinaryString

github.com/EndlessCheng/codeforces-go

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

FunctionfindDifferentBinaryString2

康托对角线

leetcode/weekly/255/b/b.go:22

MethodfindEdgeBCC

e-BCC：删除无向图中所有的割边后，剩下的每一个 CC 都是 e-BCC 缩点后形成一颗 bridge tree 模板题 https://codeforces.com/problemset/problem/1000/E 较为综合的一道题 http://codeforces.com/problems

copypasta/graph.go:906

FunctionfindEvenNumbers

枚举所有三位数偶数 github.com/EndlessCheng/codeforces-go

leetcode/weekly/270/a/a.go:6

FunctionfindGCD

github.com/EndlessCheng/codeforces-go

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

FunctionfindGoodStrings

(n int, s1 string, s2 string, evil string)

leetcode/weekly/182/d/d.go:5

FunctionfindIntegers

LC 600 不含连续 1 的非负整数

leetcode/main.go:1349

FunctionfindItinerary

LC 332

leetcode/main.go:1196

FunctionfindKthBit

github.com/EndlessCheng/codeforces-go

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

FunctionfindKthPositive

github.com/EndlessCheng/codeforces-go

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

FunctionfindLatestStep

github.com/EndlessCheng/codeforces-go

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

FunctionfindLeastNumOfUniqueInts

(a []int, k int)

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

FunctionfindLengthOfShortestSubarray

github.com/EndlessCheng/codeforces-go

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

FunctionfindLexSmallestString

github.com/EndlessCheng/codeforces-go

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

FunctionfindLucky

(arr []int)

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

FunctionfindMaxValueOfEquation

(a [][]int, k int)

leetcode/weekly/195/d/d.go:34

FunctionfindMaximumXOR

上面也可以用哈希表做 https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91049/Java-O(n)-solution-using-bit-manipulation-and-HashMap/95

copypasta/trie01.go:89

FunctionfindMinFibonacciNumbers

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/24/b/b.go:4

FunctionfindMode

LC 501

leetcode/main.go:1293

FunctionfindNumOfValidWords

github.com/EndlessCheng/codeforces-go

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

FunctionfindNumbers

(nums []int)

leetcode/weekly/168/a/a.go:5

FunctionfindOcurrences

(text string, first string, second string)

leetcode/weekly/140/a/a.go:5

FunctionfindOriginalArray

排序+遍历 github.com/EndlessCheng/codeforces-go

leetcode/biweekly/61/b/b.go:8

FunctionfindPairs

(a, b, c, d int64)

misc/nowcoder/9247/c/c.go:26

FunctionfindPeakElement

LC 162

leetcode/main.go:906

MethodfindPseudoClique

todo 基于 Capacity Scaling 的弱多项式复杂度最小费用流算法 https://ouuan.github.io/post/%E5%9F%BA%E4%BA%8E-capacity-scaling-%E7%9A%84%E5%BC%B1%E5%A4%9A%E9%A1%B9%E5%BC%8

copypasta/graph.go:3765

FunctionfindRedundantDirectedConnection

周赛出的是无向图，这里写的是有向图 Update (2017-09-26): We have overhauled the problem description + test cases and specified clearly the graph is an undirected graph.

leetcode/weekly/51/c/c.go:9

FunctionfindRepeatNumber

剑指 Offer 03. 数组中重复的数字 O(1) 空间复杂度做法

leetcode/main.go:1736

FunctionfindRotation

github.com/EndlessCheng/codeforces-go

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

FunctionfindSmallestRegion

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/13/b/b.go:4

FunctionfindSmallestSetOfVertices

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/33/b/b.go:4

FunctionfindSolution

github.com/EndlessCheng/codeforces-go

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

FunctionfindSpecialInteger

github.com/EndlessCheng/codeforces-go

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

FunctionfindTheCity

(n int, edges [][]int, distanceThreshold int)

leetcode/weekly/173/c/c.go:3

FunctionfindTheDistanceValue

github.com/EndlessCheng/codeforces-go

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

FunctionfindTheLongestSubstring

github.com/EndlessCheng/codeforces-go

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

FunctionfindTheWinner

github.com/EndlessCheng/codeforces-go

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

MethodfindVertexBCC

无向图的双连通分量 Biconnected Components (BCC) 也叫重连通图 v-BCC：任意割点都是至少两个不同 v-BCC 的公共点广义圆方树 https://oi-wiki.org/graph/bcc/ https://www.csi

copypasta/graph.go:801

FunctionfindingUsersActiveMinutes

github.com/EndlessCheng/codeforces-go

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

FunctionfirstDayBeenInAllRooms

* 前缀和优化 DP 根据题意，首次进入一个房间时，下一天是一定要回到 $\textit{nextVisit}[i]$ 房间的，下文简称为「回访」。于是定义状态 $f[i]$ 表示从房间 $i$ 回访到房间 $\textit{nextVisit}[i]$（记为 $j$），再重新访问到房间 $i

leetcode/weekly/257/c/c.go:24

FunctionfirstMissingPositive

LC 41 对未排序数组求 mex，不使用 map 的 O(n) 做法

leetcode/main.go:216

FunctionfirstPalindrome

遍历，找第一个回文串 github.com/EndlessCheng/codeforces-go

leetcode/weekly/272/a/a.go:6

github.com/EndlessCheng/codeforces-go

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

FunctionflipChess

(g []string)

leetcode/season/2021fall/c/c.go:55

Methodfloor

max <= key return nil if not found

copypasta/bst.go:96

FunctionfloorRootN

返回 floor(pow(x, 1/n)) x>=0, n>1

copypasta/geometry.go:130

MethodfloydWarshallBitset

位压缩版 O(n^3/w) LC双周赛67C https://leetcode-cn.com/problems/detonate-the-maximum-bombs/

copypasta/graph.go:1352

Methodforeach

中序遍历（如果是多重集请用下面的 foreachM）

leetcode/season/2019fall/b/b.go:3

FunctionfractionToDecimal

分数转小数 https://en.wikipedia.org/wiki/Repeating_decimal Period of decimal representation of 1/n, or 0 if 1/n terminates https://oeis.org/A051626 The per

copypasta/misc.go:570

FunctionfreqAlphabets

(s string)

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

FunctionfrequencySort

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/38/a/a.go:6

FunctionfriendRequests

github.com/EndlessCheng/codeforces-go

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

FunctionfrogPosition

(n int, edges [][]int, time int, target int)

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

FunctionfullJustify

LC 68

leetcode/main.go:356

FunctionfurthestBuilding

github.com/EndlessCheng/codeforces-go

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

FunctionfwtAND

(a []int, op int)

copypasta/math_fwt.go:40

FunctionfwtOR

* 快速沃尔什变换 fast Walsh–Hadamard transform, FWT, FWHT 在算法竞赛中，FWT 是用于解决对下标进行【位运算卷积】问题的方法一个常见的应用场景是对频率数组求 FWT 例如，求一个数组的三个元素的最大异或和，在值域不大的情况下，可以先求出该数组的频率数组

copypasta/math_fwt.go:28

FunctionfwtXOR

(a []int, op int)

copypasta/math_fwt.go:52

Functiongame

(a []int, b []int)

leetcode/season/2019fall/a/a.go:3

FunctiongameTheoryCollection

* 博弈论 Game Theory https://en.wikipedia.org/wiki/Game_theory 定义必胜状态为先手必胜的状态，必败状态为先手必败的状态定理 1：没有后继状态的状态是必败状态定理 2：一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态定理 3：一

copypasta/games.go:36

FunctiongaussJordanElimination

高斯消元 Gaussian elimination O(n^3) 列主元消去法求解 Ax=B，A 为方阵，返回解（无解或有无穷多组解） https://en.wikipedia.org/wiki/Gaussian_elimination https://en.wikipedia.org/wik

copypasta/math_matrix.go:250

FunctiongcdOfStrings

(s1 string, s2 string)

leetcode/weekly/139/a/a.go:5

FunctiongcdSort

(a []int)

leetcode/weekly/257/d/d.go:22

FunctiongenerateMaxNodes01TrieData

n 个 [0, 2^k) 范围内的数构成的 0-1 trie 至多可以有多少个节点？ n*(k-logn) + 2^(logn+1) - 1, 这里 logn = int(log_2(n)) 实际使用的时候，可以简单地用 n*(k+2-logn) 代替构造方法：先用不超过 n 的最大的 2 的幂次

copypasta/trie01.go:260

FunctiongenerateSentences

github.com/EndlessCheng/codeforces-go

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

FunctiongenerateTheString

(n int)

leetcode/weekly/179/a/a.go:5

Methodget

(key rbKeyType)

copypasta/red_black_tree.go:153

Methodget

()

copypasta/segment_tree.go:396

FunctiongetAllElements

(root1 *TreeNode, root2 *TreeNode)

leetcode/weekly/169/b/b.go:8

FunctiongetAverages

* O(n) 滑动窗口 */ github.com/EndlessCheng/codeforces-go

leetcode/weekly/269/b/b.go:7

FunctiongetBiggestThree

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/53/c/c.go:4

FunctiongetCircleCenter

三点确定一圆用三角形外心求解，见 circumcenter 给定半径和一条有向的弦，求该弦右侧的圆心（即 ao 在 ab 右侧）

copypasta/geometry.go:475

FunctiongetCollisionTimes

(a [][]int)

leetcode/weekly/230/d/d.go:74

FunctiongetConcatenation

github.com/EndlessCheng/codeforces-go

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

FunctiongetCoprimes

(a []int, edges [][]int)

leetcode/biweekly/46/d/d.go:20

FunctiongetDecimalValue

** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */

leetcode/weekly/167/a/a.go:15

FunctiongetDescentPeriods

* 分组循环将 $\textit{prices}$ 按照平滑下降的定义分成若干组。例如 $[3,2,1,4]$ 分为 $[3,2,1]$ 和 $[4]$ 两组。对于每一组的所有非空子数组，都是平滑下降的。设该组长度为 $m$，则该组的非空子数组个数为 $$ C_{m+1}^2 = \dfr

leetcode/weekly/272/c/c.go:21

FunctiongetDirections

* 一题双解：BFS / 最近公共祖先 #### 解法一：DFS + BFS 我们可以从起点出发，通过 BFS 找到终点，同时记录每个点的来源节点和方向，在找到终点后，顺着来源节点往回走，同时记录答案。由于要往父节点方向走，我们需要先通过一次 DFS 记录每个节点的父节点，这样就可以在 BF

leetcode/weekly/270/c/c.go:29

FunctiongetDirections2

(root *TreeNode, startValue, destValue int)

leetcode/weekly/270/c/c.go:65

FunctiongetDistances

O(n) 做法：哈希表 + 枚举相同元素 github.com/EndlessCheng/codeforces-go

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

FunctiongetFolderNames

(names []string)

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

FunctiongetHappyString

github.com/EndlessCheng/codeforces-go

leetcode/biweekly/24/c/c.go:4

FunctiongetIntersectionNode

LC 160

leetcode/main.go:885

FunctiongetKth

github.com/EndlessCheng/codeforces-go

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

FunctiongetLastMoment

(n int, left []int, right []int)

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

FunctiongetLengthOfOptimalCompression

github.com/EndlessCheng/codeforces-go

leetcode/weekly/199/d/d.go:22

FunctiongetLucky

Go 模拟 github.com/EndlessCheng/codeforces-go

leetcode/weekly/251/a/a.go:6

FunctiongetMaxGridHappiness

(n, m, c1, c2 int)

leetcode/weekly/215/d/d.go:49

FunctiongetMaxLen

github.com/EndlessCheng/codeforces-go

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

FunctiongetMaxLength

github.com/EndlessCheng/codeforces-go

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

← previous next →6,701–6,800 of 8,098, ranked by callers