算法笔记 ① acwing C++基础语法 | 全课程内容

2023年8月23日

#include <头文件>

cstdio 有两个函数 printf，scanf 用于输出和输入

int : %d
float : %f
double : %lf
char : %c
long long : %lld

iostream 有 cin 读入，cout 输出

using namespace std;

使用了std命名空间，cin、cout定义在该命名空间中，不引入空间会找不到导致出错

int main()

函数执行入口

基本类型

a+b

⭐所有 cout、cin 都能用 scanf、printf 替换，但反过来，由于cout、cin效率可能较低会导致超时

⭐ printf %c 会读入空格跟回车，需要手动加一个空格跟回车；cin 不会读入空格跟回车

#include <iostream>

using namespace std;

int main() {
    int a, b;  // ^ 定义两个变量

    cin >> a >> b;  // ^ 输入（把cin里的值拿到a里面去、b里面去）
    cout << a + b << endl;  // ^ 输出

    return 0;
}

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    int a, b;

    scanf("%d%d", &a, &b);
    printf("%d %d\n", a + b, a * b);

    return 0;
}

%

C++ 中取模看前面的数，如果负数则负数；而在Lua中取模的结果不可能为负数

    cout << 5 % 2 << endl; // 1
    cout << -5 % 2 << endl; // -1

类型转换

float , double 转 int 下取整 ；int 转 char 整数取ASCII表；

char类型跟int类型运算，结果是int类型；int类型与float型运算会变成float型

隐性类型转换：把精度低的类型转换成另外一个精度高的类型

604

604. 圆的面积 - AcWing题库

题目要求保留四位小数，考虑到float有效数字位只有6~7位，可能出现精度不准确，故改用 double（未来题目看到浮点数也优先使用double）

#include <cstdio>

int main() {
    double r;
    scanf("%lf", &r);
    printf("A=%.4lf", 3.14159 * r * r);
    return 0;
}

653

653. 钞票 - AcWing题库

#include <cstdio>

int main() {
    int m;
    scanf("%d", &m);
    printf("%d\n", m);
    printf("%d nota(s) de R$ 100,00\n", m / 100);
    m %= 100;
    printf("%d nota(s) de R$ 50,00\n", m / 50);
    m %= 50;
    printf("%d nota(s) de R$ 20,00\n", m / 20);
    m %= 20;
    printf("%d nota(s) de R$ 10,00\n", m / 10);
    m %= 10;
    printf("%d nota(s) de R$ 5,00\n", m / 5);
    m %= 5;
    printf("%d nota(s) de R$ 2,00\n", m / 2);
    m %= 2;
    printf("%d nota(s) de R$ 1,00\n", m / 1);
    return 0;
}

617

617. 距离 - AcWing题库

由于隐性类型转换，结果为double，用%d表示数字不正确，需要用%lf

#include <cstdio>

int main() {
    int a;
    scanf("%d", &a);
    printf("%.0lf minutos", a / 30.0 * 60);
    return 0;
}

618

618. 燃料消耗 - AcWing题库

看数据范围，最大可以到 10 ^ 14 次方远远大于 2 ^ 31，需要改用 long（8字节）

#include <cstdio>

int main() {
    long a, b;
    scanf("%ld%ld", &a, &b);
    printf("%.3lf", a * b / 12.0);
    return 0;
}

656

656. 钞票和硬币 - AcWing题库

一开始想用两个整数读整数跟小数（%d.%d），但小数位输入可能是 .1 或 .01，读出来都是1，不能处理，只能按浮点数来读

#include <cstdio>

int main() {
    double n;
    int m;
    scanf("%lf", &n);
    m = (int)(n * 100);
    printf("NOTAS:\n");
    printf("%d nota(s) de R$ 100.00\n", m / 10000);
    m %= 10000;
    printf("%d nota(s) de R$ 50.00\n", m / 5000);
    m %= 5000;
    printf("%d nota(s) de R$ 20.00\n", m / 2000);
    m %= 2000;
    printf("%d nota(s) de R$ 10.00\n", m / 1000);
    m %= 1000;
    printf("%d nota(s) de R$ 5.00\n", m / 500);
    m %= 500;
    printf("%d nota(s) de R$ 2.00\n", m / 200);
    m %= 200;
    printf("MOEDAS:\n");
    printf("%d moeda(s) de R$ 1.00\n", m / 100);
    m %= 100;
    printf("%d moeda(s) de R$ 0.50\n", m / 50);
    m %= 50;
    printf("%d moeda(s) de R$ 0.25\n", m / 25);
    m %= 25;
    printf("%d moeda(s) de R$ 0.10\n", m / 10);
    m %= 10;
    printf("%d moeda(s) de R$ 0.05\n", m / 5);
    m %= 5;
    printf("%d moeda(s) de R$ 0.01\n", m / 1);
    return 0;
}

2023年8月24日

字符串的输入

#include <iostream>

using namespace std;

int main() {
    string a, b, c;
    cin >> a >> b >> c;

666

666. 三角形类型 - AcWing题库

多注意题目意思，如果...否则...，而不是如果、否则两种情况都输出

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    double a, b, c, tmp;
    cin >> a >> b >> c;
    if (b >= a && b >= c) {
        tmp = a;
        a = b;
        b = tmp;
    } else if (c >= a && c >= b) {
        tmp = c;
        c = a;
        a = tmp;
    }
    if (a >= b + c)
        cout << "NAO FORMA TRIANGULO" << endl;
    else {
        if (a * a == b * b + c * c) cout << "TRIANGULO RETANGULO" << endl;
        if (a * a > b * b + c * c) cout << "TRIANGULO OBTUSANGULO" << endl;
        if (a * a < b * b + c * c) cout << "TRIANGULO ACUTANGULO" << endl;
        if (a == b && a == c && b == c) cout << "TRIANGULO EQUILATERO" << endl;
        if (a == b && c != b || a == c && b != c || b == c && a != b)
            cout << "TRIANGULO ISOSCELES" << endl;
    }
    return 0;
}

658

658. 一元二次方程公式 - AcWing题库

容易忘记最后 2 * a 的括号，导致先除后乘

#include <cmath>
#include <cstdio>

int main() {
    double a, b, c;
    scanf("%lf%lf%lf", &a, &b, &c);
    if (b * b - 4 * a * c < 0 || a == 0) {
        printf("Impossivel calcular");
    } else {
        printf("R1 = %.5lf\n", (-b + sqrt(b * b - 4 * a * c)) / (2 * a));
        printf("R2 = %.5lf", (-b - sqrt(b * b - 4 * a * c)) / (2 * a));
    }
    return 0;
}

2023年8月25日

读入个数未知

读入的个数未知时，可以用while(cin >> x)或while(scanf("%d", &x) != -1)或while(~scanf("%d", &x))来输入。
如果输入的最后一个为0且该0不处理，输入语句可以用while(cin >> x && x)或while(cin >> x, x)，逗号表达式取最后一个值。

714

714. 连续奇数的和 1 - AcWing题库

algorithm 函数库的使用 ， % 相关的概念

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    int x, y;
    cin >> x >> y;
    if (x > y) {
        swap(x, y);
    }
    int total = 0;
    for (x++; x < y; x++) {
        if (abs(x) % 2 == 1) total += x;
    }
    cout << total;
    return 0;
}

725

725. 完全数 - AcWing题库

设一个公约数 d 那么另一个公约数 x / d ， d <= x/d 得 d <= 根号x；另外还要考虑1的特殊情况。

AcWing 726. 质数 - AcWing 这题同理

#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    int n, x;
    cin >> n;
    while (cin >> x, n--) {
        int sum = 0;
        for (int i = 1; i * i <= x; i++) {
            if (x % i == 0) {
                if (i < x) sum += i;
                if (x / i != i && x / i < x) sum += x / i;
            }
        }
        if (sum == x)
            cout << x << " is perfect" << endl;
        else
            cout << x << " is not perfect" << endl;
    }
    return 0;
}

2023年8月26日

reverse

在 alogorithm 库中，用于翻转数组。涉及题目（翻转整个，然后两边各自再翻转）

memset

在 cstring 库中，用于数组的初始化，速度比循环初始化要快。参数是数组指针，值（字节），长度（字节）

memset(a,-1,sizeof a)

memcpy

在 cstring 库中，用于复制数组。参数是目标数组指针，被复制数组指针，长度（字节）

753

753. 平方矩阵 I - AcWing题库

技巧，需要看各个格子距离上下左右边的最短距离。下面两道也是技巧性题目

#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    int n;
    while (cin >> n, n) {
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= n; k++) {
                cout << min(min(i, k), min(n + 1 - k, n + 1 - i)) << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

754

754. 平方矩阵 II - AcWing题库

#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    int n;
    while (cin >> n, n) {
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= n; k++) {
                cout << max(i - k + 1, k - i + 1) << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

755

755. 平方矩阵 III - AcWing题库

#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    long n, m[31] = {1};
    for (int i = 1; i < 31; i++) {
        m[i] = m[i - 1] * 2;
    }
    while (cin >> n, n) {
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= n; k++) {
                cout << m[i + k - 2] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

756 ⭐

756. 蛇形矩阵 - AcWing题库

涉及到状态的转变，逻辑题

解题法-1 传统逻辑解题

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

int main() {
    int a[101][101];
    memset(a, 0, sizeof a);
    int n, m;
    cin >> n >> m;
    int i = 0, k = 0;
    int c = 1;
    int mode = 1;
    while (i - 1 >= 0 && a[i - 1][k] == 0 || i + 1 < n && a[i + 1][k] == 0 ||
           k - 1 >= 0 && a[i][k - 1] == 0 || k + 1 < n && a[i][k + 1] == 0 ||
           a[i][k] == 0) {
        if (mode == 1) {
            a[i][k] = c++;
            if (k + 1 == m || a[i][k + 1] != 0) {
                mode = 2;
                i++;
            } else
                k++;
        } else if (mode == 2) {
            a[i][k] = c++;
            if (i + 1 == n || a[i + 1][k] != 0) {
                mode = 3;
                k--;
            } else
                i++;
        } else if (mode == 3) {
            a[i][k] = c++;
            if (k - 1 < 0 || a[i][k - 1] != 0) {
                mode = 4;
                i--;
            } else
                k--;
        } else {
            a[i][k] = c++;
            if (i - 1 < 0 || a[i - 1][k] != 0) {
                mode = 1;
                k++;
            } else
                i--;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < m; k++) {
            cout << a[i][k] << " ";
        }
        cout << endl;
    }
    return 0;
}

解题法-2 将移动方式保存到数组中

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

int res[101][101];

int main() {
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    int m, n;
    cin >> n >> m;
    int mode = 0;
    for (int k = 1, x = 0, y = 0; k <= m * n; k++) {
        res[x][y] = k;
        int a = x + dx[mode];
        int b = y + dy[mode];
        if (a < 0 || a >= n || b < 0 || b >= m || res[a][b]) {
            mode = (mode + 1) % 4;
            a = x + dx[mode];
            b = y + dy[mode];
        }
        x = a;
        y = b;
    }
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < m; k++) {
            cout << res[i][k] << " ";
        }
        cout << endl;
    }
    return 0;
}

2023年8月27日

fgets

默认读入字符串遇到空格就会停止。

fgets用于读入一整行，参数为字符数组地址、最大读多少字符、从哪读，会读入最后的回车符

fgets(s,100000,stdin);

cin

cin.getline用于读入一整行，参数为字符数组地址、最大读多少字符

cin.getline(s,1000);

getline

getline用于string类型读入一整行

getline(cin,s);

puts

puts 输出字符数组，包括换行符

puts(s);

cstring 库函数

库里有 strlen，strcmp 、strcpy 与 memcpy 类似

strlen(s); //  只计算字符串的元素，\0不计入其中
strcmp(a,b); // 字典序比较，小于返回-1（可能其他负数），等于返回0，大于返回1（可能其他正数） 
strcpy(a,b); // 把b复制给a

两层循环优化

在这种循环下，每次循环 strlen(s) 都要执行一遍，是两层循环。

for (int i = 0; i < strlen(s) ; i++)

改成

for (int i = 0, len=strlen(s) ; i < len; i++)

或直接

for (int i = 0; i < s[i]; i++)

80%的情况用string处理

string s1; // 默认的空字符串
string s2 = s1; // s2是s1的副本
string s3 = "hiya"; // s3是该字符串字面值的副本
string s4(10,'c');  // s4的内容是 ccccc

cin >> s1 >> s2;
// string 不能用scanf读但可以用printf输出
printf("%s\n",s1.c_str());
cout << s1 << s2;

cout << s1.empty() << endl;  // 布尔值返回 01
cout << s3.empty() << endl;  // 布尔值返回 0

cout << s3.size() << endl;  // 数组长度，O(1)复杂度

// 支持比较运算符，相加
string s3 = s3 + s4;
s3 += s4;
s3 = s3 + " is great!" + '!'; // 这里不能用 +=
// 加法运算符两边必须有一个 string 类型

// 遍历 string
for (char c : s) cout << c << endl;  // 等价于 for 循环体里 char c = str[i]

// 引用符号（可以改变 c 的值）
for (char &c : s)
    
// 让编译器去猜类型
auto s = "Hello World!" // char[]
for (auto c : s)

裁剪字符串

使用 string类型的 substr 函数

cout << a.substr(0, max_index + 1) + b + a.substr(max_index + 1)
             << endl;

764 勿忘结束符

764. 输出字符串 - AcWing题库

简单，但是容易忘记给b加结束符

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    string a, b;
    getline(cin, a);
    for (int i = 0; i < a.size(); i++) {
        b[i] = a[i] + a[(i + 1) % a.size()];
        cout << b[i];
    }
    b = b + '\0';
    cout << b;
    return 0;
}

770 sstream 库

AcWing 770. 单词替换 - AcWing

不用库的话，判断空格位置，比较麻烦

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

int main() {
    string s, a, b, word, res;
    getline(cin, s);
    cin >> a >> b;
    int index = 0;
    for (int i = 0; i <= s.size(); i++) {
        if (s[i] == ' ' || s[i] == 0) {
            if (strcmp(word.c_str(), a.c_str()) == 0) {
                res = res + b + ' ';
            } else
                res = res + word + ' ';
            word = "";
        } else
            word = word + s[i];
    }
    cout << res;
    return 0;
}

用库的话，把读入的字符串再当成一个流（类似于split操作了）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <sstream>

using namespace std;

int main() {
    string s, a, b, word, res;
    getline(cin, s);
    cin >> a >> b;

    stringstream ssin(s);
    string str;
    while (ssin >> str)
        if (str == a)
            cout << b << ' ';
        else
            cout << str << ' ';

    cout << res;
    return 0;
}

771 ⭐ 第一类双指针算法

771. 字符串中最长的连续出现的字符 - AcWing题库

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int max_count = 0;
        char max_char;
        string a;
        cin >> a;
        for (int i = 0; i < a.size(); i++) {
            int j = i;
            while (j < a.size() && a[i] == a[j]) j++;
            int diff = j - i;
            if (max_count < diff) {
                max_char = a[i];
                max_count = diff;
            }
            i = j - 1;  // i 还会再++一次
        }
        cout << max_char << " " << max_count << endl;
    }
    return 0;
}

774 back()、pop_back()

774. 最长单词 - AcWing题库

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    string word, s_max;
    // s.back() 获取最后一个字符 s.pop_back() 去掉最后一个字符
    while (cin >> word) {
        if (word.back() == '.') word.pop_back();
        if (word.size() > s_max.size()) s_max = word;
    }
    cout << s_max;
    return 0;
}

这里还有一个思想是按词处理而不是先读入一整串再sstream，类似下面的

AcWing 775. 倒排单词 - AcWing

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    string res, word;
    while (cin >> word) {
        res = word + " " + res;
    }
    cout << res;
    return 0;
}

776 ⭐

776. 字符串移位包含问题 - AcWing题库

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    if (b.size() > a.size()) swap(a, b);
    for (int i = 0; i < a.size(); i++) {
        a = a.substr(1) + a[0];
        int k = 0;
        for (int i = 0; i + b.size() <= a.size(); i++) {
            while (k < b.size() && a[i + k] == b[k]) k++;
            if (k == b.size()) {
                puts("true");
                return 0;
            } else
                k = 0;
        }
    }
    puts("false");
    return 0;
}

2023年8月30日

777

777. 字符串乘方 - AcWing题库

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    string s;
    while (cin >> s, s != ".") {
        for (int i = 1; i <= s.size(); i++) {
            if (s.size() % i != 0) continue;
            string a = s.substr(0, i);
            string res;
            int times = s.size() / i;
            for (int i = 1; i <= times; i++) {
                res += a;
            }
            if (res == s) {
                cout << times << endl;
                break;
            }
        }
    }
    return 0;
}

也可以通过字符串移位的贪心算法实现

#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    string s;
    while (cin >> s, s != ".") {
        string res = s;
        for (int i = 1; i <= res.size(); i++) {
            res = res.substr(1) + res[0];
            if (res == s) {
                cout << res.size() / i << endl;
                break;
            }
        }
    }
    return 0;
}

778

778. 字符串最大跨距 - AcWing题库

如何处理输入的问题

    string s, s1, s2;
    char c;
    while (cin >> c, c != ',') s += c;
    while (cin >> c, c != ',') s1 += c;
    while (cin >> c) s2 += c;

779. 最长公共字符串后缀 - AcWing题库

这题没难度

函数默认参数

默认值需要是后面连续的几个参数，或全部都有默认值

void foo(int a,int b = 5,int c = 10)

sizeof 数组问题

main函数显示的是数组长度（ 40字节），foo函数显示的是指针的长度（64位8字节）。

void foo(int b[]){
    cout << sizeof b;
}

int main(){
    int a[10];
    cout << sizeof a << endl;
    foo(a);
    return 0;
}

/*
40
8
*/

inline

加在函数定义前，相当于函数展开，适用于函数调用次数小的情况。对递归函数无效

823 简单递归问题

821. 跳台阶 - AcWing题库

822. 走方格 - AcWing题库

823. 排列 - AcWing题库

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 10;

int n;

int pl(int index, int a[], bool h[]) {
    if (index == n) {
        for (int i = 0; i < n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    } else
        for (int i = 1; i <= n; i++) {
            if (!h[i]) {
                h[i] = 1;
                a[index] = i;
                pl(index + 1, a, h);
                h[i] = 0;
            }
        }
}

int main() {
    cin >> n;
    int a[10] = {0};
    bool h[10] = {0};
    pl(0, a, h);
    return 0;
}

指针、引用

int a = 3;
int* p = &a; // 指针
int& p2 = a;  // 引用、别名

链表与指针 ⭐

#include <iostream>

using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int _val) : val(_val), next(NULL) {}
};

int main() {
    Node* p = new Node(1);  // ^ 加new返回地址，不加new返回变量
    auto p2 = new Node(2);
    auto p3 = new Node(3);
    p->next = p2;  // ^ 规定:如果p是指针用->、是变量用.
    p2->next = p3;
    // IMPORTANT 头结点：第一个结点的地址而不是值

    Node* head = p;
    for (Node* i = head; i; i = i->next) {
        cout << i->val << endl;
    }
    // 添加节点
    Node* u = new Node(4);
    u->next = p;
    head = u;
    for (Node* i = head; i; i = i->next) {
        cout << i->val << endl;
    }
    // ^ 链表删除是指在遍历时遍历不到这个点
    head->next = head->next->next;
    for (Node* i = head; i; i = i->next) {
        cout << i->val << endl;
    }
    return 0;
}

84

84. 求1+2+…+n - AcWing题库

条件表达式脑筋急转弯

class Solution {
   public:
    int getSum(int n) {
        int res = n;
        n > 0 && (res += getSum(n - 1));
        return res;
    }
};

28

28. 在O(1)时间删除链表结点 - AcWing题库

class Solution {
   public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;    // 伪装成下一个点
        node->next = node->next->next;  // 将node删除（访问不到）
        // *(node) = *(node->next);
    }
};

36 ⭐

36. 合并两个排序的链表 - AcWing题库

二路归并，赋值从右往左

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
   public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1), tail = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail = tail->next = l1;
                l1 = l1->next;
            } else {
                tail = tail->next = l2;
                l2 = l2->next;
            }
        }
        if (l1)
            tail->next = l1;
        else
            tail->next = l2;
        return dummy->next;
    }
};

87 ⭐

AcWing 87. 把字符串转换成整数 - AcWing

class Solution {
   public:
    int strToInt(string str) {
        int i = 0, flag = 1;
        while (i < str.size() && str[i] == ' ') i++;
        if (i == str.size())
            return 0;
        else if (str[i] == '-') {
            flag = -1;
            i++;
        } else if (str[i] == '+') {
            flag = 1;
            i++;
        }
        long long sum = 0;
        while (i < str.size() && str[i] >= '0' && str[i] <= '9') {
            sum *= 10;
            sum += str[i] - '0';
            i++;
            if (sum * flag > INT_MAX) {
                return INT_MAX;
            } else if (sum * flag < INT_MIN)
                return INT_MIN;
        }
        sum = sum * flag;
        return (int)sum;
    }
};

        for (; i < str.size(); i++) {
            if (str[i] != ' ') break;
        }

for 循环均可修改为while减少代码量

        while (i < str.size() && str[i] == ' ') i++;

35 ⭐

AcWing 35. 反转链表 - AcWing

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
   public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;  // ^ 特殊情况
        auto A = head;
        auto B = head->next;
        A->next = NULL;
        while (B) {
            auto C = B->next;
            B->next = A;
            A = B, B = C;
        }
        return A;
    }
};

递归写法

class Solution {
   public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;  // ^ 特殊情况
        auto tail = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return tail;
    }
};

66 ⭐⭐

66. 两个链表的第一个公共结点 - AcWing题库

class Solution {
   public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto A = headA, B = headB;
        while (A != B) {
            if (A)
                A = A->next;
            else
                A = headB;
            if (B)
                B = B->next;
            else
                B = headA;
        }
        return A;
    }
};

29

29. 删除链表中重复的节点 - AcWing题库

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
   public:
    ListNode* deleteDuplication(ListNode* head) {
        if (!head || !head->next) return head;
        auto tmp = new ListNode(-1);
        tmp->next = head;
        auto A = tmp, B = head;
        while (B && B->next) {
            auto C = B->next;
            if (C->val == B->val) {
                while (C && C->val == B->val) C = C->next;
                A->next = C;
                B = C;
            } else {
                A = B;
                B = B->next;
            }
        }
        return tmp->next;
    }
};

因为B可以由A推导出，又可以改为

class Solution {
   public:
    ListNode* deleteDuplication(ListNode* head) {
        auto tmp = new ListNode(-1);
        tmp->next = head;
        auto A = tmp;
        while (A->next) {
            auto C = A->next;
            while (C->next && A->next->val == C->next->val) C = C->next;
            if (C != A->next)
                A->next = C->next;
            else
                A = A->next;
        }
        return tmp->next;
    }
};

vector

int q[100000][100000] 需要大量空间，用可变长数组可以节省很多空间。结尾插入O(1)，开头插入O(n)，自带比较，按字典序比

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> a({1, 2, 3});
    vector<int> b[233];
    struct Rec {
        int x, y;
    };

    vector<Rec> c;

    // a.size();
    // a.empty();
    // a.clear();

    vector<int>::iterator it = a.begin();
    // 当成指针来看，it 相当于访问 a[0]， [begin,end)
    // a.end() 最后位置的下一个位置
    // *a.begin() 取值
    for (int i = 0; i < a.size(); i++) {
    }
    for (auto i = a.begin(); i < a.end(); i++) {
    }
    for (int x : a) {
    }
    // a.front() 等价于 a[0] 等价于 *a.begin()
    // a.back() 等价于 a[a.size()-1]

    // a.pushback(4); 在数组最后添加元素 O(1)
    // a.pop_back(); 删除末尾元素
    return 0;
}

queue

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    queue<int> q;
    queue<double> a;
    struct Rec {
        int x, y;
        // 优先队列，大根堆，自定义结构体要重载小于号
        // 小根堆，重载大于号
        bool operator<(const Rec& t) const { return x < t.x; }
    };

    queue<Rec> c;

    // ^ 优先队列，每次优先弹最大值，大根堆
    priority_queue<int> a;
    // ^ 小根堆
    priority_queue<int, vector<int>, greater<int>> b;

    priority_queue<pair<int, int>> b;
    // 普通队列
    a.push(3);  // 队尾插入元素
    a.pop();    // 队头弹出元素
    a.front();  // 返回队头元素
    a.back();   // 返回队尾元素

    // 优先队列
    b.push(1);
    b.top();  // 取最大值
    b.pop();  // 删除最大值
              // IMPORTANT 队列、优先队列、栈没有clear函数
              // 可以重新初始化
    q = queue<int>();
    return 0;
}

stack

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> stk;
    stk.push(1);
    stk.top();
    stk.pop(); // 弹出但不返回

    return 0;
}

deque

在队头队尾插入都是O(1)

#include <deque>
#include <iostream>

using namespace std;

int main() {
    deque<int> a;
    a.begin(), a.end();
    a.front(), a.back();
    a.push_back(1), a.push_front(1);
    a[0];
    a.pop_back(), a.pop_front();

    a.clear();

    return 0;
}

set

红黑树

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> a;       // 元素不能重复
    multiset<int> b;  // 元素可以重复

    set<int>::iterator it = a.begin();
    it++;
    it--;  // 前驱、后继
    ++it, --it;
    a.end();
    a.insert(1);
    a.find(1);  // 返回迭代器，找不到返回 a.end() // 判断x在a中是否存在

    a.lower_bound(1);  // IMPORTANT 找到大于等于x的最小的元素的迭代器
    a.upper_bound(1);  // 找到大于x的最小的元素的迭代器

    a.count(1);  // 存在x返回1，不存在返回0，如果是multiset则返回个数
    a.erase(1);  // 删除
    //
    struct Rec {
        int x, y;
        bool operator<(const Rec& t) const { return x < t.x; }
    };

    set<Rec> c;  // size/empty/clear/ 也有迭代器

    return 0;
}

map

#include <iostream>
#include <map>
#include <vector>

using namespace std;

int main() {
    map<int, int> a;
    a[1] = 2;
    a[10000000] = 3;
    a.insert({100, 1});
    cout << a[10000000] << endl;
    map<string, vector<int>> b;
    b["test"] = vector<int>({1, 2, 3, 4});
    b.insert({"t", {}});
    b.find("t");
    return 0;
}

unordered

unordered_set使用哈希表

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    unordered_set<int> a;       // 比set效率高些，但不支持二分
    unordered_multiset<int> b;  // 比set效率高些，但不支持二分

    unordered_map<int, int> c;  // 比map效率高些，但不支持二分
    return 0;
}

bitset

很长的01二进制串

#include <bitset>
#include <iostream>

using namespace std;

int main() {
    bitset<1000> a, b;
    a[0] = 1;
    a[1] = 1;

    a.set(3);    // 某位设为1
    a.reset(3);  // 某位设为0
    // 支持位运算
    a &= b;

    return 0;
}

pair

#include <bitset>
#include <iostream>

using namespace std;

int main() {
    pair<int, string> a;
    a = {3, "test"};

    cout << a.first << " " << a.second << endl;

    // 老版本 make_pair(4,"abc")
    // pair 支持比较，先比较first然后比较second

    return 0;
}

与、或、取反、异或

& | ~ ^

常用二进制操作 ⭐

求某一位数字

int i = a >> 2 & 1;

返回最后一个1

a & (~a + 1) // 0000001000
// 又因为 -a 等同 ~a+1
a & -a

常用库函数 ⭐

#include <algorithm>
#include <ctime>
#include <iostream>
#include <vector>

using namespace std;
struct Rec {
    int x, y;
    bool operator<(const Rec &t) const { return x < t.x; }
} rec[5];

bool cmp(int a, int b) {  // a是否应该排在b的前面
    return a < b;
}
bool cmp2(Rec a, Rec b) {  // a是否应该排在b的前面
    return a.x < b.x;
}

int main() {
    // ^ reverse
    vector<int> a({1, 2, 3, 4});
    reverse(a.begin(), a.end());
    for (int x : a) cout << x << ' ';
    cout << endl;

    int b[] = {1, 2, 2, 4, 5};
    reverse(b, b + 5);  // 第二个参数写数组最后一个位置的下一个

    // ^ unique
    int m = unique(b, b + 5) - b;                    // 不同元素数量个数
    int m = unique(a.begin(), a.end()) - a.begin();  // 不同元素数量个数
    a.erase(unique(a.begin(), a.end()), a.end());  // 把没有用的部分删掉

    // ^ random_shuffle
    srand(time(0));
    random_shuffle(a.begin(), a.end());  // 打乱数组

    // ^ sort
    sort(a.begin(), a.end());                  // 从小到大
    sort(a.begin(), a.end(), greater<int>());  // 从大到小
    sort(a.begin(), a.end(), cmp);

    for (int i = 0; i < 5; i++) {
        rec[i].x = -i;
        rec[i].y = i;
    }
    sort(rec, rec + 5, cmp2);
    sort(rec, rec + 5);  // 重载小于号

    // ^ lower_bound/upper_bound
    int *p = lower_bound(b, b + 5, 3);  // 返回迭代器
    int *p = upper_bound(b, b + 5, 3);  // 返回迭代器

    return 0;
}

范围遍历

比for循环快一点点

    int cnt = 0;
    for (int x : nums) {
        if (x == k) cnt++;
    }

68

AcWing 68. 0到n-1中缺失的数字 - AcWing

class Solution {
   public:
    int getMissingNumber(vector<int>& nums) {
        unordered_set<int> s;
        for (int i = 0; i <= nums.size(); i++) s.insert(i);
        for (auto x : nums) s.erase(x);
        return *s.begin();
    }
};

双指针法 ⭐ 32

32. 调整数组顺序使奇数位于偶数前面 - AcWing题库

class Solution {
   public:
    void reOrderArray(vector<int> &array) {
        int i = 0, j = array.size() - 1;
        while (i < j) {
            while (i < j && array[i] % 2) i++;
            while (i < j && array[j] % 2 == 0) j--;
            if (i < j) swap(array[i], array[j]);
        }
    }
};

2023年8月31日

20

20. 用两个栈实现队列 - AcWing题库

class MyQueue {
   public:
    /** Initialize your data structure here. */
    stack<int> a, b;

    MyQueue() {}

    /** Push element x to the back of queue. */
    void push(int x) { a.push(x); }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while (a.size() > 1) b.push(a.top()), a.pop();
        int t = a.top();
        a.pop();
        while (b.size()) a.push(b.top()), b.pop();
        return t;
    }

    /** Get the front element. */
    int peek() {
        while (a.size() > 1) b.push(a.top()), a.pop();
        int t = a.top();
        while (b.size()) a.push(b.top()), b.pop();
        return t;
    }

    /** Returns whether the queue is empty. */
    bool empty() { return a.empty(); }
};

75

75. 和为S的两个数字 - AcWing题库

使用哈希表，只需要遍历一遍数组

class Solution {
   public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_set<int> s;
        for (auto x : nums) {
            if (s.count(target - x)) return {target - x, x};

            s.insert(x);
        }
    }
};

51 next_permutation ⭐

51. 数字排列 - AcWing题库

返回一个序列的下一个序列，如果是最大了返回false

class Solution {
   public:
    vector<vector<int>> permutation(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        do {
            res.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return res;
    }
};

26 lowbit

AcWing 26. 二进制中1的个数 - AcWing

class Solution {
   public:
    int NumberOf1(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if (n >> i & 1) res++;
        }
        return res;
    }
};

class Solution {
   public:
    int NumberOf1(int n) {
        int res = 0;
        while (n) {
            n -= n & -n;
            res++;
        }
        return res;
    }
};

第二种方法快一些

420 火星人 ⭐⭐

420. 火星人 - AcWing题库

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 10010;
int n, m;
int q[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> q[i];
    while (m--) next_permutation(q, q + n);
    for (int i = 0; i < n; i++) cout << q[i] << " ";
    return 0;
}

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 10010;
int n, m;
int q[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> q[i];
    while (m--) {
        int k = n - 1;
        while (q[k - 1] > q[k]) k--;
        int min_max = k;
        for (int i = k; i < n; i++) {
            if (q[min_max] > q[i] && q[i] > q[k - 1]) min_max = i;
        }
        swap(q[k - 1], q[min_max]);
        reverse(q + k, q + n);
    }
    for (int i = 0; i < n; i++) cout << q[i] << " ";
    return 0;
}

862

862. 三元组排序 - AcWing题库文章来源地址https://www.toymoban.com/news/detail-683823.html

#include <algorithm>
#include <iostream>

using namespace std;

struct Data {
    int x;
    double y;
    string z;

    bool operator<(const Data &t) const { return x < t.x; }
} a[10010];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y >> a[i].z;
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        printf("%d %.2lf %s\n", a[i].x, a[i].y, a[i].z.c_str());
    }
    return 0;
}

到了这里，关于算法笔记 ① acwing C++基础语法 | 全课程内容的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！