C++ACM模式攻略

ACM模式输入输出攻略 | C++篇

[toc]

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

当我们刷算法题的时候,比如力扣、牛客这些网站,很多的题目只需要我们写出函数体(核心代码),平台就可以自动帮助我们补齐输入输出,进行调试,但,在笔试和面试中,往往需要自己写出可以运行的完整代码(ACM模式),这个时候,需要我们去了解一下自己所使用的语言下的输入输出如何去设计。

几个注意事项

1.笔试平台用的比较多的,比如牛客,赛码,可以提前去熟悉熟悉上面的操作。

2.有些笔试,需要自己写输入输出,有些,则不需要,但我们必须要把输入输出搞懂,这样就不怕是什么类型的笔试了,而且输入输出本身是不难的,学习一下就可以完全掌握。最好不要出现,算法题的核心思路会写,卡在了输入输出上,这样就很难受了。

3.有些笔试,还会让大伙自己设计测试用例,这个平时练习的时候也可以注意一下,主要核心的思想就是测试用例设计的几个原则。

4.不仅仅是笔试,有些面试,也会要求你写输入输出和测试用例。

面试手撕代码的几种形式

1.平台类

去面试官给定的平台上去面试,上面可以编写代码,调试和运行,这些平台有的写好了函数框架,有的是白板,需要自己写全部内容

2.自己的IDE

面试官要求候选人打开自己的ide,并共享桌面进行编写,这种肯定是要自己写全输入输出了

3.要求补齐测试用例

有些面试官,比如微软的面试官,可能会让你写完代码后,自己设计尽可能全面的测试用例,对你编写的代码进行测试。

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

C++的输入输出有很多种方式,既有继承自C语言的,也有其自己独特的。这里呢,不会把全部输入输出函数进行罗列,只会介绍几个在笔试面试中经常被用到的,我认为,掌握这几个足够了,如果有余力,可以去官方文档查看更多关于输入输出的函数进行深度学习。

2.1 输入

首先,在C++语言中,要使用标准的输入,需要包含头文件

(1)cin cin是C++中, 标准的输入流对象,下面列出cin的两个用法,单独读入,和批量读入

cin的原理,简单来讲,是有一个缓冲区,我们键盘输入的数据,会先存到缓冲区中,用cin可以从缓冲区中读取数据。

注意1:cin可以连续从键盘读入数据

注意2:cin以空格、tab、换行符作为分隔符

注意3:cin从第一个非空格字符开始读取,直到遇到分隔符结束读取

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// 用法1,读入单数据
int num;
cin >> num;
cout << num << endl;  // 输出读入的整数num

// 用法2,批量读入多个数据
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] << " ";
}

(2)getline() 从cin的注意中,也可以看出,当我们要求读取的字符串中间存在空格的时候,cin会读取不全整个字符串,这个时候,可以采用getline()函数来解决。

注意1:使用getline()函数的时候,需要包含头文件

注意2:getline()函数会读取一行,读取的字符串包括空格,遇到换行符结束

示例:

1
2
3
4
string s;
getline(cin, s);
// 输出读入的字符串
cout << s << endl;

(3)getchar() 该函数会从缓存区中读出一个字符,经常被用于判断是否换行

示例:

1
2
3
4
char ch;
ch = getchar();
// 输出读入的字符
cout << ch << endl;

2.2 输出

同样的,在C++语言中,要使用标准的输出,也需要包含头文件

输出这边,主要介绍一个函数,就是用的最多的cout,需要注意的是,如果输出endl对象的时候,会输出一个换行符,类似\n。

示例:

1
2
3
4
string s = "hello, Irray~";
// 看看二者有何不同
cout << "hello, Irray~";
cout << s << endl;

当然,C++中的输入输出函数不止这几个,其他的输入函数包括scanf(),cin.get()等等方式,输出函数也有printf(),clog,cerr等方式,要根据具体的使用场景,选择具体的输入输出函数。

但,接下来的案例中,掌握上述三个方法是足够的。不想介绍太多,也是因为,记忆太多方法,容易记混,不如用最简洁的方式实现全部问题。

3.案例

一维数组

此类输入,每个元素为一个int或者char,有两类常见的案例:

1.固定数目

输入格式:

3
1 2 3

or

3 1 2 3

解析: 对于第一组,第一行的3为整数的个数,第二行为三个用空格隔开的整数,因此可以采用cin来进行读取

对于第二组,第一行的3为整数的个数,空格后面的数据为三个用空格隔开的整数,因此可以采用cin来进行读取

此类问题,可以先创建一个vector,大小设置为给定值,然后通过for循环来循环输入

答案:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int n;
cin >> n; // 读入3,说明数组的大小是3
vector<int> nums(n); // 创建大小为3的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;

2.不固定数目

输入格式: 1 2 3 4 解析: 输入的数据为四个用空格间隔的整数,没有指定整数个数,因此可以用while循环结合cin来处理该问题。

答案:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
vector<int> nums;
int num;
while(cin >> num) {
	nums.push_back(num);
	// 读到换行符,终止循环
	if(getchar() == '\n') {
		break;
	}
}

// 验证是否读入成功
for(int i = 0; i < nums.size(); i++) {
	cout << nums[i] << " ";
}
cout << endl;

二维数组

除了一维数组这种最基础的输入外,还会考察二维数组的输入,尤其是在dfs、dp类型的题目中。

二维数组主要有两种方式:

1.常规模式

输入格式:

2 3
1 2 3
1 2 3

解析: 第一行的2,代表数据为2行,3代表数据为3列,因此根据第一行,可以得出,所输入数据为2行3列的二维数组。接下来的6个数字,就是按照空格和换行符分隔开的2x3二维数组,因此用for循环和cin即可处理

答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
int m; // 接收行数
int 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;
}

2.每一行数据是逗号隔开的整数

输入格式:

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

解析: 第一行的2,代表数据为2行,3代表数据为3列,因此根据第一行,可以得出,所输入数据为2行3列的二维数组。接下来的2行,分别是一个字符串,字符串中用逗号隔开每个整数。这里采用读入字符串的方式,并将读入的字符串进行按逗号分开。

答案:

 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
int m; // 接收行数
int n; // 接收列数

cin >> m >> n;

vector<vector<int>> matrix(m);

for(int i = 0; i < m; i++) {
    // 读入字符串
	string s;
	getline(cin, s);
	
	// 将读入的字符串按照逗号分隔为vector<int>
	vector<int> vec;
	int p = 0;
	for(int q = 0; q < s.size(); q++) {
		p = q;
		while(s[p] != ',' && p < s.size()) {
			p++;
		}
		string tmp = s.substr(q, p - q);
		vec.push_back(stoi(tmp));
		q = p;
	}
	
	//写入matrix
	matrix[i] = vec;
	vec.clear();
}

// 验证是否读入成功
for(int i = 0; i < matrix.size(); i++) {
	for(int j = 0; j < matrix[i].size(); j++) {
		cout << matrix[i][j] << " ";
	}
	cout << endl;
}

字符串

1.单字符串

输入格式: abc

解析: 用cin读入即可

答案:

1
2
3
4
5
string s;
cin >> s;

// 验证是否读入成功
cout << s << endl;

2.给定数目多字符串

输入格式: 3 abc ab a

解析: 第一行的3,代表有3个字符串,后续为用空格隔开的3个字符串,采用for循环和cin读入即可

答案:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int n;
cin >> n; // 读入3,说明字符串数组的大小是3
vector<string> strings(n); // 创建大小为3的vector<string>
for(int i = 0; i < n; i++) {
	cin >> strings[i];
}

// 验证是否读入成功
for(int i = 0; i < strings.size(); i++) {
	cout << strings[i] << " ";
}
cout << endl;

3.不给定数目多字符串

输入格式: abc ab a d

解析: 输入为用空格隔开的若干个字符串。

答案:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
vector<string> strings;
string str;
while(cin >> str) {
	strings.push_back(str);
	// 读到换行符,终止循环
	if(getchar() == '\n') {
		break;
	}
}

// 验证是否读入成功
for(int i = 0; i < strings.size(); i++) {
	cout << strings[i] << " ";
}
cout << endl;

4.字符串转整数数组

输入格式: 11,22,3,4

解析: 输入为一个完整字符串,字符串内容是按照逗号隔开的一个数组,可以先读入完成字符串,然后根据逗号进行分隔

答案:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> vec;

// 读入字符串
string s;
getline(cin, s);

// 将读入的字符串按照逗号分隔为vector<int>
	int p = 0;
	for(int q = 0; q < s.size(); q++) {
		p = q;
		while(s[p] != ',' && p < s.size()) {
			p++;
		}
		string tmp = s.substr(q, p - q);
		vec.push_back(stoi(tmp));
		q = p;
	}

// 验证是否读入成功
for(int i = 0; i < vec.size(); i++) {
	cout << vec[i] << " ";
}
cout << endl;

4.ACM模式练习平台

除了在笔试中实战之外,也可以在牛客平台进行练习:https://ac.nowcoder.com/acm/contest/5652

同时,牛客上也有很多专门的ACM模式算法题。

这里给出一个案例:

解答:

因为比较简单,就直接给出代码了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <iostream>
using namespace std;

int main() {
    int a;
    int b;
    while(cin >> a >> b) {
        cout << a + b << endl;
    }
    
    return 0;
}

5.常见数据结构定义

在ACM模式中,链表、二叉树这些数据结构的定义也需要自己去定义,接下来就给出二者的定义、输入和输出。

这里就直接给出代码了,想必大伙对数据结构都是了如指掌的。

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
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;

// 链表定义,并给出两个有参构造函数
struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int _val):val(_val),next(nullptr){}
    ListNode(int _val,ListNode* _next):val(_val),next(_next){}
};
int main()
{

	// 根据控制台的输入,创建一条单链表
    ListNode* LHead = new ListNode(-1);
    ListNode* pre = LHead;
    ListNode* cur = nullptr;
    
    int num;
    while(cin >> num)
    {
    	// 为了简单起见,设置为-1退出,后续可优化,这里只是给出一个例子
        if(num == -1) break;
        cur = new ListNode(num);
        pre->next = cur;
        pre = cur;
    }
    
    cur = LHead->next;
    
    // 输出单链表的value
    while(cur)
    {
        cout << cur->val << " ";
        cur = cur->next;
    }
    
    cout << endl;
    
    return 0;
}

2.二叉树

 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

//定义树节点
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int _val):val(_val),left(nullptr),right(nullptr){}
    TreeNode(int _val,TreeNode* _left,TreeNode* _right):val(0),left(_left),right(_right){}
};

//根据数组生成树
TreeNode* buildTree(const vector<int>& v)
{
    vector<TreeNode*> vTree(v.size(),nullptr);
    TreeNode* root = nullptr;
    for(int i = 0; i < v.size(); i++)
    {
        TreeNode* node = nullptr;
        if(v[i] != -1){
            node = new TreeNode(v[i]);
        }
        vTree[i] = node;
    }
    root = vTree[0];
    for(int i = 0; 2 * i + 2 < v.size(); i++)
    {
        if(vTree[i] != nullptr)
        {
            vTree[i]->left = vTree[2 * i + 1];
            vTree[i]->right = vTree[2 * i + 2];
        }
    }
    return root;
}

//根据二叉树根节点层序遍历并打印
void printBinaryTree(TreeNode* root)
{
    if(root == nullptr) return;
    vector<vector<int>> ans;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        int size = q.size();
        vector<int> path;
        for(int i = 0;i<size;i++){
            TreeNode* node = q.front();
            q.pop();
            if(node == nullptr)
            {
                path.push_back(-1);
            }
            else
            {
                path.push_back(node->val);
                q.push(node->left);
                q.push(node->right);
            }
        }
        ans.push_back(path);
    }
    
    for(int i = 0;i<ans.size();i++)
    {
        for(int j = 0;j<ans[i].size();j++)
        {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return;
}

int main()
{	// 验证
    vector<int> v = {4,1,6,0,2,5,7,-1,-1,-1,3,-1,-1,-1,8};
    TreeNode* root = buildTree(v);
    printBinaryTree(root);
    
    return 0;
}

updatedupdated2023-04-172023-04-17