演算法筆記 ① 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題庫

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