蓝桥杯加训

1.两只塔姆沃斯牛（模拟）

在这里插入图片描述
在这里插入图片描述
思路：人和牛都记录三个数据，当前坐标和走的方向，如果人和牛的坐标和方向走重复了，那就说明一直在绕圈圈，无解

#include<iostream>
using namespace std;
const int N = 15;
char g[N][N];
int b[N][N][N][N][N][N];
int tx, ty, ex, ey;
struct Point{
	int x, y, fang;
}peo, cow;
int ok;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void ff(){
	int px = peo.x + dx[peo.fang];
	int py = peo.y + dy[peo.fang];
	int cx = cow.x + dx[cow.fang];
	int cy = cow.y + dy[cow.fang];
	if(g[px][py] != '*'){
		peo.x = px;
		peo.y = py;
	}else{
		peo.fang = (peo.fang + 1) % 4;
	}
	if(g[cx][cy] != '*'){
		cow.x = cx;
		cow.y = cy;
	}else{
		cow.fang = (cow.fang + 1) % 4;
	}
}

int main(){
	for(int i = 0; i <= 11; i++){
		for(int j = 0; j <= 11; j++){
			g[i][j] = '*';
		}
	}
	for(int i = 1; i <= 10; i++){
		for(int j = 1; j <= 10; j++){
			cin>>g[i][j];
			if(g[i][j] == 'F'){
				tx = i;
				ty = j;
			}
			if(g[i][j] == 'C'){
				ex = i;
				ey = j;
			}
		}
	}
//	for(int i = 0; i <= 11; i++){
//		for(int j = 0; j <= 11; j++){
//			cout<<g[i][j];
//		}
//		cout<<endl;
//	}
	peo = {tx, ty, 0};
	cow = {ex, ey, 0};
	int cnt = 0, ok1 = 0, ok2 = 0;
	while(!(peo.x == cow.x && peo.y == cow.y)){
		cnt++;
		ff();
		if(b[peo.x][peo.y][peo.fang][cow.x][cow.y][cow.fang] == 1){
			ok = 1;
			break;
		}
		b[peo.x][peo.y][peo.fang][cow.x][cow.y][cow.fang] = 1;
	}
	if(ok == 1) cout<<0;
	else cout<<cnt;
	return 0;
}

2.宇宙总统（排序）

在这里插入图片描述
思路：自定义排序，按照从大到小升序排序

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25;
pair<string, int> q[N];
int n;

bool cmp(const pair<string, int>& pp, const pair<string, int>& qq){
	if(pp.first.size() != qq.first.size()) return pp.first.size() > qq.first.size();
	else{
		int m = pp.first.size();
		for(int i = 0; i < m; i++){
			if(pp.first[i] != qq.first[i]){
				return pp.first[i] > qq.first[i];
			}
		}
	} 
}

int main(){
	cin>>n;
	string x;
	for(int i = 1; i <= n; i++){
		cin>>x;
		q[i] = {x, i};
	}
	sort(q + 1, q + n + 1, cmp);
	cout<<q[1].second<<endl;
	cout<<q[1].first;
	return 0;
}

3.回文质数（回文数、质数）

在这里插入图片描述
思路：先判断回文数，再判断质数，最大的回文质数是 9989899

#include<iostream>
#include<cstring>
using namespace std;
int a, b;


// 检查是否回文 
int check1(int x){
	int res = 0, t = x;
	while(t){
		res = res * 10 + t % 10;
		t /= 10;
	}
	return res == x;
}

// 检查是否质数 
int check2(int x){
	if(x < 2) return 0;
	for(int i = 2; i <= x / i; i++){
		if(x % i == 0){
			return 0;
		}
	}
	return 1;
}

int main(){
	cin>>a>>b;
	for(int i = a; i <= b; i++){
		// 最大的回文质数是 9989899 
		if(i > 10000000) break;
		if(check1(i)){
			//cout<<i<<endl;
			if(check2(i)){
				cout<<i<<endl;
			}
		}
	}
	return 0;
}

4.海底高铁（前缀和、差分）

在这里插入图片描述
在这里插入图片描述
思路：如上，差分标记两个起始地点，然后前缀和求出每个地方需要走多少次，贪心求出买票还是买卡划算

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int p[N], s[N];
int n, m;

int main(){
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		cin>>p[i];
		if(i > 0){
			if(p[i] > p[i - 1]){
				s[p[i - 1]]++;
				s[p[i]]--;
			}else{
				s[p[i]]++;
				s[p[i - 1]]--;
			}
		}
	}
	// 差分数组累加，前缀和
	for(int i = 1; i <= n; i++){
		s[i] += s[i - 1];
	}
	int a, b, c;
	long long sum = 0;
	for(int i = 1; i < n; i++){
		cin>>a>>b>>c;
		sum += min(1ll * a * s[i], 1ll * b * s[i] + c);
	}
	if(m < 2) cout<<0;
	else cout<<sum;
	return 0;
}

5.KMP（kmp）

在这里插入图片描述

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
int ne[N], f[N];
char s[N], p[N];
int n, m;

void kmp(){
	ne[1] = 0;
	int j = 0;
	for(int i = 2; i <= m; i++){
		while(j > 0 && p[i] != p[j + 1]) j = ne[j];
		if(p[i] == p[j + 1]) j++;
		ne[i] = j;
	}
	j = 0;
	for(int i = 1; i <= n; i++){
		while(j > 0 && s[i] != p[j + 1]) j = ne[j];
		if(s[i] == p[j + 1]) j++;
		f[i] = j;
	}
	for(int i = 1; i <= n; i++){
		if(f[i] == m){
			cout<<(i - m + 1)<<endl;
		}
	}
	for(int i = 1; i <= m; i++){
		cout<<ne[i]<<" ";
	}
}

int main(){
	cin>>(s + 1)>>(p + 1);
	n = strlen(s + 1);
	m = strlen(p + 1);
	kmp();
	return 0;
}

6.直播获奖（桶排序）

在这里插入图片描述

#include<iostream>
using namespace std;
const int N = 610;
int t[N];
int n, w;

int main(){
	cin>>n>>w;
	int x;
	for(int i = 1; i <= n; i++){
		cin>>x;
		t[x]++;
		int sum = 0;
		for(int j = 600; j >= 0; j--){
			sum += t[j];
			if(sum >= max(1, i * w / 100)){
				cout<<j<<" ";
				break;
			}
		}
	}
	return 0;
}

7.最大子段和（递推）

在这里插入图片描述
思路：从开头一直累加，如果小于 0，那就重新开始累加，取最大值

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int n; 

int main(){
	cin>>n;
	int x, res = 0, ans = -1e9;
	for(int i = 0; i < n; i++){
		cin>>x;
		res += x;
		ans = max(ans, res);
		if(res < 0) res = 0;
	}
	cout<<ans;
	return 0;
}

8.采药（01背包）

在这里插入图片描述
思路：每个物品只能使用一次，时间就是体积

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000 + 10;
int f[N], v[N], w[N];
int n, m; 

int main(){
	cin>>m>>n;
	for(int i = 1; i <= n; i++){
		cin>>v[i]>>w[i];
	}
	for(int i = 1; i <= n; i++){
		for(int j = m; j >= v[i]; j--){
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		} 
	}
	cout<<f[m];
	return 0;
}

9.疯狂的采药（完全背包）

在这里插入图片描述
思路：时间就是体积，完全背包，注意数据范围，背包体积 1e7，最大价值是 1e7 * 1e4 = 1e11

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e7 + 10;
long long f[N], v[N], w[N];
int n, m; 

int main(){
	cin>>m>>n;
	for(int i = 1; i <= n; i++){
		cin>>v[i]>>w[i];
	}
	for(int i = 1; i <= n; i++){
		for(int j = v[i]; j <= m; j++){
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		} 
	}
	cout<<f[m];
	return 0;
}

10.最大食物链计数（拓扑排序）

在这里插入图片描述

思路：求的是路径条数，只有出度为 0 的时候才累加答案

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 5e3 + 10, mod = 80112002;
vector<int> g[N];
int ru[N], chu[N];
int siz[N];
int n, m; 
int cnt;

void ff(){
	queue<int> q;
	for(int i = 1; i <= n; i++){
		if(ru[i] == 0){
			siz[i] = 1;
			q.push(i);
		} 
	}
	while(q.size()){
		int it = q.front();
		q.pop();
		for(int i : g[it]){
			siz[i] = (siz[i] + siz[it]) % mod;
			ru[i]--;
			if(ru[i] == 0){
				if(chu[i] == 0){
					cnt = (cnt + siz[i]) % mod;
				}else{
					q.push(i);
				}
			}
		}
	}
}

int main(){
	cin>>n>>m;
	int a, b;
	for(int i = 1; i <= m; i++){
		cin>>a>>b;
		g[a].push_back(b);
		chu[a]++;
		ru[b]++;
	}
	ff();
	cout<<cnt;
	return 0;
}

11.装箱问题（01背包）

在这里插入图片描述
思路：01 背包，求最大能装下的体积，体积也是价值

#include<iostream>
using namespace std;
const int N = 2e4 + 10;
int f[N], v[N];
int n, m;

int main(){
	cin>>m>>n;
	for(int i = 1; i <= n; i++){
		cin>>v[i];
	}
	for(int i = 1; i <= n; i++){
		for(int j = m; j >= v[i]; j--){
			f[j] = max(f[j], f[j - v[i]] + v[i]);
		}
	}
	cout<<(m - f[m]);
	return 0;
}

12.高维正方体（快速幂、逆元）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
思路：f[i][j]：i 维立方体中 j 维元素个数

#include<iostream>
using namespace std;
const int N = 1e5 + 10, mod = 1e9 + 7;
int f[N];

int qm(int a, int b){
	int res = 1 % mod;
	while(b){
		if(b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return res;
}

int main(){
	int a, b;
	cin>>a>>b;
	f[0] = qm(2, a);
	for(int j = 1; j <= b; j++){
		f[j] = ((1ll * f[j - 1] * (a + 1 - j)) % mod * qm(2 * j, mod - 2) % mod) % mod;
	}
	cout<<f[b];
	return 0;
}

13.编码（计算组合数）

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

#include<iostream>
using namespace std;
const int N = 30;
int f[N][N];

void init(){
	for(int i = 1; i < N; i++){
		for(int j = 0; j <= i; j++){
			if(j == 0) f[i][j] = 1;
			else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
		}
	}
}

int main(){
	init();
	string s;
	cin>>s;
	int n = s.size();
	for(int i = 0; i < n - 1; i++){
		if(s[i] >= s[i + 1]){
			cout<<0;
			return 0;
		}
	}
	int ans = 0;
	// 加上位数比当前小的 
	for(int i = 1; i < n; i++) ans += f[26][i];
	
	//枚举当前每一位可以有多少种情况 
	for(int i = 0; i < n; i++){
		int m = s[i] - 'a';
		for(int j = 1; j <= m; j++){
			ans += f[26 - j][n - i - 1];
		}
	} 
	
	// 加上自身 
	ans++;
	cout<<ans;
	return 0;
}

14.高低位交换（位运算）

在这里插入图片描述
思路：无符号整型 unsigned int 是 32 位整型，越界就等于取模了

#include<iostream>
using namespace std;

int main(){
	unsigned int n;
	cin>>n;
	unsigned int res = (n >> 16) + (n << 16);
	cout<<res;
	return 0;
}

15.合并果子（贪心）

在这里插入图片描述

思路：每次取出两个最小的果子合并

#include<iostream>
#include<queue>
using namespace std;
const int N = 1e4 + 10;
priority_queue<int, vector<int>, greater<int>> q;
int n;

int main(){
	cin>>n;
	int x;
	for(int i = 0; i < n; i++){
		cin>>x;
		q.push(x);
	}
	long long sum = 0;
	while(q.size() > 1){
		int a = q.top();
		q.pop();
		int b = q.top();
		q.pop();
		sum += a + b;
		q.push(a + b);
	}
	cout<<sum;
	return 0;
}

16.陶陶摘苹果（升级版）（贪心）

在这里插入图片描述
思路：按照每个苹果所需要的力气升序排序，一个一个摘

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
pair<int, int> q[N];
int n, m, a, b;

bool cmp(const pair<int, int>& pp, const pair<int, int>& qq){
	if(pp.second != qq.second) return pp.second < qq.second;
	else return pp.first < qq.first; 
}

int main(){
	cin>>n>>m;
	cin>>a>>b;
	int x, y;
	for(int i = 1; i <= n; i++){
		cin>>x>>y;
		q[i] = {x, y};
	}
	sort(q + 1, q + n + 1, cmp);
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(m - q[i].second >= 0 && a + b >= q[i].first){
			cnt++;
			m -= q[i].second;
		}
	}
	cout<<cnt;
	return 0;
}

17.一元三次方程求解（二分）

在这里插入图片描述
思路：如果有一个区间左右端点相乘小于等于 0，那么这个区间存在一个零点

#include<iostream>
#include<algorithm>
using namespace std;
double a, b, c, d;

double check(double x){
	double sum = a * x * x * x + b * x * x + c * x + d;
	return sum;
}

int main(){
	cin>>a>>b>>c>>d;
	int f = 0;
	for(int i = -100; i <= 100; i++){
		if(f == 3) break;
		double l = i - 0.5, r = i + 0.5;
		if(check(l) * check(r) <= 0){
			if(check(l) >= 0){
				while(l + 0.00001 < r){
					double mid = (l + r) / 2;
					if(check(mid) > 0) l = mid;
					else r = mid; 
				}
			}else if(check(l) < 0){
				while(l + 0.00001 < r){
					double mid = (l + r) / 2;
					if(check(mid) < 0) l = mid;
					else r = mid; 
				}
			}
			f++;
			printf("%.2lf ", r);
		}
	}
	return 0;
}

18.八皇后（dfs）

在这里插入图片描述
思路：dfs 一个参数，维护每行，然后三个数组维护每一列、正对角线、斜对角线

#include<iostream>
#include<queue>
using namespace std;
const int N = 30;
int a[N];
int vis1[N], vis2[N], vis3[N];
int n;
int cnt;

void dfs(int u){
	if(u > n){
		cnt++;
		if(cnt < 4){
			for(int i = 1; i <= n; i++){
				cout<<a[i]<<" ";
			}
			cout<<endl;
		}
		return;
	}
	for(int i = 1; i <= n; i++){
		if(!vis1[i] && !vis2[u + i] && !vis3[i - u + n]){
			vis1[i] = vis2[u + i] = vis3[i - u + n] = 1;
			a[u] = i;
			dfs(u + 1);
			vis1[i] = vis2[u + i] = vis3[i - u + n] = 0;
		}
	}
}

int main(){
	cin>>n;
	dfs(1);
	cout<<cnt;
	return 0;
}

19.单词接龙（dfs）

在这里插入图片描述
思路：dfs 维护当前拼接成功的单词，用 map 记录每个单词用了几次

#include<iostream>
#include<map>
using namespace std;
const int N = 30;
map<string, int> mp;
string s[N];
int n;
int ans;

string check(string s1, string s2){
	int len = s1.size();
	for(int i = 1; i < len; i++){
		if(s1.substr(len - i) == s2.substr(0, i)){
			string t = s1 + s2.substr(i);
			return t;
		}
	}
	return "加训";
}

void dfs(string ss){
	if(ss.size() > ans) ans = ss.size();
	for(int i = 1; i <= n; i++){
		if(mp[s[i]] == 2) continue;
		string t = check(ss, s[i]);
		if(t != "加训"){
			mp[s[i]]++;
			dfs(t);
			mp[s[i]]--;
		}
	} 
}

int main(){
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>s[i];
	}
	char c;
	cin>>c;
	for(int i = 1; i <= n; i++){
		if(s[i][0] == c){
			mp[s[i]]++;
			dfs(s[i]);
			mp[s[i]]--;
		}
	}
	cout<<ans;
	return 0;
}

20.约瑟夫问题（取模）

在这里插入图片描述
思路：vector 下标从 0 开始，每次前进 m - 1 个位置，到第 n 个位置取模后会变成 0，正好符合条件

#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
int n, m;

int main(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++) v.push_back(i);
	int cnt = 0;
	while(v.size()){
		cnt = (cnt + m - 1) % v.size();
		cout<<v[cnt]<<" ";
		v.erase(v.begin() + cnt);
	}
	return 0;
}

21.队列安排（模拟链表）

在这里插入图片描述
思路：结构体模拟双链表

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m;
struct Point{
	int l, r; // 左边和右边的同学 
	int vis; // 标记是否删除 
}q[N];

void add(int i, int j, int f){
	// j 插到 i 的右边 
	if(f == 1){
		q[j].r = q[i].r;
		q[j].l = i;
		q[i].r = j;
		q[q[j].r].l = j;
	}else{
		// j 插到 i 的左边 
		q[j].r = i;
		q[j].l = q[i].l;
		q[i].l = j;
		q[q[j].l].r = j;
	}
}

void init(){
	q[0].r = 0, q[0].l = 0;
	add(0, 1, 1); // 1 插到 0 的右 
}

int main(){
	cin>>n;
	int k, p;
	for(int i = 2; i <= n; i++){
		cin>>k>>p;
		add(k, i, p);
	}
	cin>>m;
	int x;
	for(int i = 1; i <= m; i++){
		cin>>x;
		q[x].vis = 1;
	}
	for(int i = q[0].r; i > 0; i = q[i].r){
		if(!q[i].vis) cout<<i<<" ";
	}
	return 0;
}

22.验证栈序列（模拟栈）

在这里插入图片描述
思路：按入栈顺序入栈，如果栈顶和当前 b 数组元素相等，那就弹出，如果入栈结束，栈不为空，说明 b 不是出栈序列

#include<iostream>
#include<stack>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, q;

int main(){
	cin>>q;
	while(q--){
		cin>>n;
		for(int i = 0; i < n; i++) cin>>a[i];
		for(int i = 0; i < n; i++) cin>>b[i];
		stack<int> q;
		int cnt = 0;
		for(int i = 0; i < n; i++){
			q.push(a[i]);
			while(q.top() == b[cnt]){
				q.pop();
				cnt++;
				if(q.empty()) break;
			}
		}
		if(q.empty()) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

23.马的遍历（bfs）

在这里插入图片描述

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 410;
int g[N][N], vis[N][N], dis[N][N];
int n, m;

int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};

void bfs(int x, int y){
	queue<pair<int, int>> q;
	vis[x][y] = 1;
	dis[x][y] = 0;
	q.push({x, y});
	while(q.size()){
		auto it = q.front();
		q.pop();
		for(int i = 0; i < 8; i++){
			int a = it.first + dx[i], b = it.second + dy[i];
			if(a < 1 || a > n || b < 1 || b > m) continue;
			if(vis[a][b]) continue;
			vis[a][b] = 1;
			dis[a][b] = dis[it.first][it.second] + 1;
			q.push({a, b});
		}
	}
}

int main(){
	memset(dis, -1, sizeof(dis));
	int x, y;
	cin>>n>>m>>x>>y;
	bfs(x, y);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cout<<dis[i][j]<<"    ";
		}
		cout<<endl;
	}
	return 0;
}

24.01迷宫（dfs）

在这里插入图片描述
思路：记录每个点属于哪个连通块，记录每个连通块的点个数

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e3 + 10, M = 1e5 + 10;
char g[N][N];
int vis[N][N];
int mp[M];
int n, m;
int cnt;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

void dfs(int x, int y, int z){
	vis[x][y] = z;
	mp[z]++;
	for(int i = 0; i < 4; i++){
		int a = x + dx[i], b = y + dy[i];
		if(a < 1 || a > n || b < 1 || b > n) continue;
		if(vis[a][b]) continue;
		if(g[a][b] == g[x][y]) continue;
		dfs(a, b, z);
	}
}

int main(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin>>g[i][j];
		}
	}
	for(int i = 1; i <= m; i++){
		int x, y;
		cin>>x>>y;
		if(!vis[x][y]){
			dfs(x, y, i);
			cout<<mp[i]<<endl;
			vis[x][y] = i;
		}else{
			cout<<mp[vis[x][y]]<<endl;
		}
	}
	return 0;
}

25.村村通（并查集、dfs）

在这里插入图片描述
思路：把连通的点放在一个集合，只需要找多少个不连通的集合，需要加的边数就是这个数量减一

// 并查集
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int p[N];
int n, m;

int fd(int x){
	if(x != p[x]){
		p[x] = fd(p[x]);
	}
	return p[x];
}

// 合并两个集合 
void ff(int x, int y){
	int t1 = fd(x);
	int t2 = fd(y);
	p[t2] = t1;
}

int main(){
	while(cin>>n && n != 0){
		cin>>m;
		int x, y;
		for(int i = 1; i <= n; i++){
			p[i] = i;
		}
		for(int i = 0; i < m; i++){
			cin>>x>>y;
			ff(x, y);
		}
		int cnt = 0;
		for(int i = 1; i <= n; i++){
			if(fd(i) == i){
				cnt++;
			}
		}
		cnt--;
		cout<<cnt<<endl;
	}
	return 0;
}

// dfs
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e3 + 10;
vector<int> g[N];
int vis[N];
int n, m;

void dfs(int x){
	if(!vis[x]);
	vis[x] = 1;
	for(int y : g[x]){
		if(!vis[y]){
			dfs(y);	
		}
	}
}

int main(){
	while(cin>>n && n != 0){
	    memset(vis, 0, sizeof(vis));
		cin>>m;
		int x, y;
		for(int i = 1; i < N; i++) g[i].clear();
		for(int i = 0; i < m; i++){
			cin>>x>>y;
			g[x].push_back(y);
			g[y].push_back(x);
		}
		int ans = 0;
		for(int i = 1; i <= n; i++){
			if(vis[i]) continue;
			dfs(i);
			ans++;
		}
		ans--;
		cout<<ans<<endl;
	}
	return 0;
}

26.两数之和（哈希表）

在这里插入图片描述

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mp;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            mp[nums[i]] = i + 1;
        }
        for(int i = 0; i < n; i++){
            int x = target - nums[i];
            if(mp[x] > 0 && i != mp[x] - 1){
                return vector<int> {i, mp[x] - 1};
            }
        }
        return vector<int> {0, 0};
    }
};

27.盛水最多的容器（双指针）

在这里插入图片描述

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n - 1;
        int ans = 0, res = 0;
        while(l < r){
            res = min(height[l], height[r]) * (r - l);
            ans = max(ans, res);
            if(height[l] >= height[r]) r--;
            else l++;
        }
        return ans;
    }
};

28.最长公共前缀（模拟）

在这里插入图片描述
思路：枚举第一个字符串的长度，如果后面不满足相等，那就返回

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        
        string prefix = "";
        for (int i = 0; i < strs[0].size(); ++i) {
            char ch = strs[0][i];
            for (int j = 1; j < strs.size(); ++j) {
                if (i >= strs[j].size() || strs[j][i] != ch) {
                    return prefix;
                }
            }
            prefix += ch;
        }
        return prefix;
    }
};

29.寻找重复数（哈希、二分、双指针）

在这里插入图片描述
双指针思路：数组在 [1, n] 之内，所以慢指针每次走一步，快指针每次走两步，如果有环，肯定会相遇

// 哈希
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        map<int, int> mp;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            mp[nums[i]]++;
            if(mp[nums[i]] == 2) return nums[i];
        }
        return 666;
    }
};

// 二分
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                cnt += nums[i] <= mid;
            }
            if (cnt <= mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }
};

// 双指针
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

30.分割数组的最大值（二分答案）

在这里插入图片描述
思路：二分这个最大值

class Solution {
public:

    int check(vector<int>& nums, int x, int k){
        int sum = 0;
        int n = nums.size();
        int cnt = 1;
        for(int i = 0; i < n; i++){
            if(sum + nums[i] <= x){
                sum += nums[i];
            }else{
                sum = nums[i];
                cnt++;
            }
        }
        return cnt <= k;
    }

    int splitArray(vector<int>& nums, int k) {
        int n = nums.size();
        int sum = 0, res = 0;
        for(int i = 0; i < n; i++){
            sum += nums[i];
            res = max(res, nums[i]);
        }
        int l = res - 1, r = sum + 1;
        while(l + 1 < r){
            int mid = (l + r) / 2;
            if(check(nums, mid, k)) r = mid;
            else l = mid;
        }
        return r;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/530311.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

软考高级架构师：TCP/IP 协议 和 OSI 七层模型

软考高级架构师：TCP/IP 协议 和 OSI 七层模型

一、AI 讲解 TCP/IP 协议族是一组计算机网络通信协议的集合&#xff0c;其中TCP和IP是两个核心协议。TCP/IP 协议族通常被用来参照互联网的基础通信架构。与之相对的OSI七层模型&#xff0c;是一个更为理论化的网络通信模型&#xff0c;它将网络通信分为七个层次。 TCP/IP 与…
阅读更多...
LeetCode 289.生命游戏————2024 春招冲刺百题计划

LeetCode 289.生命游戏————2024 春招冲刺百题计划

根据 百度百科 &#xff0c; 生命游戏 &#xff0c;简称为 生命 &#xff0c;是英国数学家约翰何顿康威在 1970 年发明的细胞自动机。 给定一个包含 m n 个格子的面板&#xff0c;每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态&#xff1a; 1 即为 活细胞 &am…
阅读更多...
【攻防世界】题目名称-文件包含

【攻防世界】题目名称-文件包含

看到 include()&#xff0c;想到文件包含&#xff0c;用php伪协议。 知识点 看到 include()&#xff0c;require()&#xff0c;include_once()&#xff0c;require_once() &#xff0c;想到文件包含&#xff0c;用php伪协议 ?filenamephp://filter/readconvert.base64-encode/…
阅读更多...
4.9java学习总结

4.9java学习总结

常用API(了解即可,用到了再回来看) API(工具类):已经打包好我们可以根据他提供的格式直接用就好(很像函数) API都可以通过 类名.方法名 进行调用. Math Math类包用于常用的基本数学运算的方法. System: System类包提供了一些与系统相关的方法 Runtime: Runtime类包提供方…
阅读更多...
《系统架构设计师教程（第2版）》第9章-软件可靠性基础知识-01-软件可靠性基本概念

《系统架构设计师教程（第2版）》第9章-软件可靠性基础知识-01-软件可靠性基本概念

文章目录 1. 软件可靠性的概述1.1 定义1.1.1 规定的时间1.1.2 规定的条件1.1.3 所要求的功能 1.2 定义的特点和意义1.3 注意点 2. 软件可靠性的定量描述2.1 规定时间2.1.1 自然时间2.1.2 运行时间执行时间 2.2 失效概率 F(t)2.3 可靠度 R(t)2.4 失效强度 f(t)2.5 平均失效前时间…
阅读更多...
modelsim 仿真bmp图片实现RGB_YCrCb

modelsim 仿真bmp图片实现RGB_YCrCb

用modelsim_se软件仿真bmp图片&#xff0c;可在modesim中实现一些图片处理算法和查看效果 本文以最简单的仿真一副bmp图像为例&#xff0c;实现RGB_YCrCb的modelsim仿真,带源工程 1、先在本地建立文件夹 2、首先打开moselsim 3、新建库和新建项目&#xff0c;保存到建立的文件…
阅读更多...
Android音视频的基础

Android音视频的基础

视频是什么&#xff1f; 视频就是由一系列图片构成的。 视频帧 帧&#xff0c;是视频的一个基本概念&#xff0c;表示一张画面&#xff0c;如上面的翻页动画书中的一页&#xff0c;就是一帧。一个视频就是由许许多多帧组成的。 帧率 帧率&#xff0c;即单位时间内帧的数量&a…
阅读更多...
39-性能分析（下）：APIServer性能测试和调优实战

39-性能分析（下）：APIServer性能测试和调优实战

在API上线之前&#xff0c;我们需要知道API的性能&#xff0c;以便知道API服务器所能承载的最大请求量、性能瓶颈&#xff0c;再根据业务对性能的要求&#xff0c;来对API进行性能调优或者扩缩容。通过这些&#xff0c;可以使API稳定地对外提供服务&#xff0c;并且让请求在合理…
阅读更多...
网络网络层之(7)PPPOE协议

网络网络层之(7)PPPOE协议

网络网络层之(7)PPPOE协议 Author: Once Day Date: 2024年4月7日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文档可参考专栏&#xff1a;通信网络技术_Once-Day…
阅读更多...
紫叶写作靠谱不 #笔记#学习方法#媒体

紫叶写作靠谱不 #笔记#学习方法#媒体

紫叶写作是一款非常好用的论文写作工具&#xff0c;它不仅提供了查重降重的功能&#xff0c;还能帮助用户快速完成论文的撰写和格式编辑。通过紫叶写作&#xff0c;用户可以轻松地查重降重&#xff0c;避免论文中出现抄袭和重复的现象&#xff0c;保证论文的原创性和质量。 紫叶…
阅读更多...
【网络】P2P打洞原理（简单描述）

【网络】P2P打洞原理（简单描述）

本文首发于 ❄️慕雪的寒舍 引入 如果你折腾过NAS或者BT下载等等玩意&#xff0c;可能听说过“P2P打洞”这一技术名词。简单来说&#xff0c;P2P打洞可以让我们直接在外网访问内网的设备&#xff0c;从而让没有公网IP的家庭设备也能获得“公网直连”的速度。 比如绿联、极空间…
阅读更多...
创建个人百度百科需要什么条件？

创建个人百度百科需要什么条件？

互联网时代&#xff0c;创建百度百科词条可以给个人带来更多的曝光和展现&#xff0c;相当于一个镀金的网络名片&#xff0c;人人都想上百度百科&#xff0c;但并不是人人都能创建上去的。 个人百度百科词条的创建需要满足一定的条件&#xff0c;今天伯乐网络传媒就来给大家聊聊…
阅读更多...
神经网络解决回归问题（更新ing）

神经网络解决回归问题（更新ing）

神经网络应用于回归问题 神经网络是处理回归问题的强大工具&#xff0c;它们能够学习输入数据和输出之间的复杂关系。 神经网络提供了一种灵活且强大的框架&#xff0c;用于建模和预测回归问题。通过 适当的 网络结构、训练策略和正则化技术&#xff0c;可以有效地从数据中学…
阅读更多...
在Linux系统上实现TCP（socket）通信

在Linux系统上实现TCP（socket）通信

一.什么TCP TCP&#xff08;传输控制协议&#xff09;是一种面向连接的、可靠的、基于字节流的传输层通信协议。 二.TCP通信流程 三. TCP 服务器端 1 创建socket int sockfd socket(AF_INET, SOCK_STREAM, 0); //SOCK_STREAM tcp通信2 绑定(bind) struct sockaddr_in myad…
阅读更多...
系统架构最佳实践 -- 智慧图书管理系统架构设计

系统架构最佳实践 -- 智慧图书管理系统架构设计

随着数字化时代的到来&#xff0c;智慧图书管理系统在图书馆和机构中扮演着重要的角色。一个优秀的图书管理系统不仅需要满足基本的借阅管理需求&#xff0c;还需要具备高效的性能、良好的扩展性和稳定的安全性。本文将讨论智慧图书管理系统的架构设计与实现&#xff0c;以满足…
阅读更多...
计算机视觉异常检测——PatchCore面向全召回率的工业异常检测

计算机视觉异常检测——PatchCore面向全召回率的工业异常检测

1. 概述 异常检测问题在工业图像数据分析中扮演着至关重要的角色&#xff0c;其目的是从大量正常数据中识别出异常行为或模式。这一任务的挑战在于&#xff0c;正常数据的样本相对容易获取&#xff0c;而异常情况却因其稀有性和多样性而难以收集。为了解决这一问题&#xff0c…
阅读更多...
裸机开发之汇编、寄存器

裸机开发之汇编、寄存器

一、什么是汇编&#xff1f;为什么学汇编&#xff1f; 在之前写控制代码的时候就在想&#xff1a;底层是怎么控制的&#xff1f;后来经过学习知道之前所编写的代码都是应用层代码&#xff0c;顾名思义就是在系统写好的底层之上调用系统函数。原以为底层是指写系统写好的底层函数…
阅读更多...
苹果电脑（Mac）怎么清理 itunes 备份？

苹果电脑（Mac）怎么清理 itunes 备份？

苹果电脑用户广泛利用 iTunes 应用程序对 iPhone 或 iPad进行定期备份&#xff0c;以确保珍贵的数据安全无虞。然而&#xff0c;随着备份历史的增长&#xff0c;它们会在磁盘上积累大量空间&#xff0c;尤其当您频繁为多台设备备份时&#xff0c;存储资源可能会迅速消耗殆尽。为…
阅读更多...
3D Web轻量化引擎HOOPS Commuicator如何从整体装配中创建破碎的装配零件和XML？

3D Web轻量化引擎HOOPS Commuicator如何从整体装配中创建破碎的装配零件和XML？

前言 虽然可以从某些本机CAD格式&#xff08;其子组件驻留在单独的文件中&#xff0c;例如CATIA V5、Creo - Pro/E、NX或SolidWorks&#xff09;创建破碎装配&#xff0c;但无法从整体装配文件&#xff08;例如IFC、Revit&#xff09;创建或3DXML。 本文介绍了一个示例&#…
阅读更多...
学习Rust的第一天：基础知识

学习Rust的第一天：基础知识

Introduction 介绍 I am Shafin Murani is a software development student and I am documenting every single day of my progress in learning rust. This is the first article of the series. Shafin Muranishi 是一名软件开发专业的学生&#xff0c;这是他在30天内记录学…
阅读更多...
最新文章

Copyright @ 2022~2023