当前位置： 首页 > news >正文

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

news 来源：原创 2024/9/12 11:37:09

文章目录

    • @[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. 自定义测试用例的重要性：有些笔试，会让咱们自己设计测试用例， 平时在练习的时候也要注意一下。在编写算法时，自定义测试用例可以帮助你验证代码的正确性。设计测试用例时，应考虑不同的输入场景和边界条件。
  3. 面试中的输入输出和测试用例要求：面试官可能会要求你在编写代码后自定义测试用例以验证代码的正确性，因此掌握输入输出处理技巧非常重要。

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

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

2.1 输入

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

2.1.1 cin

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

  1. cin可以连续从键盘读取多个数据。
  2. cin以空格、Tab键和换行符作为输入的分隔符。
  3. 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()函数来解决问题。
注意事项：

  1. 使用getline()函数时，需要包含头文件<string>。
  2. getline()函数会读取整行内容，包括空格字符，直到遇到换行符为止。

常用场景及示例

  1. 读取整行字符串：
string s;
getline(cin, s);
cout << s << endl;
  • 应用场景： 处理包含空格的整行输入，比如处理多词的句子或描述性文本。
  1. 读取整行并分割处理：
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')
常用场景及示例

  1. 读取单个字符：
char ch;
ch = getchar();
cout << ch << endl;
  • 应用场景： 处理逐字符输入，比如逐个处理某些符号、字母或控制字符。
  1. 读取直到换行符：
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 固定长度的一维数组

输入格式：

31 2 3

或

3 1 2 3

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

#include <iostream>
#include <vector>
using namespace std;int main() {int n;cin >> n; // 读取数组大小，例如3vector<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 4string temp = s.substr(q, p - q);//提取从位置q到p的子字符串，这部分字符串是一个数字。vec.push_back(stoi(temp)); // 将字符串转为整数并存入vectorq = 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)); // 将子字符串转换为整数并存入vectorq = p; // 更新索引位置，跳过逗号}// 输出读取的整数数组，验证输入是否正确for(int i = 0; i < vec.size(); i++) {cout << vec[i] << " ";}cout << endl;return 0;
}

4. ACM模式练习平台

4.1 练习平台推荐

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

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

image.png

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

在这里插入图片描述

  1. 📜 [ 声明 ] 由于作者水平有限，本文有错误和不准确之处在所难免，
  2. 本人也很想知道这些错误，恳望读者批评指正！
  3. 我是：勇敢滴勇~感谢大家的支持！

相关文章：

  • Adobe Lightroom Classic (LRC) 软件下载安装和软件使用介绍
  • 【Java】/* 与树有关的一些概念 */
  • u盘突然说要格式化才能访问？如何跳过格式化打开U盘
  • Java Web —— 第八天（登录功能）
  • SmartPing-记录下
  • Tita的OKR ：产品经理的OKR
  • 测试用例（还需要输入1个字）
  • 背包问题【算法 07】
  • 自然语言处理系列三十二》 语义相似度》语义相似度概念及入门
  • Python爬虫-实现自动获取随机请求头User-Agent
  • ArcGIS高/低聚类(Getis-Ord General G)——探究人口空间格局的20年变迁
  • WPS关闭后,进程依然在后台运行的解决办法
  • AI绘画SD三分钟入门教程！秋叶大佬8月最新的Stable Diffusion整合包V4.9来了，完整安装部署教程奉上，附各种模型插件一次性用爽！
  • 云 VS 边缘计算，关系与区别是什么？
  • SIP协议之匿名呼叫
  • 【159天】尚学堂高琪Java300集视频精华笔记（128）
  • 2019年如何成为全栈工程师？
  • angular学习第一篇-----环境搭建
  • hadoop集群管理系统搭建规划说明
  • Kibana配置logstash，报表一体化
  • Nacos系列：Nacos的Java SDK使用
  • springboot_database项目介绍
  • SpringBoot几种定时任务的实现方式
  • 道格拉斯-普克 抽稀算法 附javascript实现
  • 第2章 网络文档
  • 分布式事物理论与实践
  • 给Prometheus造假数据的方法
  • 规范化安全开发 KOA 手脚架
  • 简析gRPC client 连接管理
  • 跨域
  • 名企6年Java程序员的工作总结，写给在迷茫中的你！
  • 为视图添加丝滑的水波纹
  • 一起参Ember.js讨论、问答社区。
  • PostgreSQL之连接数修改
  • 阿里云ACE认证之理解CDN技术
  • 不要一棍子打翻所有黑盒模型，其实可以让它们发挥作用 ...
  • 我们雇佣了一只大猴子...
  • ​LeetCode解法汇总2696. 删除子串后的字符串最小长度
  • ​LeetCode解法汇总518. 零钱兑换 II
  • ​浅谈 Linux 中的 core dump 分析方法
  • ​软考-高级-系统架构设计师教程（清华第2版）【第9章 软件可靠性基础知识（P320~344）-思维导图】​
  • ​数据结构之初始二叉树（3）
  • ‌前端列表展示1000条大量数据时，后端通常需要进行一定的处理。‌
  • #gStore-weekly | gStore最新版本1.0之三角形计数函数的使用
  • （0）Nginx 功能特性
  • （1）(1.8) MSP(MultiWii 串行协议)(4.1 版)
  • （1）虚拟机的安装与使用,linux系统安装
  • (3) cmake编译多个cpp文件
  • （6）添加vue-cookie
  • (C#)获取字符编码的类
  • (done) ROC曲线 和 AUC值 分别是什么？
  • (ResultSet.TYPE_SCROLL_INSENSITIVE,ResultSet.CONCUR_READ_ONLY)讲解
  • （八）光盘的挂载与解挂、挂载CentOS镜像、rpm安装软件详细学习笔记
  • （二）c52学习之旅-简单了解单片机
  • （附源码）ssm基于web技术的医务志愿者管理系统 毕业设计 100910