c++
c++
求最值
max(a,b);//求两个数的最大值
min(a,b);//求两个数的最小值
max({a,b,c});//同上
min({a,b,c});
求平方根、绝对值
abs(x);//求绝对值
sqrt(n)//等于i*i>n 返回浮点值
交换
swap(a,b);//交换的是数值
求最大公约数、最小公倍数
__gcd(a,b);//最大公约数
__lcm(a,b);//此为自定义函数
//套用：
__gcd(a,__gcd(b,c));
__lcm(a,__lcm(b,c));
int lcm(int a,int b){
return a/__gcd*b;
}
string
//字符串 string
//string⼜称之为string类型字符串，它是C++中STL中的⼀种容器，它的使⽤⽅式和字符数组⼤体相同，并且增加了 ⼀些新的功能和特性，string就是字符串数据类型。
char a[300];
翻转 reverse()
查找子串 s.find()
截取子串 s.substr()
删除 s.erase()
替换 s.replace()
从字符串后方删除、添加一个字符
定义字符串并输出
string s = "hello";
cout << s;
输入并输出
string s;
cin >> s;
cout << s;
输入整行
string s;
getline(cin, s);
cout << s;
获取字符串长度
int len = s.size();
int len2 = s.length();
大小判断
string s1 = "abc", s2 = "def";
cout << (s1 < s2);
字符串的拼接:
string s1, s2, s3;
cin >> s1 >> s2;
cout << s1 << endl << s2 << endl;
s3 = s1 + s2;
s3 += s2;
s3 += s2;
cout << s3;
for (int i = 1; i <= n; i ++) {
cin >> s;
s3 += s;
}
查找子串函数
string s = "abc";
string substring = "bc";
int pos = s.find(substring) // 返回第一个找到的位置下标1
find:{
string s1 = "abc";
string substring = "xbc";
int pos = s1.find(substring);
cout << pos; // 如果找不到，返回NPOS，如果存到int变量中，或转换成int类型，数值为-1
// s1.find()如果找不到，返回的NPOS是一个很大的数，需要先存到int变量中，转换为int类 型，才能使用（跟-1比较）
string s1 = "abc";
string substring = "xbc";
int pos = s1.find(substring);
int pos = s1.find(substring, 开始查找的起点的下标);
cout << pos;
string s1 = "abcbcbbc";
string substring = "bc";
int pos = s1.find(substring);
cout << pos << endl;
pos = s1.find(substring, pos + 1);
cout << pos << endl;
pos = s1.find(substring, pos + 1);
cout << pos << endl;
do while 函数 查找子串位置
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, s2;
cin >> s2 >> s1;
int pos = -1, cnt = 0;
do {
pos = s1.find(s2, pos + 1);
if (pos != -1) {
cnt ++;
}
} while (pos != -1);
cout << cnt;
return 0;
}
int pos = s1.find(a);
cout << pos+1 << endl;
}
翻转函数
reverse(要反转的区间开始的位置, 要反转的区间结束的位置的下一个位置);
reverse(s.begin(), s.end()); // 全部翻转
reverse(s.begin() + 0, s.begin() + 7); // 从下标0翻转到下标6
reverse(s.begin() + 3, s.begin() + 7); // 从下标3翻转到下标6
一阶段
自增
int i = 1;
// i = i + 1;
i ++;
// 作用： 把i+1的值存回变量i
i = i + 2;
i += 2;
// 自减
i --;
i -= 2;
i *= 2；
i /= 2；
cout << i;
程序的三大结构
顺序结构
按照从上到下的顺序依次执行每一条代码指令。
分支结构
根据条件的判断 执行不同的代码指令。
循环结构
计算机为了重复执行某条语句或某些条语句而设置的结构。
输出5行星号 输出15行星号 输出一万五千行星号
跟计算机讲： 输出一个星号和一个换行。帮我重复一万五千次。
100000000次运算
计数思想 输出3行星号
创建一个计数变量 cnt: 0
for循环（计数循环）
循环要做的事情：
- 初始化计数变量，一开始设为零
- 用计数变量和目标次数比较（如果足够，就结束）
- 如果还需要进行，就执行一次
- 计数变量加一
- 回到第二条
for循环语法格式
for (初始化计数变量; 判断循环条件; 更新计数变量) {
// 循环体（要重复执行的语句）
}
for (int i = 0; i < 3; i++) {
cout << "*" << endl;
}
- 初始化计数变量
- 判断是否进行下一次循环
- 执行一次循环体
- 更新计数变量
- 回到第二步
int i = 0;
if (i < 3) {
cout << "*" << endl;
i++;
}
if (i < 3) {
cout << "*" << endl;
i++;
}
if (i < 3) {
cout << "*" << endl;
i++;
}
if (i < 3) {
cout << "*" << endl;
i++;
}
什么时候用int i = 1; 什么时候用int i = 0;
for (int i = 1; i <= 10; i ++) {
}
for (int i = 0; i < 10; i ++) {
}
枚举 输出1~100以内所有的偶数
让i从1变到100，每次增加1，一个一个看。
对于每一次，看i是否能整除2.如果是，则符合条件，直接输出
- 枚举的范围（起点和终点）
- 判断条件
- 执行相应操作
- 确定循环范围 (起点：1， 终点：n次)
- 确定循环体 输出i和一个加号
把i从1枚举到100
for (int i = 1; i <= 100; i ++) {
}
把i从53枚举到66
for (int i = 53; i <= 66; i++) {
}
把i从99枚举到3
for (int i = 99; i >= 3; i --) {
}
输入整数n
统计1~n中有多少个整数满足如下条件：
- 是3的倍数
- 不是5的倍数
输出满足条件的整数的个数
首先，定义计数器cnt = 0
定义并输入n
把i从1枚举到n{
如果i是3的倍数并且i不是5的倍数
cnt++
}
输出cnt
统计满足条件整数的个数
循环中输入数字 在输入的第一行给定一个整数n 在输入的第二行，给定n个整数（用空格分隔） 统计第二行的这n个整数中有多少个数字满足如下条件：
- 是3的倍数
- 不是5的倍数
输出满足条件的整数的个数
5
7 9 10 30 18
2
定义并输入n // cin >> n;
定义变量a //用来保存循环中输入的数字
定义计数器cnt=0
把i从1枚举到n （重复n次）{
输入一个数字，保存到a中// cin >> a
如果a是3的倍数并且a不是5的倍数
cnt++
}
输出2
#include <iostream>
using namespace std;
int main() {
int n, a, cnt = 0;
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a;
if (a % 3 == 0 && a % 5 != 0) {
cnt ++;
}
}
cout << cnt;
return 0;
}
一维数组
什么是数组
数组是数据类型相同元素的集合。数组在内存中创建连续的存储空间，相当于创建了多个类型相同的变量。
数组的构成
- 数组元素的类型
- 数组名
- 数组的大小（数组中有多少元素）
创建数组
数据类型 数组名[数组大小];
// 创建一个有一百个元素的数组
int a[100];
声明数组最好声明成全局。声明成全局时，数组中的每一个元素默认都是0。
#include <iostream>
using namespace std;
int a[10010];
int main(){
}
如果需要事先定义数组大小，然后创建多个长度相同的数组，在全局定义数组时，数组大小需要用常量表示，不能使用变量。定义常量需要使用关键字const
#include <iostream>
using namespace std;
const MAXN = 10010;
int a[MAXN], b[MAXN];
int main(){
}
使用数组
下标
在数组中每一个元素都有一个编号。第一个元素的编号为0，最后一个元素的编号为n-1（假设一共有n个元素）。数组元素的编号被称为下标。如果这个数组的大小为100，那么数组的第一个元素下标为0，最后一个元素下标为99.
在使用数组元素进行读取或存储时，需要使用数组名和数组下标。
数组名[下标];
// a[0] = 23; // 将数组a中下标为0的元素赋值为23
// cin >> a[2]; // 输入一个数字，将其保存到数组a中下标为2的元素（也就是第三个元素）
// cout << a[2]; 输出下标为2的元素
下标必须是一个整数。下标可以是常量，变量或表达式。因此可以使用a[1], a[i],a[i + 1]等。
数组的初始化
如果需要在创建数组时，在代码中初始化数组的值，那么可以使用大括号。
int a[3] = {1, 2, 3};
如果方括号内不写数组大小，编译器将自动计算初始化的元素并设置为数组大小。
int a[] = {1, 2, 3}; // a数组大小为3
如果方括号内指定的数组大小大于大括号中用来初始化的元素个数，那么前几个元素将使用大括号中的元素，后续的其他元素将被设置为0.
int a[5] = {1, 2, 3};
// 数组 a:[1][2][3][0][0]
使用数组时需要注意的问题
- 同一个数组，所有元素的数据类型相同。（这一点和Python不同）
- 数组下标是从0开始计算的，比如a数组中的第一个元素用a[0]来表示。
- 避免数组下标越界问题，比如
int a[10];最后一个元素用a[9]来表示，没有a[10]这个位置，如果去访问a[10]这个位置后，就会造成数组下标访问越界问题。(访问了没有创建的变量) - 访问元素或更新元素不能只用数组名，需要结合数组名和下标。比如要给数组a中的某个元素赋值为10，不能用a=10,需要a[下标]=10
- 数组下标虽然从0开始，但是可以从下标为1的位置开始存放数据，将下标为0的那个位置空出来，访问的时候也从下标为1的位置开始访问，但是需要多开几个位置，防止数组下标访问越界。
访问数组元素
读取一个元素，进行需要的操作的动作，在数组中，可以叫做“访问”。
例如：访问第一个元素（访问下标为0的元素），即a[0]。访问元素中的每一个元素。
遍历
将数组的每一个元素都读取一遍，即访问数组中的每一个元素，进行需要的操作（例如每一个都输出一次，或者每一个都加到累加器中）。
例题：倒序输出
例1：输入5个数存入到数组中，再将这5个数按倒序进行输出。
样例输入： 2 5 3 4 6
样例输出：6 5 4 5 2
思路：
因为需要倒序输出，最先输出的元素是最后输入的，最后输出的元素是一开始输入的，因此需要记忆（保存）所有的元素，才能后输出最先输入的元素。
- 如果决定从下标1开始存放元素（忽略下标0），那么创建一个大小为6的数组（使得最后的一个元素的下标为5）
- 使用循环，将i从1枚举到5，每次输入一个数字，将每次输入的数值保存到
a[i]中，由此将全部的5个数组保存到数组中。 - 使用循环，将i从5枚举到1，每次输出
a[i]，实现倒序输出
#include<iostream>
using namespace std;
int a[6];
int main(){
for(int i=1;i<=5;i++) {
cin>>a[i];
}
for(int i=1;i<=5;i++) {
cout<<a[i]<<" ";
}
return 0;
}
凹陷数
题目描述
在已知一组整数中，有这样一种数非常怪，它们不在第一个，不在第二个，不在最后一个，也不在倒数第二个，而且刚好都比左边两个和右边两个相邻的数小，你能找到它们吗？
输入格式
第一行为整数m，表示输入的整数个数。（ 5<= m <=100 ) 第二行为m个整数。
输出格式
若干个凹陷数，每行一个。
样例输入
5
3 2 1 2 3
样例输出
1
思路：
从第一个可能得元素枚举到最后一个可能的元素，即从下标`3`枚举到下标`m-2` {
如果a[i] 小于以下四个元素：a[i-1],a[i-2],a[i+1],a[i+2]，那么他是凹陷数 {
输出这个元素的值，即输出a[i]
}
}
高精
加法
#include <bits/stdc++.h>
using namespace std;
int a[1001],b[1001],ans[10001];
int main(){
string s1,s2;
cin >>s1>>s2;
int s1len=s1.size(),s2len=s2.size(),len=max(s1len,s2len);
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
for(int i=0;i<s1len;i++){
a[i]=int(s1[i]-'0');
}
for(int i=0;i<s2len;i++){
b[i]=int(s2[i]-'0');
}
for(int i=0;i<len;i++){
ans[i]+=a[i]+b[i];
if(ans[i]>=10){
ans[i+1]++;
ans[i]-=10;
}
}
if(a[0]+b[0]>=10){
for(int i=len;i>=0;i--){
cout <<ans[i];
}
}else{
for(int i=len-1;i>=0;i--){
cout <<ans[i];
}
}
return 0;
}
减法
#include <bits/stdc++.h>
using namespace std;
const int N=10087;
int a[N],b[N],ans[N];
int main(){
string s1,s2;
cin >>s1>>s2;
int lena=s1.size(),lenb=s2.size(),len=max(lena,lenb);
int flag1 = lena==lenb&&a<b;
int flag2 = lena<lenb;
if((lena==lenb&&s1<s2)||lena<lenb){
cout <<"-";
swap(s1,s2);
swap(lena,lenb);
}
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
for(int i=0;i<lena;i++) a[i]=s1[i]-'0';
for(int i=0;i<lenb;i++) b[i]=s2[i]-'0';
for(int i=0;i<len;i++){
ans[i]+=a[i]-b[i];
if(ans[i]<0){
ans[i]+=10;
ans[i+1]--;
}
}
while(ans[len-1]==0&&len>=2){
len--;
}
for(int i=len-1;i>=0;i--){
cout <<ans[i];
}
return 0;
}
乘法
#include <bits/stdc++.h>
using namespace std;
int a[2001],b[2001],ans[4002];
int main(){
string s1,s2;
cin >>s1>>s2;
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
int len1=s1.size(),len2=s2.size();
for(int i=0;i<len1;i++) a[i]=s1[i]-'0';
for(int i=0;i<len2;i++) b[i]=s2[i]-'0';
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
ans[i+j]+=a[i]*b[j];
ans[i+j+1]+=ans[i+j]/10;
ans[i+j]%=10;
}
}
int len=len1+len2;
while(ans[len-1]==0&&len>=2){
len--;
}
for(int i=len-1;i>=0;i--){
cout <<ans[i];
}
return 0;
}
除法（高精度除以低精度）
#include <bits/stdc++.h>
using namespace std;
int a[5002],ans[5002];
int main(){
string s;
int b;
cin >>s>>b;
for(int i=0;i<int(s.size());i++){
a[i]=s[i]-48;
}
long long rem=0;
for(int i=0;i<(int)s.size();i++){
rem=rem*10+a[i];
ans[i]=rem/b;
rem%=b;
}
int start=0;
while(ans[start]==0&&start<=int(s.size()-2)){
start++;
}
for(int i=start;i<s.size();i++){
cout <<ans[i];
}
return 0;
}
时间复杂度
#include <bits/stdc++.h>
using namespace std;
int main(){
int i=1;
cout <<i;
return 0;
}
这个程序的时间复杂度为O(1)
#include <bits/stdc++.h>
using namespace std;
int main(){
for(int i=1;i<=n;i++){
cout <<i<<" ";
}
return 0;
}
这个程序的时间复杂度为O(n)
#include <bits/stdc++.h>
using namespace std;
int main(){
for(int i=1;i<=n;i++){
for(int j=1;j*j<=n;j++){
cout <<a[i][j];
}
}
return 0;
}
这个程序的时间复杂度为O(n*sqrt(n))
#include <bits/stdc++.h>
using namespace std;
int main(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j+=j){
cout <<a[i][j];
}
}
return 0;
}
这个程序的时间复杂度为O(n*log(n))
#include <bits/stdc++.h>
using namespace std;
int main(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout <<i;
}
}
return 0;
}
这个程序的时间复杂度为
o(n2)#include <bits/stdc++.h>
using namespace std;
int a[5]={0,1,2,3,4};
int main(){
cout <<next_permutation(a+1,a+n+1);
return 0;
}
这个程序的时间复杂度为
o(n!)分支结构
给出一条件，当满足条件时，执行特定语句。
单分支
if (条件) {
// 语句
}
双分支
if (条件) {
//语句
} else {
//语句
}
if (score >= 60) {
cout << "及格";
} else {
cout << "不及格";
}
多分支 （只能选择一条岔路）
if (条件1) {
// 1
} else if (条件2) {
// 2
} else if (条件3) {
// 3
} else {
// 其他
}
多个if语句
int maxn = -2e9; // int maxn = -2000000000; -2*10^9
int a, b, c;
cin >> a >> b >> c;
if (a > maxn) maxn = a;
if (b > maxn) maxn = b;
if (c > maxn) maxn = c;
cout << maxn;
分支嵌套
if (c == '/') {
if (b == 0) {
cout << "除数不能为零!"
} else {
cout << a / b;
}
}
分支嵌套
if (c == '/') {
if (b == 0) {
cout << "Divided by zero!"
} else {
cout << a / b;
}
}
简单计算器：
定义整数a, b
定义字符变量c (char c;)
输入 a（左边的操作数），b（右边的操作数），c（操作符）
如果c是加号{
输出a+b
}否则 如果c是减号 {
输出a-b
}否则 如果c是乘号 {
输出a * b
}否则 如果c是除号 {
如果b等于0 {
输出Divided by zero!
} 否则 {
输出a/b
}
}否则{
// c已经排除了+-*/的情况
输出“无效操作符的英文 Invalid operator!"
}
if (c == '+') {
} else if (c == '-') {
} else if (c == '*') {
cout << a * b;
} else if (c == '/') {
if (b == 0) {
} else {
cout << a / b;
}
} else {
}
判断闰年：
判断，年份n是否是100的倍数{
判断n是否是400的倍数 {
是闰年
} 否则 {
不是闰年
}
}否则{
判断n是否是4的倍数{
是闰年
} 否则 {
不是闰年
}
}
乘车费用
输入总里程N，等待时间M
设置整数变量a，用于保存费用。
将a设为起步费6元
// 先计算2公里到10公里之内的费用
判断，如果总里程N大于2公里{
如果总里程大于10公里，那么只计算2公里到10公里之间的这8公里的费用，否则计算总里程N减去起步里程2公里的里程。单价是2元
}
// 在计算超过10公里的费用
判断，如果总里程N大于10公里{
对于总里程N大于10公里的部分，用单价3元来计算
}
加上等待费用
输出费用
int a = 6;
int N, M;
cin >> N >> M;
if (N > 2) {
if (N > 10) {
a = a + 8 * 2;
} else {
a = a + (N - 2) * 2;
}
}
if (N > 10) {
a = a + (N - 10) * 3;
}
a = a + M / 3;
cout << a;
进制转换
函数
string a="0123456789ABCDEF";
string to_k(long long n,int k){//十进制转换k进制
string s;
if(n==0){
return "0";
}
while(n){
s.push_back(a[n%k]);
n/=k;
}
reverse(s.begin(),s.end());
return s;
}
long long to_dec(string s,int k){//k进制转换十进制
if(s=="0"){
return 0;
}
long long sum=0,w=1;
for(int i=s.size()-1;i>=0;i--){
if(s[i]>='A'&&s[i]<='F'){
sum+=(s[i]-'A'+10)*w;
}else{
sum+=(s[i]-'0')*w;
}
w*=k;
}
return sum;
}
加载中...