前言

这是我的算法笔记专栏的第一篇文章，因为我走的是java开发方向但算法题都是c++写的，我个人觉得c++写题更方便，所以为了防止大家跟着我的帖子入门不方便，特在此写了这篇介绍c++常用函数和常用技巧的帖子。

后续会详细地分章节介绍链表，字符串，动态规划，图，前缀和等常考知识点及其常见套路模板，同时会给出大量例题，新手小白肯定能快速跟上篮子哥的节奏

这个专栏给的例题的解法我不追求达到最优解法，而是我借鉴了lc的大量解法，加上自己的理解注释，追求尽可能的满足套路模板的解法，让大家尽可能的更容易的接受和理解。

觉得本贴有用的话欢迎点赞收藏订阅关注和评论！

我的算法专栏链接：https://www.nowcoder.com/creation/manager/columnDetail/0aqGq8

另外，我还有八股及话术专栏，架构专栏，含金量慢慢，集齐适合新手入门，欢迎大家订阅！链接如下：https://www.nowcoder.com/discuss/660899447991201792?sourceSSR=search

1.基本函数

1.substr()

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    string tmp = s.substr(1,2);//下标1开始2位长度子串
    cout<<tmp<<endl;
}
12345
23

2.字符串转整型stoi()

int main(){
    string s;
    cin>>s;
    int n = stoi(s);
    cout<<n;
}
12.7
输出12
12
输出12

3.字符串转整型stof()

int main() {
    string s;
    cin>>s;
    double d = stof(s);
    cout<<d;
}
"3.11"
3.11

4.数字转字符串to_string()

int n;
    cin>>n;
    string s;
    s += to_string(n);
    s+= "1";
    cout<<s;

5.lower_bound( )和upper_bound( )

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中，

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int INF=2*int(1e9)+10;
#define LL long long
int cmd(int a,int b){
	return a>b;
}
int main(){
	int num[6]={1,2,4,7,15,34}; 
	sort(num,num+6);                           //按从小到大排序 
	int pos1=lower_bound(num,num+6,7)-num;    //返回数组中第一个大于或等于被查数的值 
	int pos2=upper_bound(num,num+6,7)-num;    //返回数组中第一个大于被查数的值
	cout<<pos1<<" "<<num[pos1]<<endl;3 7
	cout<<pos2<<" "<<num[pos2]<<endl;4 15
	
} 

2.字符串根据","或' '划分

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    getline(cin,s);//这样才可以输入带空格的字符串
    stringstream ss(s);
    int k = 0;
    vector<string> strs;
    string tmp;
    while(getline(ss, tmp, ',')){
        strs.push_back(tmp);
    }
    for(int i=0;i<strs.size();i++){
        cout<<strs[i]<<endl;
    }
    cout<<strs.size()<<endl;
}
a,b,c
a
b
c
3

3.浮点型4舍去5入的指定精度函数

情况1：要求一定要精确到小数点后2位
int a = 1,b = 3;
double num = a*1.0/b;
std::cout << std::fixed << std::setprecision(2) << num << std::endl;
输入1，输出1.00
输入2/3,输出0.67
输入1/3,输出0.33

//情况2：四舍五入最多保留2位小数
int a = 2,b=3;
double res = a*1.0/b;
cout<<round(res*100)/100;
输入1，输出1
输入2/3,输出0.67
输入1/3,输出0.33

4.数状数组

1.什么是树状数组？

顾名思义就是一个结构为树形结构的数组，于二叉树的结构类似但又不同，它是在二叉树的结构上删除了一些中间节点，来看两幅图就明白了.

1.这是二叉树的结构

2.这是树状数组的结构

不难发现，树状数组相比于二叉树删除了一些节点，但是为什么要删除呢？这就和树状数组的一些性质(lowbit)有关了，不懂没关系，继续往下看.

2.树状数组可以解决什么问题呢？

可以解决大部分区间上面的修改以及查询的问题，例如1.单点修改，单点查询，2.区间修改，单点查询，3.区间查询，区间修改，换言之，线段树能解决的问题，树状数组大部分也可以，但是并不一定都能解决，因为线段树的扩展性比树状数组要强.

3.树状数组和线段树的区别在哪？

有人会问了既然线段树的问题能够用树状数组解决而且线段树还比树状数组扩展性强，那为什么不直接用线段树呢？问的很好，树状数组的作用就是为了简化线段树，举个例子：一个问题可以用线段树解决写代码半个小时，但是用树状数组只需要10分钟，那么你会选择哪一个算法呢?没错，基于某些简单的问题，我们没必要用到功能性强

4.树状数组的优点

优点：修改和查询操作复杂度于线段树一样都是logN,但是常数比线段树小，并且实现比线段树简单

缺点：扩展性弱，线段树能解决的问题，树状数组不一定能解决.

5.lowbit(x)运算

6.问题引入

8.例题

1.单点修改，区间查询

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 x
• 求出某区间每一个数的和

输入格式

第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 个整数，表示一个操作，具体如下：

• 1 x k 含义：将第 x 个数加上 k
• 2 x y 含义：输出区间 [x,y] 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例

输入 #1复制

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

输出 #1复制

14
16

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int n,m,tree[2000010]; // 定义全局变量n、m和数组tree
int lowbit(int k) // 定义lowbit函数，用于获取k的二进制表示中最低位的1的位置
{
    return k & -k;
}
void add(int x,int k) // 定义add函数，用于将k加到tree数组的第x个元素上，并更新后续元素的值
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=lowbit(x);
    }
}
int sum(int x) // 定义sum函数，用于计算tree数组中前x个元素的和
{
    int ans=0;
    while(x!=0)
    {
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main() // 主函数
{
    cin>>n>>m; // 输入n和m的值
    for(int i=1;i<=n;i++) // 循环读取n个数，并将它们加到tree数组中
    {
        int a;
        scanf("%d",&a);
        add(i,a);
    }
    for(int i=1;i<=m;i++) // 循环处理m次操作
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c); // 输入操作类型a和操作范围b、c
        if(a==1) // 如果操作类型为1，则将c加到tree数组的第b个元素上，并更新后续元素的值
            add(b,c);
        if(a==2) // 如果操作类型为2，则输出tree数组中第b个元素到第c个元素的和
            cout<<sum(c)-sum(b-1)<<endl;
    }
}

2.区间修改，单点查询

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 x；
2. 求出某一个数的值。

输入格式

第一行包含两个整数 N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含 N* 个用空格分隔的整数，其中第 i* 个数字表示数列第 i* 项的初始值。

接下来 M 行每行包含 2或 4个整数，表示一个操作，具体如下：

操作 11： 格式：1 x y k 含义：将区间 [x,y] 内每个数加上 k*；

操作 22： 格式：2 x 含义：输出第 x* 个数的值。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例

输入 #1复制

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

输出 #1复制

6
10

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int n,m; // 定义两个整数变量n和m
int input[500010]; // 定义一个长度为500010的整数数组input
int tree[500100]; // 定义一个长度为500100的整数数组tree
int lowbit(int x) // 定义一个函数lowbit，输入一个整数x，返回x的二进制表示中最低位的1所对应的值
{
    return x & -x;
}
void add(int x,int k) // 定义一个函数add，输入两个整数x和k，将k累加到tree数组中下标为x及之后的节点的值上
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=lowbit(x);
    }
}
int search(int x) // 定义一个函数search，输入一个整数x，返回tree数组中下标为x及其祖先节点的值的和
{
    int ans=0;
    while(x!=0)
    {
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main() // 主函数
{
    cin>>n>>m; // 输入两个整数n和m
    for(int i=1;i<=n;i++) // 循环读取n个整数并存入input数组
        cin>>input[i];
    for(int i=1;i<=m;i++) // 循环m次
    {
        int a;
        scanf("%d",&a); // 读取一个整数a
        if(a==1) // 如果a等于1
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z); // 读取三个整数x、y和z
            add(x,z); // 调用add函数，将z累加到tree数组中下标为x及其祖先节点的值上
            add(y+1,-z); // 调用add函数，将-z累加到tree数组中下标为y+1及其祖先节点的值上
        }
        if(a==2) // 如果a等于2
        {
            int x;
            scanf("%d",&x); // 读取一个整数x
            printf("%d\n",input[x]+search(x)); // 输出input数组中下标为x的值与tree数组中下标为x及其祖先节点的值的和
        }
    }
}

3.树状数组求逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ��>��a**i>a**j 且 �<�i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update:数据已加强。

输入格式

第一行，一个数 �n，表示序列中有 �n个数。

第二行 �n 个数，表示给定的序列。序列中每个数字不超过 109109。

输出格式

输出序列中逆序对的数目。

输入输出样例

输入 #1复制

6
5 4 2 6 3 1

输出 #1复制

11

分析:对于原序列，比当前位置数大的数前出现在序列中，就会构成逆序对,例如：5 3 2 1，5,3,2比1先出现且都比1大，那么此时就构成了3个逆序对数,那么我们可以对以及出现的数字进行标记，枚举序列中每一个位置的数，统计有多少比它大的数字以及出现，然后累加进答案即可,这就是一个单点修改+区间查询的操作，树状数组实现,不过需要注意的是这道题数字很大，需要离散化存储.

注意：这道题自定义排序参数cmp的实现，不能单纯的a.val<b.val,如果相等的话也要保证位置不变,不然贡献会增多，想想为什么？
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 5e5+10;
int t[Maxn]={0};//树状数组
typedef struct node{
   int val,ind;
}Node;
Node stu[Maxn];
int Rank[Maxn];
typedef long long ll;
int n;
int lowbit(int x){return x&(-x);}
/*单点修改*/
void add(int pos){
	for(int i=pos;i<=n;i+=lowbit(i)) t[i]+=1;
}
/*区间求和*/
int ask(int pos){
	int ans = 0;
	for(int i=pos;i;i-=lowbit(i)) ans+=t[i];
	return ans;
}
/*不能单纯的a.val<b.val,如果相等的话也要保证位置不变，不然贡献会增多*/
int cmp(Node a,Node b){
	if(a.val==b.val)
	return a.ind<b.ind;
	
	return a.val<b.val;
}
int main()
{
	ll ans = 0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>stu[i].val;
		stu[i].ind=i;
	}
	sort(stu+1,stu+n+1,cmp);
	/*离散化操作*/
	for(int i=1;i<=n;i++){
		Rank[stu[i].ind] = i;
	}
	for(int i=1;i<=n;i++){
		int pos = Rank[i];

		ans+=ask(n)-ask(pos);//digit+1~n中有多少数字已经出现就贡献多少逆序对数，累加到答案
			add(pos);//单点修改
	}
	cout<<ans;
	return 0;
}

5.快速幂

/**
 * 计算 (x^n) mod MOD 的值
 * @param x 底数
 * @param n 指数
 * @param MOD 模数
 * @return (x^n) mod MOD 的结果
 */
private static long powMod(long x, int n, int MOD) {
    long result = 1; // 初始化结果为1
    x = x % MOD; // 对底数取模，防止溢出
    while (n > 0) { // 当指数大于0时循环
        if ((n & 1) == 1) { // 如果指数是奇数
            result = (result * x) % MOD; // 将结果乘以底数并对模数取模
        }
        x = (x * x) % MOD; // 将底数平方并对模数取模
        n >>= 1; // 将指数右移一位，相当于除以2
    }
    return result; // 返回最终结果
}

6.求最小公约数和最大公倍数模板

int gcd(int a,int b){//求最大公约数
    return b == 0 ? a : gcd(b,a%b);
}
int lcm(int a,int b){//求最小公倍数
    return a * b / gcd(a,b);
}

7.怎么才能使用unordered_set<pair<int, int>>?

//自定义哈希函数，元素类型为 pair<T1, T2> a(X1, X2);
struct pair_hash
{
    template <class T1, class T2>
    size_t operator () (pair<T1, T2> const &pair) const
    {
        size_t h1 = hash<T1>()(pair.first); //用默认的 hash 处理 pair 中的第一个数据 X1
        size_t h2 = hash<T2>()(pair.second);//用默认的 hash 处理 pair 中的第二个数据 X2
        return h1 ^ h2;
    }
};
unordered_set<pair<int, int>, pair_hash> hash1;

8.自定义排序

//sort自定义排序
sort(res.begin(),res.end(),[&](const auto& a,const auto& b) {
       return a > b;//倒序排列
   });

//重写仿函数
struct cmp{
    bool operator()(const int&a,const int& b){
        return a>b;//升序
    }
};
int main() {
    priority_queue<int,vector<int>,cmp> res;

9.质数筛

#include <iostream>
#include <vector>
using namespace std;

const int N = 10000005;
int primes[N]; // 存储质数的数组
bool st[N]; // 标记数组，用于判断一个数是否被筛掉
int cnt = 0; // 质数计数器

// 欧拉筛函数，筛选出小于等于n的所有质数
void ola(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) { // 如果i没有被筛掉，说明它是质数
            primes[cnt++] = i; // 将i加入质数数组，并更新质数计数器
        }
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true; // 将i的倍数标记为非质数
            if (i % primes[j] == 0) break; // 如果i能被某个质数整除，跳出循环
        }
    }
}

int main() {
    int a;
    cin >> a; // 输入一个整数a
    ola(a); // 调用欧拉筛函数，筛选出小于等于a的所有质数
    cout << cnt << endl; // 输出质数个数
    return 0;
}

10.单调栈

单调栈:每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

什么时候用单调栈？

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

单调栈的意义：用 O(n) 复杂度,正序放入单调栈可以找元素右边最近的较大/小值，倒序放入单调栈可以找元素左边最近的较大/小值

例题(每日温度)

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        //什么时候用单调栈？
        //通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)
        //在使用单调栈的时候首先要明确如下几点：
        //单调栈里存放的元素是什么？
        //单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。
        //单调栈里元素是递增呢？ 还是递减呢？
        //注意以下讲解中，顺序的描述为 从栈头到栈底的顺序，因为单纯的说从左到右或者从前到后，不说栈头朝哪个方向的话，大家一定比较懵。
        //这里我们要使用递增循序（再强调一下是指从栈头到栈底的顺序），
        //因为只有递增的时候，栈里要加入一个元素i的时候，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。
        //即：如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。

        //该题是找一个元素右边第一个较大的元素，要建个存放元素下标，从栈头到栈尾递增的单调栈
        int n = temperatures.size();
        vector<int> res(n,0);
        //注意，该栈装的是元素的下标i
        //栈为空，直接入栈第一个元素的下标0
        stack<int> stack;
        stack.push(0);
        for(int i=1;i<n;i++){
            if(temperatures[i] <= temperatures[stack.top()]){
                stack.push(i);//当前温度不大于栈顶温度，直接入栈
            }else{
                while(!stack.empty() && temperatures[i] > temperatures[stack.top()]){
                    //这里不能写成stack.empty() != 0
                    //注意：栈要删除元素的前提是栈不能为空，所以要把!stack.isEmpty放while循环的最前面
                    res[stack.top()] = i - stack.top();
                    stack.pop();
                }
                stack.push(i);//最后新元素还是要入栈
            }
        }
        return res;//如果res没有更新，说明这个元素右边没有更大的了，也就是为0。
    }
};

11.差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

航班预定统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

#include<vector>
using namespace std;
class Solution {
public:
    //差分数组模板
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> book(n,0);//原始数组
        vector<int> diff(n,0);//差分数组
        //注意题中元素从0开始
        for(auto& booking : bookings){
            //让区间[booking[0]-1,booking[1]-1]同时加booking[2]
            diff[booking[0]-1]+=booking[2];
            if(booking[1]<diff.size()){
                diff[booking[1]]-=booking[2];
            }

        }
        for(int i=0;i<n;i++){
            if(i == 0){//可能对原始数组的第一个元素也做了修改
                book[0] = diff[0];
            }
            if(i>0){
                book[i] = book[i-1] + diff[i];
            }
        }
        return book;
    }
};

12.前缀和

矩阵区域和

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

• i - k <= r <= i + k,
• j - k <= c <= j + k 且
• (r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> preSum;
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(),n = mat[0].size();
        preSum = vector<vector<int>>(m+1,vector<int>(n+1,0));
        //初始化前缀和矩阵
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                //[0,0,i-1,j-1] = [0,0,i-2,j-1]+[0,0,i-1,j-2]-[0,0,i-2,j-2]+点[i-1][j-1]
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        vector<vector<int>> res(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int x1 = i-k,y1 = j-k,x2 = i+k,y2 = j+k;
                //干脆利落的判断是否越界的方式
                if(x1<0)x1=0;
                if(y1<0)y1=0;
                if(x2>=m)x2 =m-1;
                if(y2>=n)y2=n-1;
                res[i][j] = sumRegion(x1,y1,x2,y2);
            }
        }
        return res;
    }
    // 计算子矩阵matrix的 [x1, y1, x2, y2] 的元素和
    int sumRegion(int x1, int y1, int x2, int y2) {
        // 目标矩阵之和由四个相邻矩阵运算获得
        //目标矩阵=[0,0,x2,y2]-[0,0,x1-1,y2]-[0,0,x2,y1-1]+[0,0,x1-1,y1-1]
        return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] + preSum[x1][y1];
    }

};

13.备忘录

记录数组某个数左边或右边包括自己最大的数

14.并查集

注意：并查集只能判断无向图是否有环和是否出现有向边组成的树增加一条边的情况，不能判断有向图是否有环，只有拓扑排序能判断有向图是否有环。如果是判断无向图，则join(u,v)和join(v,u)差不多效果。

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
	if(u == father[u])retrun u;
    return  father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

寻找图中是否存在路径

有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。

给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2 
- 0 → 2

#include<vector>
using namespace std;
#include<queue>
class Solution {
private:
    int n = 200005; // 题目条件1 <= n <= 2 * 10^5,n取比最大值稍大的值
    vector<int> father = vector<int> (n, 0);//并查集father
    // 并查集初始化
    void init() {
        for (int i = 0; i < n; ++i) { father[i] = i;
        }
    }
    // 并查集里寻根的过程
    int find(int u) {
        if (u == father[u]){
            return u;
        }
        father[u] = find(father[u]);
        return  father[u];// 路径压缩
    }
    // 判断 u 和 v是否找到同一个根
    bool isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
    // 将v->u 这条边加入并查集
    void join(int u, int v) {
        u = find(u); // 寻找u的根
        v = find(v); // 寻找v的根
        if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        father[v] = u;//若根不同，则u的根变成v的根的根
    }
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        init();//初始化并查集
        //把每条边加入并查集
        for (int i = 0; i < edges.size(); i++) {
            join(edges[i][0], edges[i][1]);
        }
        //判断并查集中的2点是否同根，即判断2点是否可以相连
        return isSame(source, destination);
    }
};

15.中心扩散法（回文串问题）

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            // 以 s[i] 为中心的最长回文子串
            String s1 = palindrome(s, i, i);
            // 以 s[i] 和 s[i+1] 为中心的最长回文子串
            String s2 = palindrome(s, i, i + 1);
            // res = longest(res, s1, s2)
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    String palindrome(String s, int l, int r) {
        // 防止索引越界
        while (l >= 0 && r < s.length()
                && s.charAt(l) == s.charAt(r)) {
            // 向两边展开
            l--;
            r++;
        }
        // 返回以 s[l] 和 s[r] 为中心的最长回文串
        return s.substring(l + 1, r);
    }
}