算法

杂项

滑动窗口与双指针

定长滑动窗口

将窗口长度固定，移动左右边界left和right来维护长度。
一些基础题：leetcode：定长字串中元音字母的最大数目等。
进阶题：存在重复元素|||等。

KMP算法

前缀函数

某一字符串的所有不包含自身的相同前后缀中长度最长的值，记为Π。例如：ATAATA的前缀值Π = 3.
对于一个字符数组，可以用数组Π[i]表示到第(i + 1)个字符形成的字符串的Π值。例如：对ATAATA的Π[] = [0, 0, 1, 1, 2, 3].
那么想要对于主串S判断其中是否存在字串s，只需要将s和S通过特殊的字符’#’连接起来，并计算Π数组，其中只要有数组值刚好等于s.len即可说明s存在于S中，否则不存在；注意：此处的特殊字符不一定一定是’#’，但一定是不存在于主串中的字符。
接下来就是对于Π数组的计算，由于对于第一个字符没有前后缀，因此其Π值刚好是0，而此后的字符stri，可以比较str[Π[i - 1]]与str[i]的关系。若相等，则说明，Π[i]就是在Π[i - 1]的基础上加1；反之，进一步去比较str[Π[Π[i - 1] - 1]] 与 str[i]的关系，直到前者内部的值小于0，便置为0，即此时不存在相同的前后缀；或者前者与str[i]，则在同样在前者的值的基础上加上1，其实也就是对于不满足的情况利用已分析的结果判断前后匹配的子串内部的更小的字串是否满足条件。

数据结构

前缀和

大体流程是通过数组存储某一个数组的前缀和sum[i] = array[0…i]，然后可能与哈希表等进行结合进而实现高效解体的方式，也可以称为动态规划的一种。

例题

一、

给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
示例 1：
输入：[“A”,”1”,”B”,”C”,”D”,”2”,”3”,”4”,”E”,”5”,”F”,”G”,”6”,”7”,”H”,”I”,”J”,”K”,”L”,”M”]
输出：[“A”,”1”,”B”,”C”,”D”,”2”,”3”,”4”,”E”,”5”,”F”,”G”,”6”,”7”]
示例 2：
输入：[“A”,”A”]
输出：[]
array.length <= 100000

首先这题由于只探讨字母和数字两种字符，因此，可以先将该数组进行转换，即字母转换为1、数字转换为-1.那么原题就转换为转换后的数组中子数组区间和为0(也就是区间中字母数字的数目刚好一样的情况)的长度最大且起始下标最靠左。
对于转换后的数组求前缀和函数sum，则sum[j] - sum[i] (j > i)就代表了区间[i + 1, j]的和，起始下标为i+1。
因此可以在遍历过程中用一个map存储前缀和与下标的键值对。
即在遍历数组的过程中：判断array[i]是否为字母或数字来更新前缀和sum[i]，若map中没有该前缀和，则直接存入，否则计算当前下标与map中存储下标的差值即为当前符合条件的区间长度，若比最大长度大则更新最大长度和起始下标。
当然除了使用hash，由于数据量并不是很大，还可以使用数组来存储对应的下标，开一个长度为2*n+1的数组sum，sum[i]代表前缀和为i-n的array下标。
对于字母和数字的判断方式可以使用骚的位运算来快速解决：字母的最小ASCII码为65>64，因此所有字母右移6位的第0位都是1，相反数字的话则都是0.进而建立如下映射关系：(c >> 6 & 1) * 2 - 1。
实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String[] findLongestSubarray(String[] array) {
    int n = array.length, begin = 1, end = 1, s = n;
    // 取2*n + 1为数组长度是为了用数组索引的方式来存储相对应的前缀和(因为有负数的存在)
    // 在该数组长度下，下标i的值代表前缀和为i-n的最小array下标
    var first = new int[n * 2 + 1];
    // 即前缀和为0的最左边的array下标为1也就是原来的0下标
    first[s] = 1; // 将array下标前移，即原来下标0的地方变为了现在的下标1
    for (int i = 2; i <= n + 1; ++i) {
        // 此处右移6位是因为字母的最小的ASCII码值为65刚好比64大，因此所有字母的第7位都为1
        // 则右移6位后字母与上1都是1，而数字与上1则是0，因此来通过快速的位运算来区分字母和数字
        s += (array[i - 2].charAt(0) >> 6 & 1) * 2 - 1;
        int j = first[s];
        if (j == 0)
            first[s] = i;
        else if (i - j > end - begin) {
            begin = j;
            end = i;
        }
    }
    var sub = new String[end - begin];
    // 因为此前将下标前移了，因此此处需要将begin减去1才是正确的下标
    System.arraycopy(array, begin - 1, sub, 0, sub.length);
    return sub;

}

二叉搜索树和平衡树

红黑树

合法红黑树有如下限制：

  1. 节点为红色或黑色
  2. NIL 节点（空叶子节点）为黑色
  3. 红色节点的子节点为黑色
  4. 从根节点到 NIL 节点的每条路径上的黑色节点数量相同
  5. 根节点必须为黑色

Java中的一些好用的数据结构

ConcurrentHashMap – 高并发键值存储

1
2
3
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put("a", 1);
concurrentMap.compute("a", (k, v) -> v + 1); // 原子更新

特点：线程安全、分段锁优化、支持原子操作
场景：高并发缓存、计数器、实时数据处理
性能：O(1) 读写（平均情况）

LinkedHashMap – 有序哈希映射

1
2
3
4
5
Map<String, Integer> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 100; // LRU 缓存
    }
};

特点：保留插入/访问顺序、支持 LRU 淘汰策略
场景：缓存系统、记录访问顺序
性能：O(1) 访问（与 HashMap 相同）

PriorityQueue – 优先级队列(可设计为小根堆)

1
2
3
4
Queue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority));
taskQueue.add(new Task("Urgent", 1));
taskQueue.add(new Task("Normal", 3));
Task next = taskQueue.poll(); // 获取最高优先级任务

特点：基于堆实现、自动排序
场景：任务调度、Dijkstra 算法、实时事件处理
性能：O(log n) 插入/删除，O(1) 获取最小值

CopyOnWriteArrayList – 写时复制列表

1
2
3
4
5
List<String> safeList = new CopyOnWriteArrayList<>();
// 读线程（无需锁）
safeList.forEach(System.out::println); 
// 写线程（复制新数组）
safeList.add("new element");

特点：读操作无锁、写操作复制新数组
场景：读多写少的监听器列表、配置管理
性能：O(1) 读，O(n) 写

ConcurrentSkipListMap – 跳表并发映射

1
2
3
4
ConcurrentNavigableMap<Integer, String> skipMap = new ConcurrentSkipListMap<>();
skipMap.put(3, "C");
skipMap.put(1, "A");
String first = skipMap.firstEntry().getValue(); // "A"

特点：线程安全的有序映射、支持范围查询
场景：实时排行榜、有序并发存储
性能：O(log n) 操作

EnumMap – 枚举优化映射

1
2
3
enum Day { MON, TUE, WED }
Map<Day, String> schedule = new EnumMap<>(Day.class);
schedule.put(Day.MON, "Meeting");

底层为数组、内存紧凑、速度快，适用于枚举类型映射、状态机

ArrayDeque – 双端队列

1
2
3
4
5
6
7
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 栈操作
stack.pop();

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(2); // 队列操作
queue.poll();

BFS算法、撤销操作栈、滑动窗口，O(1)头尾操作

ConcurrentLinkedQueue – 无锁并发队列

1
2
3
4
5
Queue<Message> messageQueue = new ConcurrentLinkedQueue<>();
// 生产者
messageQueue.offer(new Message()); 
// 消费者
Message msg = messageQueue.poll();

生产者-消费者模型、事件总线，O(1)出入队

动态规划

思想：

将待求解问题分解成若干子问题，分解得到的子问题往往不相互独立，即：有的子问题被重复计算过多次，因此动态规划大概就是在遍历的过程中边遍历边建立与维护一张“表”，并在依据题设条件建立好表的状态转移方程后，逐步完成”表”的建设，并将最终需要的答案填写在“表”中（一般是“表”的头或尾）。

个人感觉与递归的方式类似，只不过调用子递归函数时可以直接从“表”中读取，仅需要常数时间，而完全通过递归实现会重复计算很多一样的子递归函数，导致时间复杂度较大，因此，动态规划的效率会更高一点。

难点应该是“表”的状态转移方程的建立，一旦将状态方程建立下来，之后的实现就比较容易了。

例题：

1.最大子段和

问题描述：

  • 给定n个整数（可能是负数）组成的序列a[1], a[2], a[3], …, a[n]，求该序列的子段和，例如a[i]+a[i+1]+…+a[j]的最大值（1 <= i < j <= n）。
  • 当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为：max{0, a[i]+a[i+1]+…+a[j]}, 1<=i<=j<=n
  • 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20，即 20 = 11 + (-4) + 13。

求解：

​ 首先，由于题目要求的是序列a[1], a[2], a[3], …, a[n]的最大子段和，那其实可以将需要求解的目标一般化即去求解 a[1]+a[i+1]+…+a[j]的最大子段和，那么答案也就是j = n的时候，一般化的结果。

​ 接着，引入递归的思想，先假定数组ans[j] = max ( a[i]+a[i+1]+…+a[j])(1 <= i <= j, 1 <= j <= n)，即ans[j]表示以a[j]作为最后一个元素的最大子段和，此时**并不用在乎具体如何实现的，认为其存储的就是以a[j]作为最后一个元素的最大子段和**。再着，根据题意列出状态转移方程如下为：ans[j] = max(ans[j - 1] + a[j], a[j]) (2 <= j <= n), 也即 ans[j] = (j == 1) ? a[1] : ((ans[j - 1] > 0) ? (ans[j - 1] + a[j]) : a[j]);

这样就可以通过边遍历边建表实现快速的求解最大子段和。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
int n, x;
   scanf("%d", &n);
   int max = 0;
   for( int i = 1; i <= n; i++) {
       scanf("%d", &x);
       ans[i] = (i == 1) ? x : ((ans[i - 1] > 0) ? (ans[i - 1] + x) : x);

       if (ans[i] > max) {
           max = ans[i];
       }
   }

   printf("%d", max);

前缀DP的启示

  1. 不断试错寻找正确的状态定义
  2. 尝试以问题作为状态
  3. 尝试以i开始或以i结尾作为状态
  4. 对于严格只考虑前一个阶段对于当前阶段的影响的前缀dp，可以采用滚动数组的方式来优化，即只开一个行数为2的数组来存储当前阶段和上一阶段的状态

数学

快速幂

二进制取幂（平方法）。n个a相乘的计算量太大了，将其按照n的二进制表示拆成相应更小的幂任务。n=an……a2a1(2), a^n^ = a^((a1==1)?1:0)^ a^((a2==1)?2:0)^ * …… a^((an==1)?2*2……2:0^.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
long long binpower(long long a, long long b) {
    long long ans = 1;
    while(b > 0) {
        if (b & 1) ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}

//应用
//模意义下的取幂
long long binpower(long long a, long long b, long long m) {
    a %= m;
    long long ans = 1;
    while(b > 0) {
        if (b & 1) ans *= (a % m);
        a *= (a % m);
        b >>= 1;
    }
    return ans;
}

//计算斐波那契数
/*依据Fn = Fn-1 + Fn-2的关系式，构建一个{[1,1],[1,0]}前者在上方，后者在下方的2*2矩阵来表示从Fn、Fn+1到Fn+1、Fn+2的变换，即这个矩阵的n次幂的左上角的元素就是Fn，因此可以将矩阵乘法包装成一个函数，运用快速幂的思路，就可以快速计算出斐波那契数。
*/

数论

裴蜀定理（数论知识）

得名于艾蒂安·裴蜀（法）。

定理内容如下：∀a、b∈Z，以及gcd(a,b) = d(gcd为两数的最大公约数)，关于未知数x和y的线性不等式（裴蜀等式），对于∀x、y∈Z，一定有$d|ax + by$，特别地，一定存在整数x、y，使得$ax + by = d$成立。

一个重要推论是：a，b互质的充分必要条件是存在整数x、y使得$ax + by = 1$.

证明：

设$d = gcd(a，b)$，则$d|a$、$d|b$。则由|的性质，∀x，y∈Z，有$d|(ax + by)$。

设s为$ax + by$的最小正值，令$q = a / s$(这里的/是向下取整，类似于编程里的除法) ，则$r = a mod s = a - q(ax + by) = a(1 - qx) + b(-qy)$.

因此r也是a，b的线性组合，又因为$r = a mod s$，所以$0 <= r < s$.

又因为s为a，b线性组合的最小正值，可得$r = 0$。

所以$a mod s = 0$，所以$s|a$，同理：$s|b$，所以s为a与b的公约数，又因为d为a与b的最大公约数，所以$d >= s$.

因为$d|a$、$d|b$，且s为a与b的一个线性组合，所以$d|s$。

因为$d|s$且$s>0$,所以$d <= s$.

推广到n个整数间同理：

a1、a2、……an为n个整数，d为最大公约数，则存在整数x1、x2、……xn使得$x1*a1 + x2 * a2 + …… + xn * an = d$

例：

题目描述

现在把这个模型简化一下，第一个桶可装 a 升（即只有 a 升这一个刻度）， 第二个桶可装 b 升 ， 第三个桶无刻度。

你需要利用这两个有刻度的桶 ， 保证在操作结束后 ， 第三个桶恰有 c 升水

你只需要判断能不能完成这个操作即可。

运用裴蜀定理就可以很好的判断出是否能够完成。

进一步推广

对于自然数a、b和整数n，a与b互素，对于不定方程$ax + by = n$，若方程有自然数解x、y，称n可被a、b表示。

记$C = ab - a - b$，因为a、b互素，则C必为奇数（a、b不能同时为偶数，这样同a、b互素矛盾；若a、b一奇一偶，则ab为偶数减去一个奇数一个偶数为奇数；若a、b都属奇数，则ab为奇数，减去两个奇数仍为奇数）。
则有：对任意的整数n，n与C-n中有且仅有一个可以被a、b表示。即：可被表示的数与不可被表示的数在关于C的一半对称.0可被表示，C不可；负数不可，大于C的数可被表示。

证明：

因为a、b互素，因此原方程有整数解，设为：$x = x0 + bt; y = y0 - at;$其中t为整数，**取适当的t，s.t. y∈[0,a-1]**（这只要在y0的基础上加上或减去若干个a即可）。

先证：大于C的数都可被表示。

当n>C时：$ax = n - by>ab - a - b - by (y <= a - 1) >= ab - a- b - ab + b = -a $

所以x为非负整数，又因为y∈[0，a - 1]，所以x、y均为自然数，所以此时n可被表示。

再证：C不可被表示，进而证明n与C - n不可都被表示。

反证法：若$C = ab - a - b = ax + by$有非负整数解x、y，

则：$ab = a(x + 1) + b(y + 1)$

又因为a与b互素，所以$1 = (x+1)/b + (y + 1)/a$,因为x、y、a、b均为整数，所以$b|(x + 1)$且$a|(y+1)$,所以$b<=(x+1),a<=(y+1)$, $ab = a(x+1)+b(y+1)>=2ab$,所以$ab<=0$,与a与b为自然数矛盾，因此C不可被a、b表示。

最后证：若n不可被表示，则C-n可被表示。

若n不可被表示，由于已规定y>=0, 所以x为负数，所以：

$C-n = ab - a - b - ax - by = a(- x - 1) + (a-1-y)b$

因为x为负整数，所以$x - 1 >= 0$

又因为$y <= a - 1$，所以(a - 1 - y) >= 0，所以C - n可被表示。

得证。

欧拉函数

φ(n)，代表小于等于n且和n互质的数的个数，显然，当n为质数时，有φ(n) = n - 1

性质

费马小定理

定义：若p为质数，且a与p互质，则有a^p-1^ % p = 1.fan

推论：对任意整数a，有$a^p = a (mod p)$

证明：

设一个质数p，取一个不为p倍数的数a，对于{1,2,……,p-1}，

有(p-1)! % p = a * 2a * …… * (p-1)a % p

你或许会有这样的疑惑，会不会a、2a、……、(p-1)a中有两个数模p的余数相同呢？

不会的，兄弟，不会的。

我们假设ma与na(1 <= m < n < p)模p同余，则有ma % p = na % p，则有(n-m)a % p == 0， 又因为(n - m)与a均不能被p整除，因此(n - m)a不能被p整除，所以矛盾，假设不成立。

所以a、2a、……、(p-1)a中没有数模p相同，即它们对p的模数不过是1、2、……、(p-1)的再排列。

所以有(p - 1)! % p = (p - 1)! * a^(p-1)^ % p

显然，(p - 1)!不能被p整除，因此两边消去(p - 1)!，得到a^(p-1)^ % p = 1即费马小定理。