c++ 学习笔记

重要知识储备

ASCII码表

一维数组相关知识

二维数组相关知识

指针相关知识（包括结构体指针的声明、读写访问等）

细节

读取一行字符

用cin.getline(字符数组，个数)

char a[110];
cin.getline(a,100);
int len=strlen(a);
for(int i=0;i<len;i++){
    ······
}   //i<len可替换为a[i]!=`\0`

setprecision,setw,fixed,setfill

默认计数法保留有效位至多6位,截取数字规则为四舍五入,不会用0补齐到6位有效数字,删去无效位数

setprecision()输出有效位数，进行四舍五入，末尾0将被省略

setw()限定字段宽度，起到右对齐的作用

fixed与setprecision()搭配使用，可以起到限定小数点后几位的作用，不会省略末尾的0

setfill(char c);就是在预设宽度中如果已存在没用完的宽度大小，则用设置的字符c填充

#include<iomanip>    
printf("%3d",a);
cout<<setw(3)<<a;
cout<<fixed<<setprecision(2)<<endl;
cout<<setw(5)<<setfill('@')<<255<<endl;

puts,gets,putchar,getchar

puts(str)

• 把一个字符串输出，直到空字符，但不包括，换行符会被追加
• 该函数返回一个非负值为字符串长度（包括末尾的 \0），否则返回EOF

gets(str)

• 读取一行，并把它存储在str。当读取到换行符时，或者到达文件末尾时，它会停止

putchar(char)

• char被写入的字符。该字符以其对应的int值进行传递
• 输出

getchar(char)

• 读取字符

动态申请内存

int* b=new int [20];
delete [] b;

my* a=new my [n];    (结构体申请)
delete [] a;

int **a=new int* [3]; (二维数组申请)
for(int i=0;i<3;i++)a[i]=new int [4];
for(int i=0;i<3;i++)delete [] a[i];
delete [] a;


#include <stdlib.h> 
int* c=(int*)malloc(sizeof(int)*30);
free(c);

int** a=(int**)malloc(sizeof(int*)*h);
for(int i=0;i<h;i++)a[i]=(int*)malloc(sizeof(int)*w);
for (int i=0;i<h;i++)free(a[i]);
free(a);

静态变量

static int a;

下一次定义的时候会在原来的基础上操作

任意进制转换

#include<iostream>
using namespace std;
int  main(){
 long long num; 
 int a[50];  //取余后的数字暂时存放到数组，然后倒序输出 
 int i=0,j,base,m;
 cin>>num;
 cin>>base;
 //循环取余 
 while(num!=0)
 {
  m=num%base;
  num/=base;
  i++;
  a[i]=m;
 }
 //将数字反序输出 
 for(j=i;j>=1;j--)
 {
  if(a[j]>=10)
   cout<<(char)(a[j]+55); //以字符型输出字母
  else
   cout<<a[j]; 
 }
 return 0;
 }

//递归实现
void fff(int a,int b)
{
    if(a<b)
    {
        cout<<a;
        return;
    }
    fff(a/b,b);
    cout<<a%b;
}

浮点数转二进制

// 浮点数转二进制
#include <bits/stdc++.h>
using namespace std;
void ejz(int n) // 将整数转换为二进制
{
    int sum = 0;
    int y, x = 1;
    while (n != 0)
    {
        y = n % 2;
        sum += x * y;
        x *= 10;
        n /= 2;
    }
    cout << sum;
}
void ejzz(double n) // 将小数转换为二进制
{
    double r, m;
    int k;
    for (k = 1; k <= 20; k++)
    {
        r = n * 2;
        putchar((int)r == 0 ? '0' : '1');
        m = r - (int)r;
        n = m;
        if (n <= 1e-6)
            break;
    }
    return;
}
int main()
{
    double a;
    cin >> a;
    int zs = int(a); // 浮点数拆分成整数和小数
    double xs = a - zs;
    ejz(zs);
    cout << ".";
    ejzz(xs);
    return 0;
}

strlen,strcmp,strcpy,strcat,strstr的用法

strlen 计算字符串的长度

strcmp(str1,str2)

• 如果返回值小于 0，则表示 str1 小于 str2
• 如果返回值大于 0，则表示 str1 大于 str2
• 如果返回值等于 0，则表示 str1 等于 str2

strcpy(str1,str2)

• 将str2复制给str1
• str1可以是数组

strcat(str1,str2)

• 将str2连接在str1末尾
• str1可以是数组，要足够容纳追加后的字符串

strstr(str1,str2)

• str1 – 要被检索的字符串
• str2 – 在 str1 字符串内要搜索的小字符串
• 判断str2是否是str1的子串。如果是，则返回str2在str1中首次出现的地址；如果不是，则返回null；

按位与，按位异或，按位或，取反

按位取反（~）：将0变为1，将1变为0

位与（&）：都为1时才为1，否则为0

位或（|）：只要有一个为1就为1，否则为0

位异或（^）：相同为0，不同为1

细节

算法

排序

冒泡排序

首先比较第一张牌和第二张牌，如果后面的牌比前面的牌小，那么就交换位置；然后比较第二张牌和第三张牌，同样保证第三张牌要大于第二张牌······依次类推，直到比较最后一张牌和倒数第二张牌，这样就可以保证最后面的一张牌是最大的一张了。
代码展示

for(int i = 0; i < n - 1; i++){
    for(int j = 0; j < n - i - 1; j++){
        if(a[j] > a[j + 1]){
            int p = a[j];
            a[j] = a[j + 1];
            a[j + 1] = p;
        }
    }
}

选择排序

从第一张牌到最后一张牌中找到最小的一张，放到最前面；然后从第二张牌到最后一张牌中继续找到最小的一张，放到第二位······如此即可得到从小到大的序列
代码展示

for(int i = 0; i < n -1; i++){
    for(int j = i + 1; j < n; j++){
        if(a[j] < a[i]){
            int p = a[i];
            a[i] = a[j];
            a[j] = p;
        }
    }
}

//进阶：双端选择排序(1)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) //读入
    int begin=0;
    int end=n-1;
    while(begin<end)
    {
        int max=begin;
        int min=begin;
        int i=0;
        for(i=begin+1;i<=end;i++)
        {
            if(a[i]<a[min]) min=i;
            if(a[i]>a[max]) max=i;
        }
        swap(a[begin],a[min]);
        if(begin==max) max=min;  //如果max的位置与begin重合，则begin先与min的位置交换，此时max位置的最大值被交换走，导致 
     swap(a[end],a[max]);     //end与max交换的数值是错误的
        begin++;
        end--;
    }
    return 0;
}

//进阶：双端选择排序(2)
//输入说明
//第一行输入一个正整数n<=1000，表示第二行的整数数目
//第二行输入n个整数，空格隔开
//第三行输入一个大于等于0的整数m，表示几趟排序
#include <iostream>
using namespace std;
int main()
{
    int n,p;
    cin>>n;
    int *a = new int [n];
    for(int i=0;i<n;i++) cin>>a[i];
    cin>>p;
    int left=0;
    int right=n-1;
    while(p--&&left<right)
    {
        for(int i=left;i<=right-1;i++)
            if(a[i]>a[i+1]) swap(a[i],a[i+1]);
        right--;
        for(int i=right;i>=left+1;i--)
            if(a[i]<a[i-1]) swap(a[i],a[i-1]);
        left++;
    }
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
    delete [] a;
    a=NULL;
    return 0;
}

插入排序

二分查找

代码展示(加1还是减1，是小于还是小于或等于视具体情况而定)

一般来说l<=r与r=mid-1一起使用

int find(int x)
{
    int l = 1, r = n + 1;
    while (l < r)
    {
        int mid = l + (r - l) / 2;
        // 有时l+r可能超过int类型的极限
        if (a[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    if (a[l] == x)
        return l;
    else
        return -1;
}

洛谷P2249 【深基13.例1】查找

题目描述

输入 n 个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,···,an，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。

输入格式

第一行 2 个整数 n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

输出格式

输出一行，m 个整数，以空格隔开，表示答案。

样例 #1

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出 #1

1 2 -1

提示

数据保证，1<=n<=10^6，0<=ai,q<=10^9，1<=m<=10^5
本题输入输出量较大，请使用较快的 IO 方式。

代码

#include <iostream>
using namespace std;
int n, m, a[1000005];
int find(int x) {
 int l = 1, r = n;
 while (l < r) {
  int mid = (l + r) >> 1;
  if (a[mid] >= x)r = mid;
  else l = mid + 1;
 }
 if (a[l] == x)return l;
 else return -1;
}
int main()
{
 cin >> n >> m;
 int tmp;
 for (int i = 1; i <= n; i++)cin >> a[i];
 for (int i = 0; i < m; i++) {
  cin >> tmp;
  cout << find(tmp) << " ";
 }
 system("pause");
 return 0;
}

杨辉三角(三种实现方式)

//1. 简单相加
a[i][j]=a[i-1][j-1]+a[i-1][j];

//2. 递归实现
long long f(int a,int b)
{
    if(b==0 or a==b) return 1;
    return f(a-1,b-1)+f(a-1,b);
}

//3. 排列数
long long f(int a,int b)
{
    if(b==0 or a==b) return 1;
    long long ans=1;
    for(int fm=1,fz=a;fm<b;fm++,fz--) ans=ans*fz/fm;
    return ans;
}

猴子选大王

尼克斯彻定理

尼克斯彻定理：任何一个大于等于1的整数的立方等于一串连续奇数之和

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int i = 1, j = 1, sum = 0;
    while (sum != n * n * n) {
        if (sum < n * n * n) {
            sum += j;
            j += 2;
        } else {
            sum -= i;
            i += 2;
        }
    }
    cout << n << "^3=";
    for (int k = i; k < j; k += 2) {
        cout << k;
        if (k < j - 2) cout << "+";
    }
    cout << endl;
    return 0;
}
/*
 * i=1 3 5 7
 * j=1 3 5 7 9 11
 * sum=0 1 4 9 16 25 36 35 32 27
 * x=27
 * */

矩阵乘法

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        int summ=0;
        for(int k=1;k<=n;k++){
            summ+=a[i][k]*b[k][j];
        }
        c[i][j]=summ;
    }
}

求最大公约数和最小公倍数

//最小公约数
while(c>0){   
 e=d%c;
 d=c;
 c=e;
}  //cout<<d;

while(d%c!=0){   
 e=d%c;
 d=c;
 c=e;
}  //cout<<c;

int gcd(int a, int b)
{
   if (b == 0)
       return a;
   else
       return gcd(b, a % b);
}
//最大公倍数
int lcm(int a, int b)
{
    return (a * b) / gcd(a, b);
}

质数因子分解

#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
    int val, num;
};
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
bool cmp(node a, node b)                //按因子个数从大到小排序，如果个数一样，则按因子本身从大到小排序
{
    if (a.num != b.num)
        return a.num > b.num;
    return a.val > b.val;
}
int main()
{
    int n, a, c;
    cin >> n;
    cin >> a;
    for (int i = 2; i <= n; i++)
    {
        cin >> c;
        a = a * c / gcd(a, c);         //求多个数的最小公倍数
    }
    cout << a << endl;
    node b[1000];
    int t = 0, k = 2;
    while (a != 1)                     //求质数因子
    {
        int num = 0;
        while (a % k == 0)
        {
            num++;
            a /= k;
        }
        if (num > 0)
        {
            b[t].val = k;
            b[t].num = num;
            t++;
        }
        k++;
    }
    sort(b, b + t, cmp);
    cout << b[0].val << ": " << b[0].num;
    for (int i = 1; i < t; i++)
    {
        cout << ", " << b[i].val << ": " << b[i].num;
    }
    return 0;
}

汉诺塔问题

判断回文字符串

bool isHWC(char* a,int len)
{
    int i=0,j=len-1;
    while(i<j)
    {
        if(a[i]!=a[j])return false;
        i++;
        j--;
    }
    return true;
}

判断是否为质数

bool isPrime(int a)
{
    if(a<2)return false;
    if(a<4)return true;
    if(a%2==0)return false;
    for(int i=3;i*i<=a;i+=2)
        if(a%i==0)
            return false;
    return true;
}

判断是否为水仙花数

bool isSXH(int a)
{
    int tmp=a;
    int num=0;
    int sum=0;
    while(tmp!=0){
        tmp/=10;
        num++;
    }
    tmp=a;
    while(a!=0){
        int t=a%10;
        int d=pow(t,num);
        sum+=d;
        a/=10;
    }
    return sum==tmp;
}

递归求n

long fac(int n)
{
    long f;
    if(n<0)
    {
        cout<<"n<0,data error!"<<endl;
        f=-1;
    }
    else if(n==0||n==1) f=1;
    else f=fac(n-1)*n;
    return f;
}