牛客-某公司笔试题-20250316-全解析

【LetMeFly】牛客-某公司笔试题-20250316-全解析

该公司给我留下了十分不错的印象,包括我大四时候去参观的一次,以及研究生期间听其他同学说去参观的一次,给人印象十分不错。

大四保完研印象中都三面了,结果为了奉献研究生实验室的项目给HR姐姐打了个电话婉拒了。后悔死了,到现在还没有一段实习经历。

怀揣着对该公司不错的印象,若能有时间为之贡献一份锦帛之力,也能还一个“去一去第一个即将愿意给我发OFFER的公司”的愿吧。

不过公司要求C++求职者只能使用C++且不能使用STL库函数以及sort等函数,那就尽量手动实现吧。

一:单词规律(模式匹配)

题目地址:LeetCode - 290.单词规律

题目描述

给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

 

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

 

提示:

  • 1 <= pattern.length <= 300
  • pattern 只包含小写英文字母
  • 1 <= s.length <= 3000
  • s 只包含小写英文字母和 ' '
  • s 不包含 任何前导或尾随对空格
  • s 中每个单词都被 单个空格 分隔

解题思路

两个哈希表,记录哪个字符对应哪个字符串、哪个字符串对应哪个字符。

然后遍历一遍字符串把字符串拆分为字符串数组,若pattern和字符串数组长度相同则一一判断是否一一对应。

AC代码

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
class Solution {
private:
vector<string> s2v(string s) {
vector<string> ans;
int last = -1;
for (int i = 0; i <= s.size(); i++) {
if (i == s.size() || s[i] == ' ') {
string thisStr = s.substr(last + 1, i - last - 1);
if (thisStr.size()) {
ans.push_back(thisStr);
}
last = i;
}
}
return ans;
}
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pattern string字符串
* @param str string字符串
* @return bool布尔型
*/
bool wordPattern(string pattern, string str) {
// write code here
unordered_map<char, string> p2s;
unordered_map<string, char> s2p;
vector<string> v = s2v(str);
if (pattern.size() != v.size()) {
return false;
}
for (int i = 0; i < v.size(); i++) {
if (p2s.count(pattern[i])) {
if (p2s[pattern[i]] != v[i]) {
return false;
}
} else {
p2s[pattern[i]] = v[i];
}

if (s2p.count(v[i])) {
if (s2p[v[i]] != pattern[i]) {
return false;
}
} else {
s2p[v[i]] = pattern[i];
}
}
return true;
}
};

当时没想到拿字符串映射字符(没有使用s2p)那个哈希表,竟然过了90%。

二:下一个更大元素

类似题目:LeetCode - 556.下一个更大元素III

题目描述

给你一个正整数 n ,请你找出符合条件的最小整数,其由重新排列 n 中存在的每位数字组成,并且其值大于 n 。如果不存在这样的正整数,则返回 -1

注意 ,返回的整数应当是一个 32 位整数 ,如果存在满足题意的答案,但不是 32 位整数 ,同样返回 -1

 

示例 1:

输入:n = 12
输出:21

示例 2:

输入:n = 21
输出:-1

 

提示:

  • 1 <= n <= 231 - 1

解题思路

解这道题之前推荐先解一下另外一道题:LeetCode - 0031.下一个排列

力扣官方题解的动图做的不错:

0031力扣官方题解动图

首先找到最后一个“后面有比他大的数”的数(假设下标为$i$),接着找$i$后面最后一个大于它的数(假设下标为$j$),交换元素$i$、$j$

这样,对于交换的两个数,就满足了“最小数尽可能靠右”、“最大数尽可能小”。

然后将第一个交换位置后面的数组逆序(因为后面的数组一定是递减的)

那么这道题也就迎刃而解了,多的步骤就是十进制数和字符串之间的相互转换。同时,可以用64位整数存储中间结果以防止32位整数溢出。

AC代码

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
typedef long long ll;
class Solution {
private:
string itos(int n) {
string s;
while (n) {
s = char('0' + n % 10) + s;
n /= 10;
}
return s;
}

ll stoi(string s) {
ll ans = 0;
for (char c : s) {
ans = ans * 10 + c - '0';
}
return ans;
}
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param N int整型
* @return int整型

12334
12343

12343
12433

1235
*/
int nextGreaterElement(int N) {
// write code here
string s = itos(N);
int last = -1;
for (int i = 1; i < s.size(); i++) {
if (s[i] > s[i - 1]) {
last = i - 1;
}
}
if (last == -1) {
return -1;
}
cout << last << endl;
int j = s.size() - 1;
for (; ; j--) {
if (s[j] > s[last]) {
break;
}
}
swap(s[last], s[j]);
// cout << s << endl;
reverse(s.begin() + last + 1, s.end());
// cout << s << endl;
ll ans = stoi(s);
cout << ans << endl;
if (ans > INT_MAX) {
return -1;
}
return ans;
}
};

这道题当时有两个问题:

  1. 排序范围错了
  2. 交换错了(没有交换后方尽可能小的值而是直接交换了相邻值)

当时竟然通过了80%。

三:找两个和为目标值且不重叠的子数组

题目地址:LeetCode - 1477.找两个和为目标值且不重叠的子数组

题目描述

给你一个整数数组 arr 和一个整数值 target 。

请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案,请你返回满足要求的两个子数组长度和的 最小值

请返回满足要求的最小长度和,如果无法找到这样的两个子数组,请返回 -1 。

 

示例 1:

输入:arr = [3,2,2,4,3], target = 3
输出:2
解释:只有两个子数组和为 3 ([3] 和 [3])。它们的长度和为 2 。

示例 2:

输入:arr = [7,3,4,7], target = 7
输出:2
解释:尽管我们有 3 个互不重叠的子数组和为 7 ([7], [3,4] 和 [7]),但我们会选择第一个和第三个子数组,因为它们的长度和 2 是最小值。

示例 3:

输入:arr = [4,3,2,6,2,3,4], target = 6
输出:-1
解释:我们只有一个和为 6 的子数组。

示例 4:

输入:arr = [5,5,4,4,5], target = 3
输出:-1
解释:我们无法找到和为 3 的子数组。

示例 5:

输入:arr = [3,1,1,1,5,1,2,1], target = 3
输出:3
解释:注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。

 

提示:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 1000
  • 1 <= target <= 10^8

解题思路

类似滑动窗口,由于元素全正,所以窗口中元素越多窗口中的和越大。对于一个指定的“窗口终点”,(元素和不大于target的)窗口起点是固定的。

我们可以开辟一个数组minPrefix,其中minPrefix[i]代表下标不超过i的子数组中,最小的和为target的元素个数。

这样,对于每个“窗口终点”,如果窗口中元素和恰好为target,则使用当前窗口大小更新历史最小窗口大小。

同理,我们也可以反过来倒着滑动一次,得到minSuffix。minSuffix[i]代表所有下标不小于i的子数组中,和为target的最小子数组的元素个数。

这样,我们只需要遍历一遍数组,$\min{minPrefix[i] + minSuffix[i + 1]}$即为所求。

AC代码

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
class Solution {
private:
void debug(vector<int>& a) {
for (int t : a) {
cout << t << ' ';
}
puts("");
}
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param A int整型vector
* @param T int整型
* @return int整型
*/
int minSumOfLengths(vector<int>& a, int T) {
// write code here
vector<int> minPrefix(a.size());
int l = 0, cnt = 0, ans = 100000000;
for (int r = 0; r < a.size(); r++) {
cnt += a[r];
while (l < r && cnt > T) {
cnt -= a[l++];
}
if (cnt == T) {
ans = min(ans, r - l + 1);
}
minPrefix[r] = ans;
}
// debug(minPrefix);

vector<int> minSuffix(a.size());
int r = a.size() - 1;
cnt = 0, ans = 10000000;
for (int l = a.size() - 1; l >= 0; l--) {
cnt += a[l];
while (l < r && cnt > T) {
cnt -= a[r--];
}
if (cnt == T) {
ans = min(ans, r - l + 1);
}
minSuffix[l] = ans;
}

ans = 10000000;
for (int i = 0; i + 1 < a.size(); i++) {
ans = min(ans, minPrefix[i] + minSuffix[i + 1]);
}
return ans > a.size() ? -1 : ans;
}
};

这道题第一遍读题没想到思路,第二遍读题想到并且很快AC了。

四:Protocol Buffers序列化和反序列化模拟

题目地址:暂未找到

题目描述

Google采用数字变长编码来传输。 给定一个数字和一个编码后的字符串,输出数字的编码和对字符串解码后的数字。

编码方式: 对于给定数字M,将其转换成二进制,取前七位(低位),并将第八位(高位)作为标志位。如果第八位是1,则说明需要继续编码,是0则说明编码结束。编码结果是纯大写的十六进制字符串,例如0XE3。

对于给定编码字符串S,其是一个纯大写的十六进制表示数字的字符串,比如0XE70X07,其中0XE7是第一个数字,取出来并将16进制转换成二进制,观察其高位是1还是0。是1,则弃其高位,继续计算下边的0X07并拼接到前边的高位上,转换成数字输出回来。

举例:

输入:

1
2
100
0XE70X0&

输出:

1
2
0X64
999

解释:

100 = 0x64 = 0b01100100,高位(第八位)是0,所以编码后是0X64。

0XE70X07 先看0XE7。

0xe7 = 0b11100111,高位为1,所以要继续往后算0X07。

0x07 = 0b00000111,高位为0,所以这个数字应该是:

0b00000111(去掉高位)连接0b11100111(去掉高位)

0b00001111100111 = 999

因此输出应该是0X64和999。

解题思路

就主打一个进制转换、字符串数字转换、细心读题和模拟呗。

AC代码

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
using namespace std;
typedef long long ll;

/*
1100100
4 + 32 + 64 = 100


*/

/*
100 -> 1100100
*/
string itos(ll a) {
string s;
while (a) {
s = char('0' + a % 2) + s;
a >>= 1;
}
return s;
}

/*
0111 -> 7
*/
string _422(string s) {
ll n = 0;
for (char c : s) {
n = n * 2 + c - '0';
}
// cout << "n: " << n << endl;
string ans;
if (n < 10) {
ans = string(1, char('0' + n));
} else {
ans = string(1, char('A' + n - 10));
}
// cout << ans << endl;
return ans;
}

/*
11100111 -> 0XE7
*/
string stos(string s) {
// cout << s << endl;
if (s.size() < 8) {
s = string(8 - s.size(), '0') + s;
}
// cout << "stos: " << s << endl;
return "0X" + _422(s.substr(0, 4)) + _422(s.substr(4, 4));
}

string fi(ll a) {
string s = itos(a);
// cout << s << endl;
string ans = "";
while (s.size() > 7) {
string thisStr = '1' + s.substr(s.size() - 7, 7);
s = s.substr(0, s.size() - 7);
ans += stos(thisStr);
}
ans += stos(s);
return ans;
}

ll c2i(char c) {
if (c <= '9') {
return c - '0';
}
return 10 + c - 'A';
}

string c2s(char c) {
ll n = c2i(c);
string temp = itos(n);
if (temp.size() < 4) {
temp = string(4 - temp.size(), '0') + temp;
}
return temp;
}

/*
0XE7 -> 1100111(丢掉最高位)
*/
string _16_2(string s) {
// cout << "_16_2: " << s << endl;
return (c2s(s[2]) + c2s(s[3])).substr(1, 7);
}

/*
二进制->10进制
*/
ll _2_10(string s) {
ll ans = 0;
for (char c : s) {
ans = ans * 2 + c - '0';
}
return ans;
}

ll fs(string s) {
string bin;
for (ll i = 0; i < s.size(); i += 4) {
bin = _16_2(s.substr(i, 4)) + bin;
}
return _2_10(bin);
}

int main() {
ll a;
string s;
cin >> a >> s;
cout << fi(a) << endl;
cout << fs(s) << endl;
}
// 64 位输出请用 prllf("%lld")

这道题写了好多函数,甚至有重复的。。。

牛客无法调试,中间print了好多次。

但是最终也用屎山代码AC了。

End

考完之后搜考题的时候搜到了一个帖子,竟然是原题!

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


牛客-某公司笔试题-20250316-全解析
https://blog.letmefly.xyz/2025/03/16/Nowcoder-NingMengWeiQu-20250316-YiMian/
作者
Tisfy
发布于
2025年3月16日
许可协议