ACM模式下算法题输入输出攻略【C++】

文章目录

• • @[TOC]
• 1. 核心代码模式与ACM模式
• • 1.1 ACM模式介绍
  • 1.2 注意事项
• 2. C++常用的输入输出方法
• • • 2.1 输入
    • • 2.1.1 `cin`
      • 注意事项
      • 2.1.2 `getline()`
      • 注意事项
      • 2.1.3 `getchar()`
      • 注意事项
    • 2.2 输出
• 3. 案例
• • 3.1 一维数组输入
  • • 3.1.1 固定长度的一维数组
    • 3.1.2 不固定长度的一维数组
  • 3.2 二维数组输入
  • • 3.2.1 常规模式的二维数组输入
    • 3.2.2 每行数据用逗号分隔的二维数组输入
  • 3.3 字符串输入
  • • 3.3.1 单字符串输入
    • 3.3.2 多字符串输入（固定个数）
    • 3.3.3 多字符串输入（不固定个数）
    • 3.3.4 字符串转整数数组
• 4. ACM模式练习平台
• • 4.1 练习平台推荐
  • 4.2 实战平台案例
• 5. 常见数据结构定义
• • 5.1 链表
  • 5.2 二叉树

八月份快结束了，秋招提前批和秋招也陆续开始了。在一般大厂笔试中都会要求手撕算法，如果算法正确，最后输出的时候没解决好就很吃亏啦~所以今天这篇文章带你详细理解核心代码模式与ACM模式下需要注意的事项。

1. 核心代码模式与ACM模式

1.1 ACM模式介绍

在编程竞赛和笔试中，ACM模式是常见的要求，它需要我们编写完整的程序来处理输入输出。与平台上的核心代码模式不同，ACM模式通常要求我们处理标准输入输出并完整实现解决方案。核心代码模式只需要提交核心算法部分（通常是某一个函数），而ACM模式需要处理整个程序(包括main函数)，包括输入输出和其他程序结构。

1.2 注意事项

面试手撕代码的几种形式： 1.平台类 去面试官给定的平台上去面试，上面可以编写代码，调试和运行，这些平台有的写好了函数框架，有的是白板，需要自己写全部内容 2.自己的IDE 面试官要求候选人打开自己的ide，并共享桌面进行编写，这种肯定是要自己写全输入输出了 3.要求补齐测试用例 有些面试官，比如微软的面试官，可能会让你写完代码后，自己设计尽可能全面的测试用例，对你编写的代码进行测试。 ————————来源：牛客网

2. C++常用的输入输出方法

2.1 输入

在C++语言中，标准输入操作需要包含头文件<iostream>。以下是C++中常用的几种标准输入方法，以及它们的特点和使用方式。下面这列了几个常用的，熟练掌握下面这几个就够了，如果学有余力可以去官方文档查看更多的输入输出函数。

2.1.1 cin

cin是C++中最常用的标准输入流对象。它的基本原理是通过一个缓冲区（Buffer）来存储键盘输入的数据，cin则从这个缓冲区中读取数据。注意事项：

示例代码：

• 单独读入一个数据：

int num;
cin >> num;
cout << num << endl; // 输出读入的整数num

应用场景： 当题目要求输入一个整数并处理时，这是最基本的用法。

• 批量读入多个数据：

vector<int> nums(5);
for(int i = 0; i < nums.size(); i++) {
cin >> nums[i];
}

// 输出读入的数组
for(int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}

应用场景： 常用于读取一组整数，比如数组或序列。

• 处理多组输入：

int a,b
while(cin>>a>>b){
cout<<a+b<<endl;
}

应用场景： 处理多组输入，直到文件结束（EOF）。这种用法常见于需要连续处理多组测试数据的题目。

注意事项

• cin 会忽略输入中的空格、Tab 和换行符。
• 当遇到空格、Tab 或换行符时，cin 会结束当前变量的读取，并开始读取下一个变量。

2.1.2 getline()

在某些情况下，cin无法满足需求。例如，当我们需要读取包含空格的字符串时，cin会在遇到空格时停止读取,读不全整个字符串。此时，可以使用getline()函数来解决问题。注意事项：

常用场景及示例

string s;
getline(cin, s);
cout << s << endl;

• 应用场景： 处理包含空格的整行输入，比如处理多词的句子或描述性文本。

string line;
getline(cin, line);
stringstream ss(line);
int num;
while (ss >> num) {
cout << num << endl;
}

• 应用场景： 处理复杂输入格式，如需要按空格分割的整行数据，并将其转换为数字。

注意事项

• getline 会读取换行符之前的所有字符，但不会包括换行符本身。
• 当 getline 与 cin 混合使用时，可能会出现换行符残留问题。通常建议在使用 getline 前使用 cin.ignore() 以清除换行符。

2.1.3 getchar()

getchar()函数用于从缓冲区中读取一个字符，常用于判断是否遇到换行符等场景。比如：while(getchar()!='\\n')常用场景及示例

char ch;
ch = getchar();
cout << ch << endl;

• 应用场景： 处理逐字符输入，比如逐个处理某些符号、字母或控制字符。

char ch;
while ((ch = getchar()) != '\\n') {
cout << ch;
}
cout << endl;

• 应用场景： 在逐字符处理输入时，直到遇到换行符为止。常用于需要逐字符解析输入的情况。

注意事项

• getchar 读取的是缓冲区中的下一个字符，这意味着它包括空格、Tab、换行符等所有字符。
• 如果需要逐字符处理输入，getchar 是一个很好的选择，尤其是在需要精确控制输入处理时。

2.2 输出

在C++中，标准输出操作同样需要包含头文件<iostream>。常用的输出函数是cout，其基本功能是将数据输出到控制台。需要特别注意的是，cout在输出endl对象时，不仅会换行，还会刷新输出缓冲区，这与\\n略有不同。示例代码：

string s = "hello, Irray~";
// 观察以下输出的区别
cout << "hello, Irray~";
cout << s << endl; // 输出后换行

3. 案例

在刷算法题时，掌握不同类型输入的处理方式是非常重要的。根据输入格式的不同，我们可以采用不同的方法来读取数据。以下我们将详细介绍几种常见输入类型的处理方法，并附上相应的代码示例。

3.1 一维数组输入

一维数组是算法题中最基础的输入类型之一，通常每个元素是一个整数或字符。根据题目要求，输入的数组可以是固定长度或不固定长度。

3.1.1 固定长度的一维数组

输入格式：

3
1 2 3

或

3 1 2 3

解析：在第一种格式中，第一行的3表示数组的长度，第二行是用空格隔开的整数。在第二种格式中，第一行包含数组的长度3以及数组元素。对于这两种情况，我们都可以使用cin来逐一读取数据。代码示例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
int n;
cin >> n; // 读取数组大小，例如3
vector<int> nums(n); // 创建大小为n的vector<int>

// 逐一读取数组元素
for(int i = 0; i < n; i++) {
cin >> nums[i];
}

// 输出读取的数组，验证输入是否正确
for(int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;

return 0;
}

3.1.2 不固定长度的一维数组

输入格式：

1 2 3 4

解析：在这种情况下，输入的数据是多个用空格分隔的整数，没有明确给出数组的长度。我们可以使用while循环结合cin和getchar来处理。代码示例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
vector<int> nums;
int num;

// 使用while循环逐一读取整数，直到遇到换行符结束
while(cin >> num) {
nums.push_back(num);
if(getchar() == '\\n') {
break;
}
}

// 输出读取的数组，验证输入是否正确
for(int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;

return 0;
}

3.2 二维数组输入

在一些算法题中，我们需要处理二维数组的输入。常见的输入形式包括常规模式和每行数据用逗号分隔的模式。

3.2.1 常规模式的二维数组输入

输入格式：

2 3
1 2 3
1 2 3

解析：第一行的2表示二维数组的行数，3表示列数。接下来两行数据是二维数组的内容。我们可以使用嵌套的for循环和cin来逐行读取数据。代码示例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
int m, n;
cin >> m >> n; // 读取行数和列数

vector<vector<int>> matrix(m, vector<int>(n));
//这里 二维数组的表达方式一定要掌握

// 逐行逐列读取二维数组元素
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}

// 输出读取的二维数组，验证输入是否正确
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}

return 0;
}

3.2.2 每行数据用逗号分隔的二维数组输入

输入格式：

2 3
1,2,3
1,2,3

解析：同样的，第一行的2和3分别代表行数和列数。不同的是，接下来的每行数据是用逗号分隔的字符串。我们可以使用getline读取每行字符串，然后通过处理字符串来分隔出每个整数。输入的时候有逗号作为分隔，但是我们希望存到二维数组里面的只有数字。代码示例：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
int m, n;
cin >> m >> n;
//cin.ignore(); // 忽略换行符，以便后续getline读取
//当你使用 cin 读取 m 和 n 后，输入流中还会残留一个换行符（\\n）。如果你直接调用 getline()，
//它会立即读取到这个换行符，并将其视为一个空行。这就会导致 getline() 读取到的内容为空字符串，
//而不是你期望的那一整行输入数据。

//cin.ignore() 的作用就是忽略掉这个换行符（或其他指定的字符），从而让后续的 getline() 能正确读取你需要的那一行数据。

getchar();
//getchar() 会从输入流中读取下一个字符并将其丢弃，因此可以用来忽略掉 cin 读取 m 和 n 后残留的换行符。

vector<vector<int>> matrix(m);
//仅初始化了 m 行，但每一行都是一个空的 vector，需要后续手动添加元素。
//vector<vector<int>> matrix(m, vector<int>(n));也可以，因为已经给出m，n.

// 逐行读取并处理字符串
for(int i = 0; i < m; i++) {
string s;
getline(cin, s);//读取一行放入到字符串s中

vector<int> vec;//建立存放整数的一维数组
int p = 0;//索引p，用于表示当前数字的结束位置
for(int q = 0; q < s.size(); q++) {
p = q;
while(p < s.size() && s[p] != ',') {
p++;
}
// 2 , 3 , 4
// 0 1 2 3 4
string temp = s.substr(q, p – q);
//提取从位置q到p的子字符串，这部分字符串是一个数字。
vec.push_back(stoi(temp));
// 将字符串转为整数并存入vector
q = p; // 更新索引位置
}

matrix[i] = vec; // 将处理后的vector存入matrix
}

// 输出读取的二维数组，验证输入是否正确
for(int i = 0; i < m; i++) {
for(int j = 0; j < matrix[i].size(); j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}

return 0;
}

3.3 字符串输入

字符串在算法题中也非常常见，以下介绍几种常见的字符串输入情况及其处理方式。

3.3.1 单字符串输入

输入格式：

abc

解析：对于单个字符串的输入，我们直接使用cin即可读取。代码示例：

#include <iostream>
using namespace std;

int main() {
string s;
cin >> s; // 读取单个字符串

// 输出读取的字符串，验证输入是否正确
cout << s << endl;

return 0;
}

3.3.2 多字符串输入（固定个数）

输入格式：

3 abc ab a

解析：第一行的3表示接下来有三个字符串，每个字符串用空格隔开。我们可以使用for循环结合cin来逐一读取字符串。代码示例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
int n;
cin >> n; // 读取字符串数量
vector<string> strings(n);

// 逐一读取字符串
for(int i = 0; i < n; i++) {
cin >> strings[i];
}

// 输出读取的字符串，验证输入是否正确
for(int i = 0; i < strings.size(); i++) {
cout << strings[i] << " ";
}
cout << endl;

return 0;
}

3.3.3 多字符串输入（不固定个数）

输入格式：

abc ab a d

解析：当输入为多个用空格隔开的字符串且没有给出数量时，我们可以使用while循环结合cin和getchar来逐一读取，直到遇到换行符结束输入。代码示例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
vector<string> strings;
string str;

// 使用while循环逐一读取字符串，直到遇到换行符结束
while(cin >> str) {
//cin成功读取返回true，否则false;
strings.push_back(str);
if(getchar() == '\\n') {
break;
}
}

// 输出读取的字符串，验证输入是否正确
for(int i = 0; i < strings.size(); i++) {
cout << strings[i] << " ";
}
cout << endl;

return 0;
}

3.3.4 字符串转整数数组

输入格式：

11,22,3,4

解析：输入为一个完整字符串，字符串内容为用逗号隔开的整数。我们可以先读取整个字符串，然后根据逗号分隔出每个整数，并将其存入vector<int>中。代码示例：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
vector<int> vec;
string s;

// 读取整行字符串
getline(cin, s);

// 按照逗号分隔字符串并转换为整数
int p =0;
for(int q = 0; q < s.size(); q++) {
p = q;
while(p < s.size() && s[p] != ',') {
p++;
}
string temp = s.substr(q, p – q); // 提取子字符串
vec.push_back(stoi(temp)); // 将子字符串转换为整数并存入vector
q = p; // 更新索引位置，跳过逗号
}

// 输出读取的整数数组，验证输入是否正确
for(int i = 0; i < vec.size(); i++) {
cout << vec[i] << " ";
}
cout << endl;

return 0;
}

4. ACM模式练习平台

4.1 练习平台推荐

以下是一些推荐的练习平台：

• LeetCode：提供多种类型的编程问题，适合练习各种算法和数据结构。
• Codeforces：有丰富的编程比赛题目和讨论区，可以提升算法能力和解题速度。
• AtCoder：提供编程竞赛题目，适合训练自己的算法能力。
• 牛客网：有许多笔试题和面试题，适合进行ACM模式训练。重点推荐此题单：题目来自：牛客竞赛链接

4.2 实战平台案例

题目：给定一个整数数组，求数组中的每个元素的平方，并按升序输出。输入：

5
1 2 3 4 5

输出：

1 4 9 16 25

解决方案：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
int n;
cin >> n; // 读入数组大小
vector<int> nums(n);
for(int i = 0; i < n; i++) {
cin >> nums[i]; // 读入数组元素
}
for(int i = 0; i < n; i++) {
nums[i] = nums[i] * nums[i]; // 计算平方
}
sort(nums.begin(), nums.end()); // 排序
for(int i = 0; i < n; i++) {
cout << nums[i] << " "; // 输出结果
}
cout << endl;
return 0;
}

5. 常见数据结构定义

在ACM模式中，链表、二叉树这些数据结构的定义也需要自己去定义，接下来就给出二者的定义、输入和输出。这里就直接给出代码了，想必大伙对数据结构都是了如指掌的。

5.1 链表

链表是一种基本的数据结构，常用于存储和操作数据。以下是一个简单的链表的输入和输出示例：

#include <iostream>
using namespace std;

// 定义链表节点的结构
struct ListNode {
int val; // 节点的值
ListNode* next; // 指向下一个节点的指针
// 构造函数，初始化节点的值和指针
ListNode(int x)
: val(x)
,next(nullptr)
{}
};

int main() {
ListNode* head = nullptr; // 链表的头指针，初始化为空
ListNode* tail = nullptr; // 链表的尾指针，初始化为空
int n;

// 从输入中读取数据，直到遇到换行符
while (cin >> n) {
ListNode* newNode = new ListNode(n); // 创建新的链表节点
if (!head) {
// 如果链表为空，则新的节点是头节点
head = newNode;
tail = head;
} else {
// 否则，将新节点添加到链表末尾
tail->next = newNode;
tail = newNode;
}
if (getchar() == '\\n') {
// 如果输入流中遇到换行符，则停止读取
break;
}
}

// 输出链表中的所有节点值
ListNode* current = head; // 从头节点开始遍历
while (current) {
cout << current->val << " "; // 输出当前节点的值
current = current->next; // 移动到下一个节点
}
cout << endl;

// 清理链表，释放内存
while (head) {
ListNode* temp = head; // 保存当前节点的指针
head = head->next; // 移动到下一个节点
delete temp; // 删除当前节点，释放内存
}

return 0;
}

5.2 二叉树

二叉树是一种常见的数据结构，用于组织和存储数据。以下是一个简单的二叉树的输入和层序遍历输出示例：

#include <iostream>
#include <queue>
using namespace std;

// 定义二叉树节点的结构
struct TreeNode {
int val; // 节点的值
TreeNode* left; // 指向左子节点的指针
TreeNode* right; // 指向右子节点的指针
// 构造函数，初始化节点的值和子节点指针
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int main() {
int n;
cin >> n; // 读取树的节点个数
if (n == 0) {
cout << endl; // 如果节点个数为0，直接输出换行并返回
return 0;
}

vector<TreeNode*> nodes(n, nullptr); // 创建一个保存所有节点的向量
for (int i = 0; i < n; i++) {
int value;
cin >> value; // 读取节点的值
nodes[i] = new TreeNode(value); // 创建新的节点并存储到向量中
}

// 连接树的节点，构建二叉树
for (int i = 0; i < n; i++) {
if (2 * i + 1 < n) nodes[i]->left = nodes[2 * i + 1]; // 左子节点
if (2 * i + 2 < n) nodes[i]->right = nodes[2 * i + 2]; // 右子节点
}

// 层序遍历输出
queue<TreeNode*> q; // 创建一个队列，用于层序遍历
q.push(nodes[0]); // 从根节点开始
while (!q.empty()) {
TreeNode* node = q.front(); // 获取队列中的第一个节点
q.pop(); // 移除队列中的第一个节点
cout << node->val << " "; // 输出当前节点的值
if (node->left) q.push(node->left); // 将左子节点加入队列
if (node->right) q.push(node->right); // 将右子节点加入队列
}
cout << endl;

// 清理树，释放内存
for (auto node : nodes) {
delete node; // 删除每个节点，释放内存
}

return 0;
}