coding_note

备赛蓝桥杯时做的一些题目,记录一下

next_permutation()

在C++中,std::next_permutation 是一个标准库函数,用于生成序列的下一个排列。这个函数定义在头文件 <algorithm> 中,可以用于遍历一个序列的所有可能的排列。

std::next_permutation 函数的基本用法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <algorithm>
#include <iostream>
#include <string>

int main() {
std::string s = "ABC";
if (std::next_permutation(s.begin(), s.end())) {
std::cout << "The next permutation is: " << s << std::endl;
} else {
std::cout << "There are no more permutations." << std::endl;
}
return 0;
}

在这个例子中,std::next_permutation 函数尝试为字符串 s 生成下一个排列。如果成功,函数返回 true,并且 s 会被更新为下一个排列。如果已经是最后一个排列,函数返回 falses 保持不变。

函数的参数是序列的开始和结束迭代器。对于数组,可以使用数组的指针或数组的引用作为参数。例如:

1
2
int arr[] = {1, 2, 3};
std::next_permutation(arr, arr + sizeof(arr) / sizeof(arr[0]));

在使用 std::next_permutation 时,通常将其放在一个循环中,以便遍历序列的所有排列。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
std::vector<int> v = {1, 2, 3};
do {
for (int i : v) {
std::cout << i << ' ';
}
std::cout << '\n';
} while (std::next_permutation(v.begin(), v.end()));
return 0;
}

在这个例子中,do-while 循环确保了即使在最后一次调用 std::next_permutation 后,循环体内的代码也会执行,从而打印出最后一个排列。然后,std::next_permutation 被调用,尝试生成下一个排列。循环会一直继续,直到所有的排列都被遍历完毕。

无重复字符的最长子串

给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。

希哈表+快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int lengthOfLongestSubstring(char* s) {
int result = 0, i = 0, j = 0;
int length = strlen(s);
int cnt[128] = { 0 };
for (j = 0; j < length; j++) {
cnt[s[j]]++;
if (cnt[s[j]] > 1) {//遇到重复的字母
result = result < j - i ? j - i : result;//计算快慢指针间子串的长度并更新
//查找第一个重复字母并清零计数
for (int k = i; k < j; k++) {
cnt[s[k]]--; //清零第一个重复字母(含)前的计数
if (s[k] == s[j]) {//找到第一个重复字母,退出查找循环
i = k;
break;
}
}
i++;//慢指针指向第一个重复字母后的字母
}
}
result = result < j - i ? j - i : result;
return result;
}

对一列数排序(火星人)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
int a[10110];
cin>>n;
cin>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
while(m--)
{
next_permutation(a+1,a+1+n); //对数组排序传递索引即可
}
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}

排列序数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
//先对输入的字符串进行排列,然后输出全排列的情况,情况想等时结束
int main()
{
string s,o;
cin>>s;
o=s;
sort(s.begin(),s.end()); //字符串内部排序的实现
if(s==o) cout<<0;
int cnt=0;
while(next_permutation(s.begin(),s.end()))
{
cnt++;
if(s==o) cout<<cnt;
}
return 0;
}

第几个幸运数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>  //cpp实现
using namespace std;
int main() //暴力搜索
{
long long n=59084709587505;
int cnt=0;
for(int i=0;pow(3,i)<n;i++)
{
for(int j=0;pow(5,j)<n;j++)
{
for(int k=0;pow(7,k)<n;k++)
{
if(pow(3,i)*pow(5,j)*pow(7,k)<=n) cnt++;
}
}
}
printf("%d",cnt-1);
return 0;
}
1
2
3
4
5
6
7
8
9
10
import os  # python实现
import sys
cnt=0
for i in range(50):
for j in range(50):
for k in range (50):
a=3**i;b=5**j;c=7**k
if a*b*c<=59084709587505:
cnt+=1
print(cnt-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
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct stu{ //定义一个结构体来存储相关数据
int id;
int c,m,e;
int sum;
}st[305]; //n<=300
bool cmp(stu a,stu b) //定义一个结构体比较的函数
{
if(a.sum>b.sum) return true;
else if(a.sum<b.sum) return false;
else {
if(a.c>b.c) return true;
else if(a.c<b.c) return false;
else{
if(a.id>b.id) return true;
else return false;
}
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
st[i].id=i+1; //输入学号
cin>>st[i].c>>st[i].m>>st[i].e; //输入三科成绩
st[i].sum=st[i].c+st[i].m+st[i].e;
}
sort(st,st+n,cmp); //按照结构体比较的方式进行排序
for(int i=0;i<5;i++)
{
cout<<st[i].id<<" "<<st[i].sum<<"\n";
}
return 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
27
28
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int a[N];
//60%的解法 算法的复杂度为mnlogn
bool cmp(int a ,int b) //定义降序排列
{
return a>b;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) a[i]=i; //先生成数组包含数1-n
while(m--)
{
int p,q;
cin>>p>>q;
if(p==1) sort(a+q,a+n+1);// 升序排列
if(p==0) sort(a+1,a+q+1,cmp);//降序排列
}
for(int i =1;i<=n;i++)
{
cout<<a[i]<<' ';
}
return 0;
}

错误票据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int m[N];
int main()
{
int n;
cin>>n;
int cnt=0;
while(scanf("%d",&m[cnt])!=EOF) cnt++; //这里需要关注对输入的处理
sort(m,m+cnt);
int ans1,ans2;
for(int i=0;i<cnt-1;i++)
{
if(m[i+1]-m[i]>1) ans1=m[i]+1;
if(m[i]==m[i+1]) ans2=m[i];
}
cout<<ans1<<' '<<ans2;
return 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
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int m[200010];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&m[i]);
}
sort(m,m+n);
int cnt=0;
for(int i=0;i<n;i++)
{
cnt++;
if(m[i]!=m[i+1])
{
printf("%d %d\n",m[i],cnt);
cnt=0;
}
}
return 0;
}

求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int main()
{
long long n;
cin>>n;
int a[200005];
long long sum=0;
long long temp=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
temp +=a[i];
}
for(int i=0;i<n;i++)
{
temp-=a[i];
sum += a[i]*temp;
}
printf("%lld",sum);
return 0;
}

782 拼数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//按两个数字组合的字典序排序,就是把数字看成字符串来排序
#include<bits/stdc++.h>
using namespace std;
bool cmp(string a,string b) //从大到小,按字典序的反序列排列
{
return a+b>b+a; //组合字符串的技巧,这里需要注意
}
int main()
{
int n;
cin>>n;
string a[n];
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n,cmp);
for(int i=0;i<n;i++) cout<<a[i];
return 0;
}

208 带分数

这题我不是很会,参考了题解,懂了一点,感觉好复杂啊啊啊啊啊

仔细看还是很好理解的,就是不太好想到欸,还是自己太菜了。。。

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
27
28
29
30
31
32
33
34
35
36
37
//排列题,9!共有362880种情况,全排列即可,不会超时
#include <bits/stdc++.h>
using namespace std;
int num[9]={1,2,3,4,5,6,7,8,9};
int cnt;
int func(int a,int b)
{
int sum=0;
for(int i=a;i<=b;i++)
{
sum=sum*10+num[i];
}
return sum;
}
int main()
{
int n;
cin>>n;
while(next_permutation(num,num+9))
{
for(int i=0;i<7;i++)
{
for(int j=i+1;j<8;j++)
{
int a=func(0,i);
int b=func(i+1,j);
int c=func(j+1,8); //9个数索引是0到8。。。
if(n*c==a*c+b)
{
cnt++;
}
}
}
}
cout<<cnt;
return 0;
}

回文判定(双指针/反向扫描)

实现一 for循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
int n=s.size();
int cnt=0;
for(int i=0;i<n/2;i++)
if(s[i]!=s[n-i-1]) cnt++;
if(cnt!=0) cout<<'N';
else cout<<'Y';
return 0;
}
实现二 for循环加改进
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
int n=s.size();
int cnt=0;
for(int i=0;i<n/2;i++)
if(s[i]!=s[n-i-1])
{
cout<<'N';
return 0; //这里通过return 0可以实现直接结束程序
}
cout<<'Y';
return 0;
}
实现三 使用while循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin>>s;
int n=s.size();
int i=0,j=n-1; //双指针
while(i<j)
{
if(s[i]!=s[j])
{
cout<<'N';
return 0;
}
i++,j--;
}
cout<<'Y';
return 0;
}


coding_note
http://jrhu0048.github.io/2024/03/20/cpp/codingnote/
作者
JR.HU
发布于
2024年3月20日
更新于
2024年10月26日
许可协议