牛客-某公司笔试题-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和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

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