C++ 算法题学习总结#

1
// 如果是2的幂，不断除以2最后会得到1
2
unsigned long long temp = x;
3

4
// 特判0
5
if(x == 0){
6
    cout << "NO";
7
    return;
8
}
9

10
// 不断除以2
11
while(temp % 2 == 0){
12
    temp /= 2;
13
}
14

15
// 如果最后等于1，说明原数是2的幂
16
if(temp == 1){
17
    cout << "YES";
18
} else {
19
    cout << "NO";
20
}

1
if(x > 0 && (x & (x - 1)) == 0){
2
    cout << "YES";
3
} else {
4
    cout << "NO";
5
}

1
1  = 0001  (2^0)
2
2  = 0010  (2^1)
3
4  = 0100  (2^2)
4
8  = 1000  (2^3)
5
16 = 10000 (2^4)

1
x = 8 = 1000
2
x-1 = 7 = 0111
3

4
x   = 1000
5
x-1 = 0111
6
-----------
7
x & (x-1) = 0000  ← 如果x是2的幂，结果是0！

1
x = 12 = 1100  (不是2的幂，有两个1)
2
x-1 = 11 = 1011
3

4
x   = 1100
5
x-1 = 1011
6
-----------
7
x & (x-1) = 1000 ≠ 0  ← 不是2的幂

1
while(cin >> n){
2
    // 处理
3
}

1
string line;
2
getline(cin, line);
3
stringstream ss(line);
4
int num;
5
while(ss >> num){
6
    // 处理每个数字
7
}

1
int n;
2
cin >> n;
3
cin.ignore();  // 忽略换行符！
4
string line;
5
getline(cin, line);

1
⌈a/b⌉ = (a + b - 1) / b

1
bool isPrime(int x){
2
    if(x < 2) return false;
3
    for(int i = 2; i*i <= x; i++){  // 只检查到√x
4
        if(x % i == 0) return false;
5
    }
6
    return true;
7
}

1
bool isLeap(int year){
2
    return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
3
}

1
// 方法1: 逐位检查
2
int count = 0;
3
while(n > 0){
4
    if(n % 2 == 1) count++;
5
    n /= 2;
6
}
7

8
// 方法2: 位运算
9
while(n > 0){
10
    count += n & 1;
11
    n >>= 1;
12
}
13

14
// 方法3: 内置函数（最简单）
15
count = __builtin_popcountll(n);

1
二进制最后一位决定奇偶性
2
奇数 % 2 = 1（最后一位是1）
3
偶数 % 2 = 0（最后一位是0）

1
// 方法1: 循环除2（易理解）
2
unsigned long long temp = x;
3
if(x == 0) return false;
4
while(temp % 2 == 0){
5
    temp /= 2;
6
}
7
return temp == 1;
8

9
// 方法2: 位运算（最优雅）
10
return x > 0 && (x & (x - 1)) == 0;

1
8 = 1000
2
7 = 0111
3
8 & 7 = 0000 ✓ 是2的幂
4

5
12 = 1100
6
11 = 1011
7
12 & 11 = 1000 ≠ 0 ✗ 不是2的幂

1
56 → 5+6=11 → 1+1=2

1
long long digitSum(long long m) {
2
    if (m <= 9) return m;  // 递归出口
3

4
    long long sum = 0;
5
    while (m > 0) {
6
        sum += m % 10;
7
        m /= 10;
8
    }
9

10
    return digitSum(sum);  // 递归调用
11
}

1
long long digitalRoot(long long m) {
2
    if (m == 0) return 0;
3
    if (m % 9 == 0) return 9;
4
    return m % 9;
5
}
6

7
// 更简洁写法
8
return (m == 0) ? 0 : ((m % 9 == 0) ? 9 : m % 9);

1
56 % 9 = 2 → 答案2 ✓
2
12 % 9 = 3 → 答案3 ✓
3
18 % 9 = 0 → 答案9（特判）✓

1
seconds = hours * 3600 + minutes * 60 + secs;

1
hours = seconds / 3600;
2
minutes = (seconds % 3600) / 60;
3
secs = seconds % 60;

1
// 方法1: 手动反转（最推荐）
2
for(int i = s.size()-1; i >= 0; i--){
3
    cout << s[i];
4
}
5

6
// 方法2: 使用reverse
7
reverse(s.begin(), s.end());
8
cout << s;

1
string s = "hello";
2

3
// 1. 删除单个字符
4
s.erase(1);        // 删除位置1及之后的所有字符 → "h"
5

6
// 2. 删除指定位置的n个字符
7
s.erase(1, 2);     // 从位置1开始删除2个字符
8
                   // "hello" → "hlo"
9

10
// 3. 删除最后一个字符
11
s.erase(s.length() - 1);
12
// 或者
13
s.pop_back();      // C++11，更简洁

1
string s = "abcdefg";
2

3
// erase(pos, len)
4
// pos: 起始位置（从0开始）
5
// len: 删除的字符个数（可选，默认删除到末尾）
6

7
s.erase(2, 3);     // 从位置2删除3个字符
8
                   // "abcdefg" → "abfg"
9
                   // 删除了 c d e
10

11
s.erase(1);        // 从位置1删除到末尾
12
                   // "abcdefg" → "a"

1
// 泡泡合并：oo → O，OO → 爆掉
2
for (int i = 0; i < s.length() - 1; ) {
3
    if (s[i] == 'o' && s[i+1] == 'o') {
4
        s[i] = 'O';
5
        s.erase(i + 1, 1);  // 删除下一个字符
6
        // 不移动i，继续检查当前位置
7
    } else if (s[i] == 'O' && s[i+1] == 'O') {
8
        s.erase(i, 2);      // 删除2个字符
9
        // 不移动i
10
    } else {
11
        i++;
12
    }
13
}

1
string s = "a1b2c3";
2
// 删除所有数字
3
for (int i = 0; i < s.length(); ) {
4
    if (s[i] >= '0' && s[i] <= '9') {
5
        s.erase(i, 1);
6
        // 不移动i
7
    } else {
8
        i++;
9
    }
10
}
11
// 结果: "abc"

1
string s = "aabbcc";
2
for (int i = 0; i < s.length() - 1; ) {
3
    if (s[i] == s[i+1]) {
4
        s.erase(i+1, 1);
5
    } else {
6
        i++;
7
    }
8
}
9
// 结果: "abc"

1
string s = "hello";
2

3
// 长度
4
s.length()  或  s.size()
5

6
// 添加字符
7
s.push_back('!');        // "hello!"
8
s += '!';                // "hello!"
9
s.append("world");       // "hello!world"
10

11
// 删除字符
12
s.pop_back();            // 删除最后一个
13
s.erase(1, 2);           // 删除指定位置
14

15
// 查找
16
s.find("lo");            // 返回3（位置）
17
s.find('e');             // 返回1
18
if (s.find("xyz") == string::npos) {
19
    // 没找到
20
}
21

22
// 截取子串
23
s.substr(1, 3);          // 从位置1开始截取3个字符 → "ell"
24
s.substr(2);             // 从位置2到末尾 → "llo"
25

26
// 替换
27
s.replace(1, 2, "XX");   // 从位置1开始的2个字符替换成"XX"
28
                         // "hello" → "hXXlo"
29

30
// 插入
31
s.insert(1, "XX");       // 在位置1插入"XX"
32
                         // "hello" → "hXXello"
33

34
// 清空
35
s.clear();               // ""

1
#include <cstdio>
2

3
double v = 14.14285;
4

5
printf("%.2f", v);  // 输出：14.14（保留2位小数）
6
printf("%.3f", v);  // 输出：14.143（保留3位小数）
7
printf("%.1f", v);  // 输出：14.1（保留1位小数）

1
int a = 5;
2
double b = 3.14159;
3
printf("a=%d, b=%.2f\n", a, b);  // 输出：a=5, b=3.14

1
printf("hello\n");   // \n 换行
2
printf("a\tb\n");    // \t 制表符

1
#include <iostream>
2
#include <iomanip>
3
using namespace std;
4

5
double v = 14.14285;
6

7
cout << fixed << setprecision(2) << v;  // 输出：14.14

1
double x = 1234.5678;
2

3
// 不加fixed
4
cout << setprecision(2) << x;  // 输出：1.2e+03（科学计数法）
5

6
// 加fixed
7
cout << fixed << setprecision(2) << x;  // 输出：1234.57
8

9
// 设置后一直有效
10
cout << fixed << setprecision(2);
11
cout << x << " " << y << " " << z;  // 全部保留2位

1
// 场景：输入坐标，输出距离（保留2位小数）
2
double x, y;
3
cin >> x >> y;
4
double dist = sqrt(x*x + y*y);
5

6
// 方案1
7
printf("%.2f", dist);
8

9
// 方案2
10
cout << fixed << setprecision(2) << dist;