2023年8月23日

#include <頭文件>

cstdio 有兩個(gè)函數(shù) printf，scanf 用于輸出和輸入

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

iostream 有 cin 讀入，cout 輸出

using namespace std;

使用了std命名空間，cin、cout定義在該命名空間中，不引入空間會(huì)找不到導(dǎo)致出錯(cuò)

int main()

函數(shù)執(zhí)行入口

基本類型

a+b

?所有 cout、cin 都能用 scanf、printf 替換，但反過來，由于cout、cin效率可能較低會(huì)導(dǎo)致超時(shí)

? printf %c 會(huì)讀入空格跟回車，需要手動(dòng)加一個(gè)空格跟回車；cin 不會(huì)讀入空格跟回車

#include <iostream>

using namespace std;

int main() {
    int a, b;  // ^ 定義兩個(gè)變量

    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++ 中取?？辞懊娴臄?shù)，如果負(fù)數(shù)則負(fù)數(shù)；而在Lua中取模的結(jié)果不可能為負(fù)數(shù)

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

類型轉(zhuǎn)換

float , double 轉(zhuǎn) int 下取整 ；int 轉(zhuǎn) char 整數(shù)取ASCII表；

char類型跟int類型運(yùn)算，結(jié)果是int類型；int類型與float型運(yùn)算會(huì)變成float型

隱性類型轉(zhuǎn)換：把精度低的類型轉(zhuǎn)換成另外一個(gè)精度高的類型

604

604. 圓的面積 - AcWing題庫(kù)

題目要求保留四位小數(shù)，考慮到float有效數(shù)字位只有6~7位，可能出現(xiàn)精度不準(zhǔn)確，故改用 double（未來題目看到浮點(diǎn)數(shù)也優(yōu)先使用double）

#include <cstdio>

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

653

653. 鈔票 - AcWing題庫(kù)

#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題庫(kù)

由于隱性類型轉(zhuǎn)換，結(jié)果為double，用%d表示數(shù)字不正確，需要用%lf

#include <cstdio>

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

618

618. 燃料消耗 - AcWing題庫(kù)

看數(shù)據(jù)范圍，最大可以到 10 ^ 14 次方遠(yuǎn)遠(yuǎn)大于 2 ^ 31，需要改用 double（8字節(jié)）

#include <cstdio>

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

656

656. 鈔票和硬幣 - AcWing題庫(kù)

一開始想用兩個(gè)整數(shù)讀整數(shù)跟小數(shù)（%d.%d），但小數(shù)位輸入可能是 .1 或 .01，讀出來都是1，不能處理，只能按浮點(diǎn)數(shù)來讀

#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題庫(kù)

多注意題目意思，如果...否則...，而不是如果、否則兩種情況都輸出

#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題庫(kù)

容易忘記最后 2 * a 的括號(hào)，導(dǎo)致先除后乘

#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日

讀入個(gè)數(shù)未知

讀入的個(gè)數(shù)未知時(shí)，可以用while(cin >> x)或while(scanf("%d", &x) != -1)或while(~scanf("%d", &x))來輸入。
如果輸入的最后一個(gè)為0且該0不處理，輸入語句可以用while(cin >> x && x)或while(cin >> x, x)，逗號(hào)表達(dá)式取最后一個(gè)值。

714

714. 連續(xù)奇數(shù)的和 1 - AcWing題庫(kù)

algorithm 函數(shù)庫(kù)的使用 ， % 相關(guān)的概念

#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. 完全數(shù) - AcWing題庫(kù)

設(shè)一個(gè)公約數(shù) d 那么另一個(gè)公約數(shù) x / d ， d <= x/d 得 d <= 根號(hào)x；另外還要考慮1的特殊情況。

AcWing 726. 質(zhì)數(shù) - 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 庫(kù)中，用于翻轉(zhuǎn)數(shù)組。涉及題目（翻轉(zhuǎn)整個(gè)，然后兩邊各自再翻轉(zhuǎn)）

memset

在 cstring 庫(kù)中，用于數(shù)組的初始化，速度比循環(huán)初始化要快。參數(shù)是數(shù)組指針，值（字節(jié)），長(zhǎng)度（字節(jié)）

memset(a,-1,sizeof a)

memcpy

在 cstring 庫(kù)中，用于復(fù)制數(shù)組。參數(shù)是目標(biāo)數(shù)組指針，被復(fù)制數(shù)組指針，長(zhǎng)度（字節(jié)）

753

753. 平方矩陣 I - AcWing題庫(kù)

技巧，需要看各個(gè)格子距離上下左右邊的最短距離。下面兩道也是技巧性題目

#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題庫(kù)

#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題庫(kù)

#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題庫(kù)

涉及到狀態(tài)的轉(zhuǎn)變，邏輯題

解題法-1 傳統(tǒng)邏輯解題

#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 將移動(dòng)方式保存到數(shù)組中

#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;
    // 每一個(gè)點(diǎn)都會(huì)走過一遍，算次數(shù)即可
    for (int k = 1, x = 0, y = 0; k <= m * n; k++) {
        res[x][y] = k;
        // 先看看新坐標(biāo)
        int a = x + dx[mode];
        int b = y + dy[mode];
        // 如果新坐標(biāo)不行就更新狀態(tài)并重新計(jì)算坐標(biāo)
        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回車去除方法

if(s[strlen(s)-1]=='\n')
    s[strlen(s)-1]=0;

fgets

默認(rèn)讀入字符串遇到空格就會(huì)停止。

fgets用于讀入一整行，參數(shù)為字符數(shù)組地址、最大讀多少字符、從哪讀，會(huì)讀入最后的回車符

fgets(s,100000,stdin);

cin

cin.getline用于讀入一整行，參數(shù)為字符數(shù)組地址、最大讀多少字符

cin.getline(s,1000);

getline

getline用于string類型讀入一整行

getline(cin,s);

puts

puts 輸出字符數(shù)組，包括換行符

puts(s);

cstring 庫(kù)函數(shù)

庫(kù)里有 strlen，strcmp 、strcpy 與 memcpy 類似

strlen(s); //  只計(jì)算字符串的元素，\0不計(jì)入其中
strcmp(a,b); // 字典序比較，小于返回-1（可能其他負(fù)數(shù)），等于返回0，大于返回1（可能其他正數(shù)） 
strcpy(a,b); // 把b復(fù)制給a

兩層循環(huán)優(yōu)化

在這種循環(huán)下，每次循環(huán) strlen(s) 都要執(zhí)行一遍，是兩層循環(huán)。

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

改成

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

或直接

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

80%的情況用string處理

c++ string 的簡(jiǎn)單用法_c++ string sprintf_ddancoo的博客-CSDN博客

string s1; // 默認(rèn)的空字符串
string s2 = s1; // s2是s1的副本
string s3 = "hiya"; // s3是該字符串字面值的副本
string s4(10,'c');  // s4的內(nèi)容是 ccccc

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

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

cout << s3.size() << endl;  // 數(shù)組長(zhǎng)度，O(1)復(fù)雜度

// 支持比較運(yùn)算符，相加
string s3 = s3 + s4;
s3 += s4;

/* 當(dāng)把string對(duì)象和字符字面值及字符串字面值混在一條語句中使用時(shí)，
必須確保每個(gè)加法運(yùn)算符的兩側(cè)的運(yùn)算對(duì)象至少有一個(gè)是string*/
s3 = s3 + " is great!" + '!'; // 這里不能用 +=
// 加法運(yùn)算符兩邊必須有一個(gè) string 類型

// 遍歷 string
for (char c : s) cout << c << endl;  // 等價(jià)于 for 循環(huán)體里 char c = str[i]

// 引用符號(hào)（可以改變 c 的值）
for (char &c : s)
    
// 讓編譯器去猜類型
auto s = "Hello World!" // char[]
for (auto c : s)

裁剪字符串

使用 string類型的 substr 函數(shù)

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

764 輸出字符串 ??

764. 輸出字符串 - AcWing題庫(kù)

簡(jiǎn)單，記得給b加結(jié)束符

c++string的輸出異常_c++ mexfunction string 沒有輸出-CSDN博客

其中的s1+='a',就可以在s1初始為空白的情況下往后追加字符,并且擴(kuò)充他的size,所以可以正確輸出

以前使用string的時(shí)候只是把它當(dāng)做字符數(shù)組來用,卻沒有去深入了解string這個(gè)東西,才會(huì)導(dǎo)致今天弄了這么大的麻煩,以后要長(zhǎng)記性

#include <cstdio>
#include <iostream>

using namespace std;

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

770 sstream 庫(kù)

AcWing 770. 單詞替換 - AcWing

不用庫(kù)的話，判斷空格位置，比較麻煩

#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;
}

用庫(kù)的話，把讀入的字符串再當(dāng)成一個(gè)流（類似于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 ? 第一類雙指針?biāo)惴?/h3>

771. 字符串中最長(zhǎng)的連續(xù)出現(xiàn)的字符 - AcWing題庫(kù)

#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;
            }
            // IMPORTANT
            i = j - 1;  // i 還會(huì)再++一次
        }
        cout << max_char << " " << max_count << endl;
    }
    return 0;
}

774 back()、pop_back() ?

774. 最長(zhǎng)單詞 - AcWing題庫(kù)

#include <cstdio>
#include <iostream>

using namespace std;

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

這里還有一個(gè)思想是按詞處理而不是先讀入一整串再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題庫(kù)

#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題庫(kù)

#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;
}

也可以通過字符串移位的貪心算法實(shí)現(xiàn)

#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題庫(kù)

如何處理輸入的問題

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

s.find();    // 在字符串s上從前往后找
s.rfind();   // 從后往前

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    string s, s1, s2;
    getline(cin, s, ',');
    getline(cin, s1, ',');
    getline(cin, s2);

    int temp = s.find(s1);
    int ans = s.rfind(s2);
    if (temp == -1 || ans == -1) 
    {
        cout << -1 << endl; 
        return 0;
    }
    int len = ans - temp - s1.size();
    if (len < 0) cout << -1 << endl;
    else cout << len << endl;
    return 0;
}

779. 最長(zhǎng)公共字符串后綴 - AcWing題庫(kù)

這題沒難度

#include<bits/stdc++.h>
using namespace std;
int n;
string a[209];
int main(){
    while(cin>>n){
        if(n==0) return 0;
        for(int i=0;i<n;++i) cin>>a[i],reverse(a[i].begin(),a[i].end());
        sort(a,a+n);
        string v="";
        for(int i=0;i<a[0].length();++i){
            if(a[0][i]==a[n-1][i]) v=a[0][i]+v;
            else break;
        }
        cout<<v<<"\n";
    }
}

函數(shù)默認(rèn)參數(shù)

默認(rèn)值需要是后面連續(xù)的幾個(gè)參數(shù)，或全部都有默認(rèn)值

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

sizeof 數(shù)組問題

main函數(shù)顯示的是數(shù)組長(zhǎng)度（ 40字節(jié)），foo函數(shù)顯示的是指針的長(zhǎng)度（64位8字節(jié)）。

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

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

/*
40
8
*/

inline

加在函數(shù)定義前，相當(dāng)于函數(shù)展開，適用于函數(shù)調(diào)用次數(shù)小的情況。對(duì)遞歸函數(shù)無效

823 簡(jiǎn)單遞歸問題

821. 跳臺(tái)階 - AcWing題庫(kù)

822. 走方格 - AcWing題庫(kù)

823. 排列 - AcWing題庫(kù)

#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;  // ^ 規(guī)定:如果p是指針用->、是變量用.
    p2->next = p3;
    // IMPORTANT 頭結(jié)點(diǎn)：第一個(gè)結(jié)點(diǎn)的地址而不是值

    Node* head = p;
    for (Node* i = head; i; i = i->next) {
        cout << i->val << endl;
    }
    // 添加節(jié)點(diǎn)
    Node* u = new Node(4);
    u->next = p;
    head = u;
    for (Node* i = head; i; i = i->next) {
        cout << i->val << endl;
    }
    // ^ 鏈表刪除是指在遍歷時(shí)遍歷不到這個(gè)點(diǎn)
    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題庫(kù)

條件表達(dá)式腦筋急轉(zhuǎn)彎

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

28

28. 在O(1)時(shí)間刪除鏈表結(jié)點(diǎn) - AcWing題庫(kù)

class Solution {
   public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;    // 偽裝成下一個(gè)點(diǎn)
        node->next = node->next->next;  // 將node刪除（訪問不到）
        // *(node) = *(node->next);
    }
};

36 ?

36. 合并兩個(gè)排序的鏈表 - AcWing題庫(kù)

二路歸并，賦值從右往左

/**
 * 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 ?

87. 把字符串轉(zhuǎn)換成整數(shù) - AcWing題庫(kù)

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 循環(huán)均可修改為while減少代碼量 ?

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

35 ?

AcWing 35. 反轉(zhuǎn)鏈表 - 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. 兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn) - AcWing題庫(kù)

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. 刪除鏈表中重復(fù)的節(jié)點(diǎn) - AcWing題庫(kù)

/**
 * 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;
    }
};

因?yàn)锽可以由A推導(dǎo)出，又可以改為

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] 需要大量空間，用可變長(zhǎng)數(shù)組可以節(jié)省很多空間。結(jié)尾插入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();
    // 當(dāng)成指針來看，it 相當(dāng)于訪問 a[0]， [begin,end)
    // a.end() 最后位置的下一個(gè)位置
    // *a.begin() 取值 :star:
    for (int i = 0; i < a.size(); i++) {
    }
    for (auto i = a.begin(); i < a.end(); i++) {
    }
    for (int x : a) {
    }
    // a.front() 等價(jià)于 a[0] 等價(jià)于 *a.begin()
    // a.back() 等價(jià)于 a[a.size()-1]

    // star
    // a.push_back(4); 在數(shù)組最后添加元素 O(1)
    // a.pop_back(); 刪除末尾元素
    return 0;
}

queue

普通隊(duì)列取隊(duì)尾是 front()，優(yōu)先隊(duì)列取最大\最小是 top()

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

using namespace std;

int main() {
    queue<int> q;
    queue<double> a;
    struct Rec {
        int x, y;
        // 優(yōu)先隊(duì)列
        // 大根堆，自定義結(jié)構(gòu)體要重載小于號(hào)
        // 小根堆，重載大于號(hào)
        bool operator<(const Rec& t) const { return x < t.x; }
    };

    queue<Rec> c;

    // ^ 優(yōu)先隊(duì)列，每次優(yōu)先彈最大值，大根堆
    priority_queue<int> a;
    // ^ 小根堆
    priority_queue<int, vector<int>, greater<int>> b;

    priority_queue<pair<int, int>> b;
    // 普通隊(duì)列
    a.push(3);  // 隊(duì)尾插入元素
    a.pop();    // 隊(duì)頭彈出元素
    a.front();  // 返回隊(duì)頭元素
    a.back();   // 返回隊(duì)尾元素

    // 優(yōu)先隊(duì)列
    b.push(1);
    b.top();  // 取最大值
    b.pop();  // 刪除最大值
              // IMPORTANT 隊(duì)列、優(yōu)先隊(duì)列、棧沒有clear函數(shù)
              // 可以重新初始化
    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

在隊(duì)頭隊(duì)尾插入都是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;       // 元素不能重復(fù)
    multiset<int> b;  // 元素可以重復(fù)

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

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

    a.count(1);  // 存在x返回1，不存在返回0，如果是multiset則返回個(gè)數(shù)
    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

很長(zhǎng)的01二進(jìn)制串

#include <bitset>
#include <iostream>

using namespace std;

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

    a.set(3);    // 某位設(shè)為1
    a.reset(3);  // 某位設(shè)為0
    // 支持位運(yùn)算
    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;
}

與、或、取反、異或

& | ~ ^

常用二進(jìn)制操作 ?

求某一位數(shù)字（如下求第三位數(shù)字）

int i = a >> 2 & 1;

返回最后一個(gè)1 ?

a & (~a + 1) // 0000001000
    
// 又因?yàn)?-a 等同 ~a+1
a & -a

常用庫(kù)函數(shù) ?

#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是否應(yīng)該排在b的前面
    return a < b;
}
bool cmp2(Rec a, Rec b) {  // a是否應(yīng)該排在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);  // 第二個(gè)參數(shù)寫數(shù)組最后一個(gè)位置的下一個(gè)

    // ^ unique  :star:
    int m = unique(b, b + 5) - b;                    // 不同元素?cái)?shù)量個(gè)數(shù)
    int m = unique(a.begin(), a.end()) - a.begin();  // 不同元素?cái)?shù)量個(gè)數(shù) :star:
    a.erase(unique(a.begin(), a.end()), a.end());  // 把沒有用的部分刪掉

    // ^ random_shuffle
    srand(time(0));
    random_shuffle(a.begin(), a.end());  // 打亂數(shù)組

    // ^ sort
    sort(a.begin(), a.end());                  // 從小到大
    sort(a.begin(), a.end(), greater<int>());  // 從大到小 :star:
    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);  // 重載小于號(hào)

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

    return 0;
}

范圍遍歷

比for循環(huán)快一點(diǎn)點(diǎn)

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

68

68. 0到n-1中缺失的數(shù)字 - AcWing題庫(kù)

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. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面 - AcWing題庫(kù)

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. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列 - AcWing題庫(kù)

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的兩個(gè)數(shù)字 - AcWing題庫(kù)

使用哈希表，只需要遍歷一遍數(shù)組

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. 數(shù)字排列 - AcWing題庫(kù)

返回一個(gè)序列的下一個(gè)序列，如果是最大了返回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. 二進(jìn)制中1的個(gè)數(shù) - 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題庫(kù)

#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題庫(kù)文章來源地址http://www.zghlxwxcb.cn/news/detail-688804.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;
}

到了這里，關(guān)于C++算法之旅、04 基礎(chǔ)篇 | 第一章 基礎(chǔ)算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！