Fork me on GitHub

牛客网笔试形式

牛客网作为近来应届学生招聘的新贵网站,大大小小许多公司都将其作为自己的校招在线笔试平台,而作为广大编程大牛刷题的社区LeetCode,两者代码提交的形式则有着很大的不同。

牛客网与LeetCode

在LeetCode上面,题目都已按照不同的语言类型定义好了接口函数,你只需要将给出的函数补充完整即可,并且提交运行之后LeetCode还会给出详细的错误用例。而牛客网上面的算法题目只描述出两个左右输入输出样例,你需要写出完整的可执行程序,提交运行之后只会给出测试样例通过的百分比,你不能根据提示知道你的程序疏忽了哪些测试样例,如果你通过了100%的测试样例,你的程序就被AC(Accept)了。因此即使你能在LeetCode上熟练的解决各种难题,但是不一定能在牛客网上顺利AC,这还是需要熟悉一下这些形式的。让我们来看一些常见题型,寻找一些牛客网上算法题目的提交模板吧!

[编程题] 矩阵查数——第四范式

时间限制:4秒
空间限制:65536K

给定一个二维整型矩阵,已知矩阵的每一行都按照从小到大的顺序排列,每一列也都按照从小到大的顺序排列。现在给出一个数,请写一个函数返回该数是否存在于矩阵中。
矩阵中出现的数字与需要查找的数(k)都为0~100000之间的整数,且矩阵的大小在3000*3000以内。
在保证正确性的基础上,请尽量给出比较高效的解法。请列出你的算法时间复杂度与空间复杂度分别是多少?

输入描述:

输入两个整数m,n, 且 0> matrix矩阵,大小为m行n列,与一个int k,为需要查找的数字。

输出描述:

输出true或者false,true表示该数k存在于该matrix矩阵中,false表示该数k不存在于该matrix矩阵中。

输入例子1:

1
2
3
4
5
3 3
​​2 3 5
​​3 4 7
​​3 5 8
4

输出例子1:

true

例子说明1:

4位于矩阵的第二行第二列,故输出true

%E7%9F%A9%E9%98%B5%E6%9F%A5%E6%95%B0.cpplink
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
#include <iostream>
#include <vector>
using namespace std;
//从左下角开始遍历如果值比k小则向右走,如果值比k大则往下走
bool findk(vector<vector<int>> &matrix, int k)
{
int m = matrix.size();
int n = matrix[0].size();
m--;
int i = 0;
while (m >= 0 && i < n)
{
if (matrix[m][i] == k)
{
return true;
}
else if (matrix[m][i] > k)
m--;
else
i++;
}
return false;
}

int main()
{
int m, n; // 输入两个整数m,n, 且 0<m<=3000, 0<n<=3000.
cin >> m >> n;
if (m == 0 || n == 0)
{
cout << "false" << endl;
return 0;
}
//接着输入一个vector<vector<int>> matrix矩阵,大小为m行n列
vector<vector<int>> vec(m, vector<int>(n, 0));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> vec[i][j];
int k; //与一个int k,为需要查找的数字。
cin >> k;
bool res = findk(vec, k);
//输出true或者false,true表示该数k存在于该matrix矩阵中,false表示该数k不存在于该matrix矩阵中。
cout << boolalpha << res << endl;
return 0;
}

您的支持将鼓励我继续创作!