> For the complete documentation index, see [llms.txt](https://qmmms.gitbook.io/note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://qmmms.gitbook.io/note/algorithm/qms07-you-hua-fang-fa.md).

# 优化方法

## 重新思考排序

**任务：**

给定一组数字段，连接成最小的数字。例如，给定{32，321，3214，0229，87}，我们可以连接成许多数字，例如32-321-3214-0229-87或0229-32-87-321-3214，关于这些片段的不同组合顺序，最小的数字是0229-321-3214-32-87。

**分析：**

朴素的贪心的思考方式应该是：首先给我两个数字段，例如32和321，我把它们正反组合排列起看哪个更小来排序，在这个例子中是 32-132，然后再拿到3214，在两个数中间的三个空之间插入排序，把3214插入进去。

众所周知，插入排序是很慢的，我们能不能使用快速排序来书写？这里我们遇到了一个困境：我们目前的方式是在每个空位插入一个新的数字段，然后看整个数字哪个最小。而传统的cmp函数方法要求我们随便拿出两个元素出来就要比大小。

我们重新审视排序过程：我们真的需要把整个数字拿出来比较吗？其实我们可以看作把前面和后面的数字固定不动，只比较要插入的这个数字段和我们要比较的数字段，即：

```cpp
// 或者使用Java的 Comparator
bool cmp(string a, string b){
    return a + b < b + a;
}
```

> 来源：PAT甲级 **1038 Recover the Smallest Number**

## 二分

**任务：**

你找到一本残缺很多但还是很厚的词典，想找到某个词或确认它不在，要求时间复杂度$O(log \ n)$

**分析：**

词典意味着**有序**

先翻到词典中间，与要找的词比较，让查找范围缩小一半

重复操作，一直到找到

**核心代码：**

```cpp
int l=1,r=MAX,mid=(l+r)>>1;//准备开始二分
while(l <= r){//终止条件
	//使用judge函数来判断当前猜测的答案是否可行
    if(judge(mid)){//如果可以的话 
        r = mid - 1;//改变右端点，看看再少一点是不是也可以
        mid = (l + r) >> 1;
    } else{
        l = mid + 1;//当前答案不可行，需要增大答案
        mid = (l + r) >> 1;
    }
}
cout << l << endl;//输出找到的答案
```

> 看到最大的最小（最小的最大），可能是二分或者二分答案

std::lower\_bound() 返回有序表里第一个大于等于给定值的指针或迭代器；

std::upper\_bound() 返回有序表里第一个大于给定值的指针或迭代器；

set / map / … （迭代器是不可减）用法：

```cpp
a.lower_bound(2)
```

vector （迭代器是可以减的）用法：

```cpp
lower_bound(a.begin(), a.end(), 2)
```

## 二维前缀和

**任务：**

给出一个 $n \* n$ 矩阵，从中找到最大加权矩形。

**分析：**

朴素的想法是对所有可能的矩形都做一遍遍历，但是要枚举所有矩形，时间复杂度已经达到 $O(n^4)$，再遍历矩形求权，时间复杂度最终达到 $O(n^6)$

前缀和的思想是记录数组中从开始到当前值的和，做一遍预处理，以应对之后对于和的询问。对于这个任务，可以让时间复杂度保留在 $O(n^4)$

二维前缀和记录左上角顶点为$(0,0)$，右下角顶点为$(i,j)$矩阵的权，递推式为：

$$
f\[i]\[j]=a\[i]\[j]+f\[i-1]\[j]+f\[i]\[j-1]-f\[i-1]\[j-1]
$$

**代码：**

> 例题：洛谷P1719 最大加权矩形
>
> <https://www.luogu.com.cn/problem/P1719>

```cpp
#include<iostream>
#include<cmath>
using namespace std;

int a[200][200];
int f[200][200];
int N, ans;

int main() {
	cin >> N;
	for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) cin >> a[i][j];
	for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) f[i][j] = a[i][j] + f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1];
	for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) for (int x = i; x <= N; ++x) for (int y = j; y <= N; ++y) ans = max(ans, f[x][y] - f[i - 1][y] - f[x][j - 1] + f[i - 1][j - 1]);
	cout << ans << endl;
	return 0;
}
```

## 差分

***

**任务：**

给定一个长度为 $n$ 的数列 ${a\_1,a\_2,\cdots,a\_n}$，每次可以选择一个区间$\[l,r]$，使这个区间内的数都加 $1$ 或者都减 $1$。问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。

**分析：**

差分的思想是记录原数组 $a$ 相邻元素的差，公式就是$s\[i]=a\[i]-a\[i-1]$

对于区间操作可以大幅加速时间，如果要对原数组的$\[l,r]$区间$+k$，可以修改$s\[l]+=k$，$s\[r+1]-=k$，再对差分数组 $s$ 做一遍前缀和，就可以得到区间操作后的原数组，把遍历的$O(n)$降到$O(1)$

对于这个任务，先将其做差分，然后所有正偏差、负偏差求和再取绝对值，设分别为$pos$，$neg$，易得：

$$
最少操作次数=min(pos, neg) + abs(pos - neg)
$$

$$
数列种类=1 + abs(pos - neg)
$$

**代码：**

> 例题：洛谷P4552 \[Poetize6] IncDec Sequence
>
> <https://www.luogu.com.cn/problem/P4552>

```cpp
#include <iostream>
#include <cmath>
using namespace std;

const int MAX = 1e5 + 5;
int a[MAX], s[MAX];
int N;
long long pos, neg;

int main() {
    cin >> N;
    for (int i = 1; i <= N; ++i) cin >> a[i];
    for (int i = 1; i <= N; ++i) s[i] = a[i] - a[i - 1];
    for (int i = 2; i <= N; ++i) {
        if (s[i] > 0) pos += s[i];
        else neg += -s[i];
    }
    cout << min(pos, neg) + abs(pos - neg) << endl;
    cout << 1 + abs(pos - neg) << endl;

    return 0;
}
```

## 单调队列

**任务：**

有一个长为 $n$ 的序列 $f$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

**分析：**

朴素的想法是每滑动一次就遍历一遍窗口中的所有元素，但这太慢了

考虑维护一个双向队列，它是单调的，最大的在前面，从前到后变小，目标是处理窗口中的最大值

在滑动后，需要处理一个新的值，位置为 $x$，需要把 $f\[x]$ 放到队列尾

因为目标是窗口中的最大值，所以位置在 $x$ 之前且比 $f\[x]$ 小的数都可以舍弃

更新后，队列最前端的数可能已经不在窗口内，检查并去除

这样，因为队列单调，则最前面的就是窗口内的最大值

**核心代码：**

> 例题：洛谷P1886 滑动窗口 /【模板】单调队列
>
> <https://www.luogu.com.cn/problem/P1886>

```cpp
deque<pair<int, int>> maxx;	//保存值和位置
int f[MAX];					//序列f

void process_max(int x) {//处理位置为x的数
	while (!maxx.empty() && maxx.back().first < f[x])maxx.pop_back();//之前且比f[x]小的数都可以舍弃
	maxx.push_back(make_pair(f[x], x));//把 f[x] 放到队列尾
	while (!maxx.empty() && maxx.front().second <= x - K)maxx.pop_front();//队列最前端的数可能已经不在窗口内
}
```

## 并查集

**任务：**

有一群人，有些人互相为亲戚，亲戚的亲戚也是亲戚，现在指定两个人，问他们是否是亲戚，要求预处理时间 $O(n)$ ，查询时间 $O(1)$

**分析：**

换句话讲，在一个图中，查询两点是否联通，要求预处理时间 $O(n)$ ，查询时间 $O(1)$

以亲戚为例，假设每个家族都有一个族长，象征这个家族，数组 $fa\[i]$ 代表 $i$ 的长辈（爸爸或爷爷或...或族长）

首先假设每个人都是族长

然后考虑一对父亲和儿子，那么父亲的长辈肯定是儿子的长辈

怎么找到族长？找爸爸的爸爸的爸爸......一直到族长，查询时压缩路径使时间逼近 $O(1)$

族长相同，肯定是亲戚

**代码：**

> 例题：洛谷P1551 亲戚
>
> <https://www.luogu.com.cn/problem/P1551>

```cpp
#include<iostream>
using namespace std;

int N, M, P;
int fa[5003];
int S, F;

int getfa(int n) {
    if(fa[n] == n) return n;//找到族长
    return fa[n] = getfa(fa[n]);//找爸爸的爸爸，压缩路径
}

void setfa(int son, int father) {
    fa[getfa(son)] = getfa(father);//父亲的长辈是儿子的长辈
}

int main() {
    cin >> N >> M >> P;
    for (int i = 1; i <= N; ++i) fa[i] = i;//假设每个人都是族长
    for (int i = 0; i < M; ++i) {
        cin >> S >> F;
        setfa(S, F);
    }
    for (int i = 0; i < P; ++i) {
        cin >> S >> F;
        if (getfa(S) == getfa(F)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}
```

**进阶**

并查集并不支持删点操作，我们可以把每个查询都存下来，反过来往里面添加点。[2021 RoboCom 世界机器人开发者大赛T4](https://blog.csdn.net/zzq1775840762/article/details/120941978)

## 异或

***

**基础：**

`^`的异或指的是二进制中，对应的对应二进制位相同时异或为零，相异时异或为一

* 规律一：大小相同的数字异或结果一定为0，而0与任何数字进行异或大小不会改变。比如3 ^ 3=0, 3 ^ 0=3
* 规律二：自反性。A^B^B=A
* 规律三：二进制的异或运算符合结合律和交换律

**任务：**

**非空** 整数数组 `nums` ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。实现线性时间复杂度，只使用常量额外空间的算法。

**代码：**

```cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
		int ans = nums[0];
         for (int i = 1; i < nums.size(); i++)ans = ans ^ nums[i];
         return ans;
    }
};
```

> 出处：力扣[136. 只出现一次的数字](https://leetcode.cn/problems/single-number/)

## 线段树

***

**任务：**

对一个数列的两种操作：

1. 将某区间每一个数加上 $k$，要求$O(log, n)$时间复杂度
2. 求出某区间的加和，要求$O(1)$时间复杂度（接近）

> 例题：洛谷P3372 【模板】线段树 1
>
> <https://www.luogu.com.cn/problem/P3372>

## 回溯

**任务：**

给你一个 **无重复元素** 的整数数组 `candidates` 和一个目标整数 `target` ，找出 `candidates` 中可以使数字和为目标数 `target` 的 所有 **不同组合** ，并以列表形式返回。你可以按 **任意顺序** 返回这些组合。

`candidates` 中的 **同一个** 数字可以 **无限制重复被选取** 。如果至少一个数字的被选数量不同，则两种组合是不同的。

```cpp
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int> > res;
        vector<int> path;
        dfs(candidates, 0, target, path, res);
        return res;
    }

    void dfs(vector<int>& candidates, int begin, int target, vector<int>& path, vector<vector<int> >& res){
        if(target == 0){
            res.push_back(path);
            return;
        }
        for(int i = begin; i < candidates.size(); i++){
            if(target - candidates[i] < 0){
                continue;
            }
            path.push_back(candidates[i]);
            dfs(candidates, i, target - candidates[i], path, res);
            path.pop_back();
        }
    }
};
```

> 出处：力扣39<https://leetcode.cn/problems/combination-sum/>

## 杂题思路

[按照权重的概率取随机采样](https://leetcode.cn/problems/random-pick-with-weight/submissions/553637346/)：现在有包含很多个样本数据的数组，现在对这些数进行多次有放回采样，但每个数都有自己的采样概率，这个概率存在另外一个数组里面，总概率是1，问怎么实现这个采样过程。思路是：设数组 *w* 的权重之和为 *total*。根据题目的要求，我们可以看成将 \[1,*total*] 范围内的所有整数分成 *n* 个部分。给出一个随机数，看落在哪个部分，优化考虑前缀和 + 二分查找。

***

一个文件有9998个数，对应\[1-10000]的范围，少了两个数。内存1k，怎么查找？先用公式n(n+1)/2算出1-10000的总和 ， 用公式n(n+1)(2n+1)/6算出1-10000的平方和，然后扫描那9998个数，每扫到一个就从平方和中减去这个数的平方，扫描一个就从总和中减去这个数。 知道两个数的和和平方和，解方程组即可得出这两个数

***

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。递归。

***

给你一个整数数组 `nums` 和一个整数 `k` ，请你统计并返回 *该数组中和为 `k` 的子数组的个数*

思路：前缀和 + 哈希表，键是前缀和，值是这个前缀和出现的次数。遍历 i，从哈希表中找 $$pre\[j-1]$$ 出现的次数

$$
pre\[j-1]==pre\[i]-k
$$

***

找出下一个排列：

* 例如，`arr = [1,2,3]` 的下一个排列是 `[1,3,2]` 。
* 类似地，`arr = [2,3,1]` 的下一个排列是 `[3,1,2]` 。
* 而 `arr = [3,2,1]` 的下一个排列是 `[1,2,3]` ，因为 `[3,2,1]` 不存在一个字典序更大的排列。

标准的 “下一个排列” 算法可以描述为：

1. **从后向前** 查找第一个 相邻升序 的元素对 (i,j)，满足 A\[i] < A\[j]。此时 \[j,end) 必然是降序
2. 在 \[j,end) **从后向前** 查找第一个满足 A\[i] < A\[k] 的 k。
3. 将 A\[i] 与 A\[k] 交换
4. 可以断定这时 \[j,end) 必然是降序，逆置 \[j,end)，使其升序
5. 如果在步骤 1 找不到符合的相邻元素对，说明当前 \[begin,end) 为一个降序顺序，则直接跳到步骤 4

![](/files/CJpCZ0PnURAVqSiTcBu6)

***

给你一个只包含 `'('` 和 `')'` 的字符串，找出最长有效（格式正确且连续）括号子串的长度。例如s = ")()())"的最长有效括号子串是 "()()"

[思路](https://leetcode.cn/problems/longest-valid-parentheses/solutions/314683/zui-chang-you-xiao-gua-hao-by-leetcode-solution/?envType=study-plan-v2\&envId=top-100-liked)：贪心，两次遍历

***

一个数组由两段有序序列拼接得来，在 O(log n) 时间内找到目标 target 返回下标

[思路](https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2\&envId=top-100-liked)：两次二分，第一次找到两段有序序列的分界点（l=1）