-
单调队列
AcWing 154. 滑动窗口 原题链接给定一个大小为n≤106n≤106的数组。有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。您只能在窗口中看到k个数字。每次滑动窗口向右移动一个位置。以下是一个例子：该数组为[1 3 -1 -3 5 3 6 7]，k为3。 窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3...…
-
单调栈
单调栈将一些不可能成为结果，或者说是无用的数据清除出栈从而保证栈中元素的单调性AcWing 830. 单调栈 原题链接给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。输入格式第一行包含整数N，表示数列长度。第二行包含N个整数，表示整数数列。输出格式共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。数据范围1≤N≤1051≤N≤1051≤数列中元素≤1091≤数列中元素≤109输入样例：53 4 2 7 5输出样...…
-
区间合并
AcWing 803. 区间合并 原题链接给定 nn 个区间 [li,ri][li,ri]，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。输出合并完成后的区间个数。例如：[1,3]和[2,6]可以合并为一个区间[1,6]。输入格式第一行包含整数n。接下来n行，每行包含两个整数 l 和 r。输出格式共一行，包含一个整数，表示合并区间完成后的区间个数。数据范围1≤n≤1000001≤n≤100000,−109≤li≤ri≤109−109≤li≤ri≤109输入样例：51 22...…
-
前缀和
AcWing 795. 前缀和 原题链接输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。输入格式第一行包含两个整数n和m。第二行包含n个整数，表示整数数列。接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。输出格式共m行，每行输出一个询问的结果。数据范围1≤l≤r≤n1≤l≤r≤n,1≤n,m≤1000001≤n,m≤100000,−1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1...…
-
位运算
AcWing 801. 二进制中1的个数 原题链接给定一个长度为n的数列，请你求出数列中每个数的二进制表示中1的个数。输入格式第一行包含整数n。第二行包含n个整数，表示整个数列。输出格式共一行，包含n个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。数据范围1≤n≤1000001≤n≤100000,0≤数列中元素的值≤1090≤数列中元素的值≤109输入样例：51 2 3 4 5输出样例：1 1 2 1 2private static int countNumb...…
-
二分
二分两种模板版本1当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1，计算mid时不需要加1。int bsearch_1(int l, int r){ while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } return ...…
-
Trie树
Trie树用来快速存储 和 查找 字符串集合 的数据结构如何存储？son[N][26]: 每个节点最多有26条边 （单词只由小写字母组成）count[N]: 以当前节点为结尾的单词有多少个idx：下标用到了哪， 0 又是根节点 又是 空节点insert \ find 方法insert 一个字符串如何查找？一个一个字符去查找，到结尾的时候需要有标记count 数组就能 作为标记数据结构class Trie{ public TrieNode root; public Trie(){...…
-
KMP
AcWing 831. KMP字符串 原题链接给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。模板串P在模式串S中多次作为子串出现。求出模板串P在模式串S中所有出现的位置的起始下标。输入格式第一行输入整数N，表示字符串P的长度。第二行输入字符串P。第三行输入整数M，表示字符串S的长度。第四行输入字符串S。输出格式共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。数据范围1≤N≤1051≤N≤1051≤M≤1061≤M≤106...…
