发表更新2 分钟读完 (大约346个字)

双指针基础-字符串处理实现

字符串处理实现

在处理字符串时，可以使用C++中的字符串操作库进行各种处理。本文将介绍如何使用C++实现简单的字符串处理。

代码实现

以下是一个实现字符串处理的完整C++代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstring> // 包含c字符串操作库
using namespace std;

int main()
{
    char str[1000];
    cin.getline(str, 1000); // 使用cin.getline替代gets
    int n = strlen(str);
    for (int i = 0; i < n; i++)
    {
        int j = i;
        while (j < n && str[j] != ' ') j++;
        for (int k = i; k < j; k++) cout << str[k];
        cout << endl;
        i = j;
    }
    return 0;
}

示例输入输出

以下是一些示例输入和对应的输出，帮助理解代码的工作原理。

示例 1

输入：

1
hello world

输出：
1
2
hello
world

示例 2

输入：

1
this is a test

输出：
1
2
3
4
this
is
a
test

示例 3

输入：

1
C++ string processing example

输出：
1
2
3
4
C++
string
processing
example

代码说明

输入处理：

  • 使用 cin.getline 函数读取整行输入字符串，避免使用不安全的 gets 函数。
  • 使用 strlen 函数获取字符串长度。

字符串处理实现：

  • 遍历输入字符串，找到每个单词，并逐个输出。

主函数逻辑：

  • 读取输入字符串并获取其长度。
  • 遍历字符串，通过空格分隔单词，并逐行输出每个单词。
发表更新4 分钟读完 (大约667个字)

高精度加法

高精度加法实现

在处理大整数运算时，直接使用内置的数据类型可能会导致溢出，因此需要使用字符串或数组来存储大整数，并逐位进行运算。本文将介绍如何使用C++实现高精度加法。

代码实现

以下是一个实现高精度加法的完整C++代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h> // 包含所有标准库的头文件

using namespace std;

vector<int> a; // 存储第一个大整数
vector<int> b; // 存储第二个大整数
string s1, s2; // 存储输入的两个大整数字符串

// 实现两个大整数的加法函数
vector<int> add(vector<int> a, vector<int> b) {
    if (a.size() < b.size()) return add(b, a); // 确保 a 的长度大于或等于 b

    vector<int> c; // 存储结果的向量
    int t = 0; // 进位

    // 遍历较长的向量 a
    for (int i = 0; i < a.size(); ++i) {
        t += a[i]; // 累加 a 的当前位
        if (i < b.size())
        t += b[i]; // 如果 b 还有对应的位，则累加 b 的当前位
        c.push_back(t % 10); // 将当前位的结果存入 c
        t /= 10; // 更新进位
    }

    // 如果有剩余的进位，则加入结果
    if (t)
        c.push_back(t);

    return c;
}

int main() {
    // 读取两个大整数的字符串
    cin >> s1 >> s2;

    // 将字符串转换为向量，低位在前
    for (int i = s1.size() - 1; i >= 0; --i)
        a.push_back(s1[i] - '0');
    for (int i = s2.size() - 1; i >= 0; --i)
        b.push_back(s2[i] - '0');  
    //在C++中，字符（char）和整数（int）之间有一定的对应关系。具体来说，字符 '0' 到 '9' 的ASCII值分别是48到57。为了将字符 '0' 到 '9' 转换为对应的整数0到9，需要减去字符 '0' 的ASCII值。这是因为字符 '0' 的ASCII值是48，所以减去48就得到了对应的整数值。

    // 计算两个向量的和
    auto ans = add(a, b);

    // 逆序输出结果
    for (int i = ans.size() - 1; i >= 0; --i)
        printf("%d", ans[i]);

    return 0;
}

示例输入输出

以下是一些示例输入和对应的输出，帮助理解代码的工作原理。

示例 1

输入：

1
2
12345678901234567890
98765432109876543210

输出：
1
111111111011111111100

示例 2

输入：

1
2
50000000000000000000
50000000000000000000

输出：
1
100000000000000000000

示例 3

输入：

1
2
99999999999999999999
1

输出：
1
100000000000000000000

代码说明

输入处理：

  • 使用字符串 s1 和 s2 分别存储输入的两个大整数。
  • 将字符串转换为倒序存储的整数数组 a 和 b。

加法实现：

  • 函数 add 实现两个大整数的逐位加法，考虑进位情况。

主函数逻辑：

  • 将两个字符串转换为整数数组，并确保 a 的长度大于或等于 b。
  • 计算两个向量的和，并逆序输出结果。
发表更新2 分钟读完 (大约363个字)

高精度除法

高精度除法实现

在处理大整数运算时，直接使用内置的数据类型可能会导致溢出，因此需要使用字符串或数组来存储大整数，并逐位进行运算。本文将介绍如何使用C++实现高精度除法。

代码实现

以下是一个实现高精度除法的完整C++代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

vector<int> div(vector<int> a, int b, int &r) {
    vector<int> c;
    r = 0;
    for (int i = a.size()-1; i >= 0; i--) {
        r = r*10 + a[i];
        c.push_back(r / b);
        r = r % b;
    }
    reverse(c.begin(), c.end());
    return c;
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--) {
        A.push_back(a[i] - '0');
    }
    int r = 0;
    auto C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; i--) {
        printf("%d", C[i]);
    }
    cout << endl << r << endl;
    return 0;
}

示例输入输出

以下是一些示例输入和对应的输出，帮助理解代码的工作原理。

示例 1

输入：

1
2
12345678901234567890
12345

输出：
1
2
1000054089004
6170

示例 2

输入：

1
2
98765432109876543210
123456789

输出：
1
2
800000004500000036
98765432

示例 3

输入：

1
2
10000000000000000000
999999999

输出：
1
2
10000000001
1

代码说明

输入处理：

  • 使用字符串 a 存储输入的大整数。
  • 将字符串转换为倒序存储的整数数组 A。

除法实现：

  • 函数 div 实现大整数与单个整数的逐位除法，并计算余数。

主函数逻辑：

  • 将字符串转换为整数数组，并进行逐位除法计算。
  • 输出结果并打印余数。
发表更新3 分钟读完 (大约509个字)

高精度减法

高精度减法实现

在处理大整数运算时，直接使用内置的数据类型可能会导致溢出，因此需要使用字符串或数组来存储大整数，并逐位进行运算。本文将介绍如何使用C++实现高精度减法。

代码实现

以下是一个实现高精度减法的完整C++代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>

using namespace std;

vector<int> a, b; // 存储大整数
string s1, s2; // 存储输入的两个大整数字符串
int t;

vector<int> sub(vector<int> a, vector<int> b) {
    vector<int> c; 
    int t = 0;
    for(int i = 0; i < a.size(); ++i) {
        a[i] -= t;
        if(i < b.size()) a[i] -= b[i];
        if(a[i] < 0) t = 1;
        else t = 0;
        c.push_back((a[i] + 10) % 10);
    }
    while(c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

bool Max(vector<int> a, vector<int> b) {
    if(a.size() < b.size())
        return true;
    if(a.size() > b.size())
        return false;
    for(int i = a.size() - 1; i >= 0; --i)
        if(a[i] > b[i])
            return false;
        else if(a[i] < b[i])
            return true;
    return 0;
}

int main() {
    cin >> s1 >> s2;
    for(int i = s1.size() - 1; i >= 0; --i) a.push_back(s1[i] - '0');
    for(int i = s2.size() - 1; i >= 0; --i) b.push_back(s2[i] - '0');
    if(Max(a, b) == true) {
        printf("-");
        auto c = sub(b, a);
        for(int i = c.size() - 1; i >= 0; --i)
            printf("%d", c[i]);
    }
    else {
        auto c = sub(a, b);
        for(int i = c.size() - 1; i >= 0; --i)
            printf("%d", c[i]);
    }
    return 0;
}

示例输入输出

以下是一些示例输入和对应的输出，帮助理解代码的工作原理。

示例 1

输入：

1
2
12345678901234567890
98765432109876543210

输出：
1
-86419753208641975320

示例 2

输入：

1
2
98765432109876543210
12345678901234567890

输出：
1
86419753208641975320

示例 3

输入：

1
2
50000000000000000000
50000000000000000000

输出：
1
0

代码说明

输入处理：

  • 使用字符串 s1 和 s2 分别存储输入的两个大整数。
  • 将字符串转换为倒序存储的整数数组 a 和 b。

减法实现：

  • 函数 sub 实现两个大整数的逐位减法，考虑借位情况。
  • 函数 Max 用于比较两个大整数的大小，确定是否需要输出负号。

主函数逻辑：

  • 根据 Max 函数的结果，确定是 a - b 还是 b - a。
  • 输出结果时，如果需要，先输出负号，再输出结果。
发表更新1 分钟读完 (大约166个字)

数的三次方根

题目描述

给定一个浮点数 n，求它的三次方根。

输入格式

共一行，包含一个浮点数 n。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 6 位小数。

数据范围

  • −10000≤n≤10000

样例

输入样例：

1
1000.00

输出样例：

1
10.000000

算法1

(二分) O(logn)

小数二分

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;

double x;

double bsearch(double x) {
    double l = -1e3, r = 1e3;
    while(r - l > 1e-8) { //取保留位数多2位,如:保留一位小数,写1e-3
        double mid = (l + r) / 2;
        if(mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    return l;
}

int main() {
    cin >> x;
    printf("%.6lf",bsearch(x));
    return 0;
}
发表更新4 分钟读完 (大约608个字)

整数二分(besearch)

题目描述

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。

输入格式

  • 第一行包含整数 n 和 q，表示数组长度和询问个数。
  • 第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
  • 接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式

共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。

数据范围

  • 1≤n≤100000
  • 1≤q≤10000
  • 1≤k≤10000

样例

输入样例：

1
2
3
4
5
6 3
1 2 2 3 3 4
3
4
5

输出样例：

1
2
3
3 4
5 5
-1 -1

算法1

(二分) O(nlogn)

枚举左端点和右端点

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

using namespace std;

#define N 1000010

int n, k, q, a[N];

// 查找元素q在数组a中的首次和最后一次出现的位置
void bearch(int q) {
    // leftans和rightans用于存储结果，初始化为最大值和最小值
    int leftans = INT_MAX, rightans = INT_MIN;
    int l = 0, r = n - 1;

    // 找到元素q的首次出现位置
    while (l < r) {
        int mid = (l + r) >> 1;  // 等价于 (l + r) / 2
        if (a[mid] >= q)
            r = mid;
        else 
            l = mid + 1;
    }

    // 如果在数组a中没有找到元素q，输出-1 -1
    if (a[l] != q) {
        printf("-1 -1\n");
        return;
    }

    // 输出元素q的首次出现位置
    printf("%d ", l);

    // 重置左右边界，准备查找最后一次出现位置
    l = 0, r = n - 1;

    // 找到元素q的最后一次出现位置
    while (l < r) {
        int mid = (l + r + 1) >> 1;  // 等价于 (l + r + 1) / 2
        if (a[mid] <= q)
            l = mid;
        else 
            r = mid - 1;
    }

    // 输出元素q的最后一次出现位置
    printf("%d\n", l);
    return;
}

int main() {
    // 输入数组长度n和查询次数k
    scanf("%d %d", &n, &k);

    // 输入数组元素
    for (int i = 0; i < n; ++i)
        scanf("%d", a + i);

    // 对每个查询执行bearch函数
    while (k--) {
        scanf("%d", &q);
        bearch(q);
    }

    return 0;
}

算法2

(upperbound 和 lowerbound) O(nlogn)

STL

大法好！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>

using namespace std;

#define N 1000010

int n, k, q, a[N];

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++i)
        scanf("%d",a + i);
    while (k--) {
        scanf("%d", &q);
        int t = lower_bound(a, a + n, q) - a;

        if (t == n || a[t] != q) {
            puts("-1 -1");
            continue;
        }

        printf("%d ", t);

        t = upper_bound(a, a + n, q) - a;
        printf("%d\n", t - 1);
    }
    return 0;
}
发表更新2 分钟读完 (大约300个字)

归并排序(merge_sort)

题目描述

给定你一个长度为 n 的整数数列。请你使用归并排序对这个数列按照从小到大进行排序，并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1 ≤ n ≤ 100000

样例

输入样例：

1
2
5
3 1 2 4 5

输出样例：

1
1 2 3 4 5

算法1 (排序) O(nlogn)

归并排序板子，先分组，再组合（merge）

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>

using namespace std;

#define N 100005

int n, q[N];

void merge_sort(int q[], int l, int r) {
    if (l >= r) return;

    int mid = (l + r) >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int temp[N];
    int k = 0;
    int x = l, y = mid + 1;
    while (x <= mid && y <= r) {
        if (q[x] <= q[y]) temp[++k] = q[x++];
        else temp[++k] = q[y++];
    }

    while (x <= mid) temp[++k] = q[x++];
    while (y <= r) temp[++k] = q[y++];

    for (int i = 1, j = l; j <= r; ++i, ++j)
        q[j] = temp[i];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", q + i);
    merge_sort(q, 1, n);
    for (int i = 1; i <= n; ++i)
        printf("%d ", q[i]);
    return 0;
}
发表更新2 分钟读完 (大约313个字)

快速排序(quick_sort)

题目描述

给定你一个长度为 n 的整数数列。请你使用快速排序对这个数列按照从小到大进行排序，并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1 ≤ n ≤ 100000

样例

输入样例：

1
2
5
3 1 2 4 5

输出样例：

1
1 2 3 4 5

C++ 代码

算法1：使用手写快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>

using namespace std;

#define N 100005

int q[N], n;

void quick_sort(int l, int r) {
    if(l >= r) return ;

    int i = l - 1, j = r + 1;
    int x = q[l + r >> 1];

    while(i < j) {
        do ++i; while(q[i] < x);
        do --j; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }

    quick_sort(l, j);
    quick_sort(j + 1, r);
}

int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
        scanf("%d",q+i);
    quick_sort(1, n);
    for(int i = 1; i <= n; ++i) 
        printf("%d ",q[i]);
    return 0;
}

算法2：(c++STL) O(nlogn) 用algorithm库的sort函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>

using namespace std;

#define N 100005

int q[N], n;

int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
        scanf("%d",q+i);
    sort(q + 1, q + 1 + n); // STL yyds!!!
    for(int i = 1; i <= n; ++i) 
        printf("%d ",q[i]);
    return 0;
}
关注我

链接

分类

最新文章

归档

标签

C++8
Computer1
C语言3
linux1
rag1
transformer3
代码1
代码实现1
堆栈3
多模态1
字符串3
字符串处理1
字符处理1
排序1
数学函数1
数据结构4
日常1
算法19
算法设计3
算法设计、动态规划1
算法设计概念1
编程3
证明题3
输入方法1
面经1
面经1-swimtransformer1
面经2-attention(注意力机制)1
面试真题1
面试经验1
×