2021届秋招笔试题汇总

科大讯飞20200815

第1题

定义一个n*m的数字矩阵，要求你再当中找到两个不在用一行同一列的数组，使得乘积最大

输入描述

第一行数字n、m表示矩阵大小
接下来又n行数字，每行m个数字，约定n和m都是小于等于1000，大于等于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
int main() {
    int n , m;
    cin >> n;
    cin >> m;
    vector<vector<int>> arr(n, vector<int>(m, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> arr[i][j];
        }
    }

    int MAX = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int num1 = arr[i][j];
            for (int x = 0; x < n; ++x) {
                for (int y = 0; y < m; ++y) {
                    int num2 = arr[x][y];
                    if (x == i || y == j) continue;
                    MAX = max(MAX, num1 * num2);
                }
            }
        }
    }
    cout <<MAX<<endl;
    return 0;
}

第2题

用某种排序方法对32位整数序列(25,84,21,47,15,27,68,35,20)进行行排序，序列变化的情况如下

1
2
3
21 25 84 47 15 27 68 35 20  
15 20 21 25 35 27 47 68 84
15 20 21 25 27 35 47 68 84

请以该排序方法对其他的输入序列进行排序并输出结果

输入描述：

第一行为给定数字序列中的元素个数
第二行为给定的数字序列，以空格分割

输出描述：

输出排序后的数字序列，以空格分割 

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
int help(vector<int>& arr, int left, int right) {
    int tmp = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= tmp) right--;
        arr[left] = arr[right];
        while (left < right && arr[left] <= tmp) left++;
        arr[right] = arr[left];
    }
    arr[left] = tmp;
    return  left;
}

void qsort(vector<int>& arr, int left, int right) {
    if (left > right) return;
    int mid = help(arr, left, right);
    qsort(arr, left, mid - 1);
    qsort(arr, mid + 1, right);
}

int main() {
    int n = 0;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >>arr[i];
    }
    qsort(arr, 0, n - 1);
    for (int i = 0; i < n; ++i) {
        cout << arr[i] <<" ";
    }
}

第3题

统计数字二进制形式1的个数

1
2
3
4
5
6
7
8
9
10
11
int main() {
    int num;
    cin >> num;
    int cnt = 0;
    while (num) {
        if (num & 1) cnt++;
        num >>= 1;
    }
    cout << cnt;
    return 0;
}

第4题

将一个长度位m的字符串左移n位

输入描述：

第一行位长度位m的字符串
第二行位左移的位数n
1 < n,m < 2000

输出描述：

一行输出左移后的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() {
    string str;
    int n ;
    getline(cin, str);
    cin >> n;
    n %= str.size();
    string res = "";
    int cnt = str.size();
    int idx = n;
    while (cnt--) {
        idx %= str.size();
        res += str[idx++];
    }
    cout << res;
}

大疆2020816

给定一个整数序列，你需要找到两个的子段，保证这两个子段不能重复，并且使得这两个子段中得所有整数得和最大。

输入描述：

1
2
3
4
5
第1行整数，测试用例数
每个测试用例包括3行，
第1行整数，整数序列得长度n
第2行，n个整数
第3行空格

输出描述：

每个测试用例一行，输出一个整数表示最大子段和

示例

1
2
3
4
5
6
7
8
9
10
11
12
input:
3
10
1 -1 2 2 3 -3 4 -4 5 -5
5
-5 9 -5 11 20
10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
output:
13
40
-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
int maxSubArray(vector<int>& nums, int& left, int& right) {
    int len = nums.size();
    vector<int> dp(len);
    int maxSum = nums[0];
    for (int i = 0; i < len; ++i) {
        if (i == 0) dp[0] = nums[0];
        else {
            if (dp[i - 1] + nums[i] < nums[i]){
                dp[i] = nums[i];
                left = i;
            } else {
                dp[i] = dp[i - 1] + nums[i];
            }
        }
        if (maxSum<dp[i]) {
            right = i;
            maxSum = dp[i];
        }
    }
    if (left > right) {
        left = 0, right = 0;
        return dp[0];
    }
    return maxSum;
}

int main() {
    int cnt;
    cin >> cnt;
    vector<vector<int>> input(cnt);
    for (int i = 0; i < cnt; ++i) {
        int n = 0;
        cin >> n;
        input[i].resize(n);
        for (int j = 0; j < n; ++j) {
            cin >> input[i][j];
        }
    }
    for (int i = 0; i < cnt; ++i) {
        int left = 0, right = 0;
        int res = maxSubArray(input[i], left, right);
        sort(input[i].begin(), input[i].begin()+ right - left + 1, less<int>());
        res = left != right ? res - *input[i].begin() : input[i][0] * 2;
        cout << res << endl;
    }
    return 0;
}

美的20200820

  • 部分选择题 
    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
    119
    120
    121
    122
    123
    124
    125
    /******************【1】**********************/
    #include <stdio.h>
    #define  clrscr() 100
    main()
    {
        clrscr();
        printf("%d\n", clrscr());
    }
    /******************【2】**********************/
    void main()
    {
        char* p = "ayqm";
        printf("%c", ++*(p++));
    }
    /******************【3】**********************/
    int main()
    {
        int const* p = 5;
        printf("%d", ++(*p));
        return 0;
    }
    /******************【4】**********************/
    void main()
    {
        struct emp
        {
            char name[20];
            int age;
            float sal;
        };
        struct emp e = {"Tiger"};
        printf("\n%d %f", e.age, e.sal);
    }
    /******************【5】**********************/
    struct A{
        long a1;
        short a2;
        int a3;
        int *a4;
        char c;
        char c2;
    };
    /******************【6】**********************/
    struct S1 {
        char c;
        int i[2];
        double v;
    } SA1;
    struct S2{
        double x;
        int i[2];
        char c;
    }SA2;

    int main()
    {
        printf("\n sizeof S1 %d: sizeof S2 %d", sizeof(SA1), sizeof(SA2));
        return 0;
    }
    /******************【7】**********************/
    int main() {
        char s[] = {'a','b','c','\n','c','\0'};
        char *p, *str, *str1;
        p = &s[3];
        str = p;
        str1 = s;
        printf("%d", ++*p + ++*str1 - 32);
        return 0;
    }
    /******************【8】**********************/
    void main() {
        enum {i = 10, j = 20, k = 50};
        printf("%d", ++k);
    }
    /******************【9】**********************/
    #define FALSE -1
    #define TRUE 1
    #define NULL 0
    int main() {
        if (NULL)
            puts("NULL");
        else if(FALSE)
            puts("TRUE");
        else
            puts("FALSE");
    }
    /******************【10】**********************/
    void main(){
        unsigned int m = 32;
        printf("%X", ~m);
    }
    /******************【11】**********************/
    #define square(x) x * x
    void main() {
        int i ;
        i = 64 / square(4);
        printf("%d", i);
    }
    /******************【12】**********************/
    void swap(int *a, int *b) {
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
    void main(){
        int x = 10, y = 8;
        swap(&x, &y);
        printf("x = %d y = %d", x, y);
    }
    /******************【13】**********************/
    #if something == 0
    int some = 0;
    #endif
    void main(){
        int thing = 0;
        printf("%d %d\n", some, thing);
    }
    /******************【14】**********************/
    int main() {
        char *p;
        p = "Hello";
        printf("%c\n", *&*p);
        return 0;
    }

商汤科技20200820

选择题：

2、 transformer的位置编码使用交替的多维sin、cos函数实现，不属于设计原理的一项是。

  • 对于不同长度的序列，其相隔同样距离的两个序列元素，进行位置编码后的编码值的距离相同。
  • 保持序列中的绝对位置关系。
  • 保证序列中元素在一定范围内的相对位置关系。
  • 限定在固定值域内，避免不同长度序列取值范围不同，以及过大数值对序列的影响。
    3、 链表访问i位置的时间复杂度。
    4、 现代CPU都有较大的缓存，cache来提高内存的访问效率。
  • c的数组的访问可以使用cache来加速，但数组大小不要超过cache大小
  • cache使用需要考虑到不用的cpu核的同步
  • cache的访问时按cache entry来进行的，c的数组需要按行优先访问
  • 一般的cache越大，程序效率越高
    5、 当多个程序连接动态库，所占内存是多少
    6、 docker使用什么技术来运行环境的隔离

    编程题：

    给出一个数字矩阵，寻找一条最上上升路径，每个位置只能向上下左右四个位置移动

    示例

    1
    2
    3
    4
    5
    9 1 4
    6 2 8 
    5 5 7
    [1, 2, 5, 7, 8]
    输出5
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int row, col;
int cnt;
vector<int> res;
int dff[4][2] = {{1, 0}, {-1, 0},{0, 1},{0, -1}};

void dfs(int x, int y, vector<vector<int>>& arr, vector<vector<bool>>& isVis) {
    if (isVis[x][y]) return;
    isVis[x][y] = true;
    cnt++;

    int MAX = INT_MIN;
    for (int i = 0; i < 4; ++i) {
        int m = x + dff[i][0];
        int n = y + dff[i][1];
        if (m < row && m >= 0 && n < col && n >= 0){
            MAX = max(MAX, arr[m][n]);
        }
    }
    if (arr[x][y] > MAX) {
        res.push_back(cnt);
        return;
    }

    for (int i = 0; i < 4; ++i) {
        int m = x + dff[i][0];
        int n = y + dff[i][1];
        if (m < row && m >= 0 && n < col && n >= 0 && arr[m][n] > arr[x][y]){
            dfs(m, n,arr,isVis);
        }
    }
    isVis[x][y] = false;
    cnt--;
}

int main() {
    cin >> row;
    cin >> col;
    vector<vector<int>> arr(row, vector<int>(col, 0));
    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
            cin >> arr[i][j];
        }
    }

    int MIN = INT_MAX;
    int min_x = 0, min_y = 0;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; ++j) {
            if (arr[i][j] < MIN) {
                min_x = i;
                min_y = j;
                MIN = arr[i][j];
            }
        }
    }
    vector<vector<bool>> isVis(row, vector<bool>(col, false));

    dfs(min_x, min_y, arr, isVis);
    sort(res.begin(), res.end());
    cout << res.back();
    return 0;
}

中兴20200824

选择题

1、shell语言连接到127.0.0.1：8080服务器上的所有ip。netstat -anp | grep "127.0.0.1:8080" | awk - F':' '{print $5}'
2、手动测试和自动化测试的区别。
3、在浏览器里面输入http网址，哪些协议不会用到：

1
ARP,SMTP,IP,HTTP,DNS,TCP

4、平衡二叉树AVL失衡，时空复杂度。
5、构建类的设计模式。
6、某个服务器通过域名+端口无法访问，但通过IP+端口可以访问的原因

编程题

第一题：

给定一个长度为n得数组a,求最大连续子区间内平均数最大得值。

输入描述

1
2
9					// 数组长度
3 5 3 7 7 6 6 5 6	// 数组

输出

1
7		// 最大平均子区间为[4, 5],值为7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
    int n = 0;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    
    vector<int> dp(n);
    dp[0] = arr[0];
    int left = 0;
    for (int i = 1; i < n; ++i) {
        int avg = (dp[i - 1] + arr[i]) / (i - left + 1);
        if (avg > arr[i]) {
            dp[i] = avg;
        } else {
            dp[i] = arr[i];
            left = i;
        }
    }
    sort(dp.begin(), dp.end());
    cout << dp[n - 1];
    return 0;
}

第二题：

给出一个字符串S，S中可能包含(0-9)和(A-Z),现在我们将字符串S(x)看作一个由x进制转为十进制的数字，
给定l和r(l <= r)，问S(l) + S(l + 1) … S(r - 1) + S(r - 1)是奇数还是偶数？

输入描述

1
2
3
2			// 测试的字符串组数
101 2 3		// 计算2进制到3进制所有数字十进制下之和，并判断奇偶。
4B 12 13

输出描述:

1
2
1
0
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
int transfer(string s, int x) {
    int sum = 0,k = 1;
    for (int i = s.size() - 1; i >= 0; i--) {
        if (s[i] >= 'A' && s[i] <= 'Z')
            sum += (s[i] - 'A' + 1 + 9) * k;
        else
            sum += (s[i] - '0') * k;
        k *= x;
    }
    return sum;
}

int main() {
    int n = 0;
    cin >> n;
    vector<string> num(n);
    vector<int> x(n), y(n);
    for (int i = 0; i < n; ++i) {
        cin >> num[i] >> x[i] >> y[i];
    }

    for (int i = 0; i < n; ++i) {
        int ans = 0;
        for (int j = x[i]; j <= y[i]; ++j) {
            ans += transfer(num[i], j);
        }
        cout << ((ans & 1) == 1) <<endl;
    }
    return 0;
}

汇顶科技20200824

部分选择题

奇偶校验
static关键字作用
do while循环次数

编程题

查找一行字符串中子字符串的个数。

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
#include <stdio.h>

int del_sub(char* str, char* sub)
{
    int cnt = 0;
    while(*str != '\0') {
        char* s1 = str;
        char* s2 = sub;
        while(*s2 == *s1 && *s2 != '\0' && *s1 != '\0') {
            s2++;
            s1++;
        }
        if(*s2 == '\0') cnt++;
        str++;
    }
    return cnt;
}

int main() {
    char str[100];
    char sub[100];
    int num = 0;
    scanf("%s",str);
    scanf("%s",sub);
    num = del_sub(str, sub);
    printf("%d",num);
}

科大讯飞20200829

编程题

第一题：

写一个函数用递归实现将一个正整数分解质因数，如50，则程序打印”255”

输入描述

1
50

输出描述：

1
2*5*5

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string s;
void fun(int n){
    if (n == 1 || n == 0) return;
    for (int i = 2; i <= n; i++){
        if (n % i == 0) {
            s += ('0' + i);
            s += '*';
            fun(n / i);
            break;
        }
    }
}

int main() {
    int n;
    cin >> n;
    fun(n);
    s.pop_back();
    cout << s;
    return 0;
}

第二题：

去除多余的下划线，要求再原串上进行操作

输入描述

1
___aaa__b___c__dd__

输出描述：

1
aaa_b_c_dd

代码

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
void deleteSpace(string& str) {
    int cur = 0;
    while (str[cur] == '_') cur++;
    int tail = 0;
    while (cur < str.size()) {
        if (str[cur] != '_')
            str[tail++] = str[cur];
        if (str[cur] == '_' && str[cur - 1] != '_')
            str[tail++] = str[cur];
        cur++;
    }
    cur--;
    while (str[cur] == '_') {
        str.pop_back();
        cur--;
    }
}


int main() {
    string str;
    cin >> str;
    deleteSpace(str);
    cout << str;
    return 0;
}

美的20200831

  • 部分选择题
    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
    119
    120
    121
    122
    123
    124
    125
    126
    127
    #define prod(a, b) a * b
    int main() {
        int x = 3,y = 4;
        printf("%d",prod(x + 2, y -1));
        return 0;
    }

    int main() {
        unsigned char C = 32;
        printf("%d %d", C ^= C, !(C & 128) && !(C & 1));
        return  0;
    }

    int main() {
        char s[] = {'a','b','c','\n','c','\0'};
        char *p, *str, *str1;
        p = &s[3];
        str = p;
        str1 = s;
        printf("%d", ++*p + ++*str1 - 32);
        return 0;

    }

    #define square(x) x * x
    int main() {
        int i ;
        i = 64 / square(4);
        printf("%d", i);
        return 0;
    }

    int main() {
        float a = 5.375;
        char *p;
        int i;
        p = (char*) &a;
        for (int i = 0; i <= 3; i++)
            printf("%02X", (unsigned char)p[i]);
    }

    #define max(a,b) (a > b) ? a : b
    int main(){
        int a,b;a=3;b=4;
        printf("%d", ++max(a++,b--));
        return 0;
    }

    #define f(g, g2) g##g2
    int main(){
        int var12 = 100;
        printf("%d", f(var,12));
        return 0;
    }

    void change(int* a, int &b,int c){
        c =* a;
        b = 30;
        *a = 20;
    }
    int main() {
        int a = 10, b = 20, c = 30;
        change(&a,b, c);
        printf("%d, %d, %d", a, b, c);
        return 0;
    }

    struct myStruct{
        int a;
        char b;
    }*ptr;

    int main() {
        struct myStruct ms = {400,'A'};
        printf("%d  %d", ptr->a, ptr->b);
        return 0;
    }

    typedef  struct Error
    {
        int warning;
        int error;
        int exception;
    }error;
    int main() {
        error g1;
        g1.error = 1;
        printf("%d", g1.error);
        return 0;
    }

    int main() {
        int i = 10;
        i = !i > 14;
        printf("i=%d",i);
        return 0;
    }

    int main() {
        int x, y = 2, z, a;
        x = (y *= 2) + ( z = a = y);
        printf("%d", x);
        return 0;
    }

    int main(){
        unsigned char i = 0x80;
        printf("\n%d",i << 1);
        return 0;
    }

    int main() {
        char *p;
        p = "hello";
        printf("%c\n", *&*p);
        return 0;
    }

    int main() {
        int x, y = 2, z, a;
        if (x = y % 2);
        z=2;
        a=2;
        printf("%d %d",z,x);
        return 0;
    }

中兴20200903

编程题二：

A城和B城是双向路径，求A城到B城的最短路径

输入描述：

1
2
3
4
5
6
7
5 3 3	// n m q 代表：n个城市 m条双向路径 q次询问
1 2 1	// x y l 代表x到y有一条距离为l的双向路径
2 3 1	
3 5 2
1 2		// a b 代表要询问的两个城市
2 4
1 5

输出描述：

1
2
3
1		// 查询的最短路，若不存在输出-1
-1
4

代码

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
vector<vector<int>> graph;
vector<vector<int>> dist;
vector<bool> isVis;
int MIN = INT_MAX;

void dfs(int cur, int dst, int distance) {
    if (cur == dst) {
        MIN = min(MIN, distance);
    }
    for (auto v : graph[cur]) {
        if (isVis[v]) continue;
        isVis[v] = true;
        distance += dist[cur][v];
        dfs(v, dst, distance);
        isVis[v] = false;
        distance -= dist[cur][v];
    }
}

int main() {
    int n, m, q;
    cin >> n;
    cin >> m;
    cin >> q;
    graph.resize(n + 1);
    dist.resize(n + 1, vector<int>(n + 1, 0));
    isVis.resize(n + 1, false);
    for (int i = 0; i < m; ++i) {
        int u = 0, v = 0, dis = 0;
        cin >> u;
        cin >> v;
        cin >> dis;
        graph[u].push_back(v);
        graph[v].push_back(u);
        dist[u][v] = dis;
        dist[v][u] = dis;
    }

    int src[q], dst[q];
    for (int i = 0; i < q; ++i) {
        cin >> src[i];
        cin >> dst[i];
    }

    for (int i = 0; i < q; ++i) {
        MIN = INT_MAX;
        dfs(src[i], dst[i], 0);
        cout << ((MIN == INT_MAX) ? -1 : MIN) << endl;
    }
    return 0;
}

深信服20200910

选择题考点：

  • 时间复杂度
  • 结构体内存对齐
  • 位运算符
  • 八大排序算法时间复杂度

编程题：

x*y的矩阵，从一个房间进入，从另一个房间出来，要求不重复的走完全部房间的路径数量。

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
int off[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<bool>> isVis;
int row, col;
int cnt = 0;
int endX, endY;
void dfs(int x, int y, int depth)
{
	if (isVis[x][y]) return;
	isVis[x][y] = true;
	depth++;
	if (x == endX && y == endY && depth == row * col) {
		cnt++;
		isVis[x][y] = false;
		return;
	}
	for (int i = 0; i < 4; ++i) {
		int m = x + off[i][0];
		int n = y + off[i][1];
		if (m >= 0 && m < row && n >= 0 && n < col && !isVis[m][n])
			dfs(m, n, depth);
	}
	depth--;
	isVis[x][y] = false;
}


int main()
{
	cin >> row;
	cin >> col;
	isVis.resize(row, vector<bool>(col, false));
	int stratX, startY;
	cin >> stratX;
	cin >> startY;
	cin >> endX;
	cin >> endY;
	dfs(stratX, startY, 0);
	cout << cnt << endl;
	system("pause");
	return 0;
}

网易20200912

编程题1

一颗二叉树，叶子结点定义为“樱桃”，统计一串上刚好有两颗“樱桃”的串的个数

输入描述：

1
2
3
3 2		// 3个结点 2条边
1 1 2	// 1的左子树为2
1 2 3	// 1的右子树为3
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
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int cnt = 0;

void dfs(TreeNode* root) {
	if (!root) return;
	if (root->left && root->right &&
		!root->left->left && !root->left->right && 
		!root->right->left && !root->right->right) 
		cnt++;
	dfs(root->left);
	dfs(root->right);
}

int main() {
	int n, m;
	cin >> n;
	cin >> m;
	unordered_map<int, TreeNode*> hash;
	for (int i = 0; i < m; ++i) {
		int uid, dir, vid;
		cin >> uid;
		cin >> dir;
		cin >> vid;
		
		if (hash.find(uid) == hash.end()) {
			hash[uid] = new TreeNode(uid);
		}
		
		if (dir == 1) { // left
			if (hash.find(vid) == hash.end())
				hash[vid] = new TreeNode(vid);
			hash[uid]->left = hash[vid];
		} else {			// right
			if (hash.find(vid) == hash.end())
				hash[vid] = new TreeNode(vid);
			hash[uid]->right = hash[vid];
		}
	}

	dfs(hash[1]);
	cout << cnt;
	return 0;
}

编程题2

快递员城市中送快递，每个城市距离1km，求图的最大深度

输入描述：

1
2
6 3			// 共6个城市 还能再开3公里
0 0 2 3 3 	// 想象成一个数组S[5] 下标i+1 到 S[i]之间有一条路径
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
vector<bool> isVis;
vector<vector<int>> G;
int depth = 0;
int MAX = 0;

void dfs(int root) 
{
	if (isVis[root]) return;
	isVis[root] = true;
	depth++;
	MAX = max(MAX, depth);
	for (auto v : G[root]) {
		dfs(v);
	}
	depth--;
	isVis[root] = false;
}

int main() 
{
	int n, k;
	cin >> n;
	cin >> k;
	G.resize(n);
	isVis.resize(n, false);
	for (int i = 0; i < n - 1; ++i) {
		int v;
		cin >> v;
		G[i+1].push_back(v);
		G[v].push_back(i+1);
	}
	dfs(0);
	cout << (MAX > (k + 1) ? (k + 1) : MAX);
	return 0;
}

编程题3

给定一个字符串，求最长字符串的长度，前提这个字符串满足aeiou元音字母在字符串中出现次数刚好为偶数次

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
//暴力法会超时
bool judge(const string &str) {
	char count[256];
	for (char i : str) {
		count[i]++;
	}
	return count['a'] % 2 == 0 &&
		count['e'] % 2 == 0 &&
		count['i'] % 2 == 0 &&
		count['o'] % 2 == 0 &&
		count['u'] % 2 == 0;
}

int sol(const string &s) {
	int maxVal = 0;
	for (int i = 0; i < s.length(); i++) {
		for (int j = i; j < s.length(); j++) {
			if (judge(s.substr(i, j + 1 - i))) {
				maxVal = max(maxVal, j - i + 1);
			}
		}
	}
	return maxVal;
}

int main() {
	string str;
	getline(cin, str);
	cout << sol(str);
	return 0;
}

VIVO20200912

编程题1

给定非空字符串str，在最多可以删除一个字符情况下，判定能够成为回文串，
如果可以则输出首次删除一个字符所能得到的回文字，如果不行则输出字符串“false”

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
bool isPali(string str) {
	int left = 0, right = str.size() - 1;
	while (left < right) {
		if (str[left] != str[right]) return false;
		left++, right--;
	}
	return true;
}

int main3()
{
	string str;
	getline(cin, str);
	string res = "false";
	for (int i = 0; i < str.size(); ++i) {
		string s = str;
		if (isPoli(s)) {
			res = s;
			break;
		}else if (isPali(s.erase(i, 1))) {
			res = s;
			break;
		}
	}
	
	cout << res;
	return 0;
}

编程题2

矩形格子，字符 ‘@’ 和 ‘#’ 代表障碍物，指定起点和终点，求最短路径的长度，无法到达则返回-1

输入描述

1
2
3
4
5
3			// 维度为3*3的矩形
0 0 2 2		// 起点 （0，0）终点（2，2）
1@3			// 迷宫描述
1@#
123
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
vector<vector<char>> map;
vector<vector<bool>> isVis;
int endX, endY, n;
int depth = 0;
int MIN = INT_MAX;
int off[4][2] = { {1,0}, {-1,0}, {0,1}, {0, -1} };

void dfs(int x, int y)
{
	if (isVis[x][y]) return;
	isVis[x][y] = true;
	depth++;

	if (x == endX && y == endY) {
		MIN = min(MIN, depth);
		return;
	}
	for (int i = 0; i < 4; ++i) {
		int xi = x + off[i][0];
		int yi = y + off[i][1];
		if (xi >= 0 && xi < n && yi >= 0 && yi < n &&
			map[xi][yi] != '#' && map[xi][yi] != '@') {
			dfs(xi, yi);
		}
	}
	depth--;
	isVis[x][y] = false;
}

int main() 
{
	int startX, startY;
	cin >> n;
	cin >> startX;
	cin >> startY;
	cin >> endX;
	cin >> endY;
	map.resize(n, vector<char>(n, ' '));
	isVis.resize(n, vector<bool>(n, false));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> map[i][j];
		}
	}

	dfs(startX, startY);
	cout << (MIN == INT_MAX ?  -1 : MIN );
	return 0;
}

美团点评20200913

编程题1

回文矩阵，按行回文，找到最小非回文矩阵

输入描述：

1
2
3
4
5
6
7
8
9
8 3		// 8 * 3矩阵
1 0 1
0 1 0
0 1 0
1 0 1
1 0 1
0 1 0
0 1 0
1 0 1

输出描述：

1
2
1 0 1
0 1 0
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
int n, m;
vector<vector<int>> arr;

bool operator != (const vector<int>& v1, const vector<int>& v2) {
	for (int i = 0; i < v1.size(); ++i) {
		if (v1[i] != v2[i])
			return true;
	}
	return false;
}

bool isPali(vector<vector<int>> arr) 
{
	int left = 0, right = arr.size() - 1;
	while (left < right) {
		if (arr[left] != arr[right])
			return false;
		left++, right--;
	}
	return true;
}

int main1() {
	cin >> n;
	cin >> m;
	arr.resize(n, vector<int>(m, 0));

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> arr[i][j];
		}
	}

	int right = n;
	while (right) {
		if (isPali(arr)) {
			right /= 2;
			arr.erase(arr.begin() + right, arr.end());
			continue;
		} 
		break;
	}
	for (auto lev : arr) {
		for (auto num : lev) {
			cout << num << " ";
		}
		cout << endl;
	}
	return 0;
}

编程题2

一个齿轮，26个齿A~Z，每个齿轮两个按钮，按钮1：跟前轮啮合并逆时针转一格，按钮2：跟后轮啮合并逆时针转一格，按完按钮恢复原状。
用所有齿轮正上方的字母组成一个字符串，给定初始齿轮状态，统计所有无重复字符串的个数。
注意：A不能转到Z，Z不能转到A,

输入描述：

1
2
3
4
2	// 2个齿轮
BB	// 2个齿轮初始状态 B B
3	// 3个齿轮
ABA	// 3个齿轮初始状态 A B A

输出描述：

1
2
3	// 结果对998244353取模
3	
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
vector<string> res;
long sol(string str) {
	res.clear();
	string s = str;
	for (int i = 0; i < str.size(); ++i) {
		if (i == 0) {
			s = str;
			s[i] += 1;
			s[i + 1] -= 1;
			if (s[i] <= 'Z' && s[i + 1] >= 'A')
				res.push_back(s);
		} else  if (i == str.size() - 1) {
			s = str;
			s[i] += 1;
			s[i - 1] -= 1;
			if (s[i] <= 'Z' && s[i - 1] >= 'A')
				res.push_back(s);
		} else {
			s = str;
			s[i] += 1;
			s[i + 1] -= 1;
			if (s[i] <= 'Z' && s[i + 1] >= 'A')
				res.push_back(s);
			s = str;
			s[i] += 1;
			s[i - 1] -= 1;
			if (s[i] <= 'Z' && s[i - 1] >= 'A')
				res.push_back(s);
		}
	}
	unordered_set<string> set(res.begin(), res.end());
	return (set.size() + 1) % 998244353;
}

int main() {
	int n;
	string str;
	vector<string> strs;
	while (getline(cin, str)) { 	// 必须使用ctrl + z结束输入
		if (str[0] >= '0' && str[0] <= '9') continue;
		strs.push_back(str);
	}
	for (int i = 0; i < strs.size(); ++i) {
		cout << sol(strs[i]) <<endl;
	}
	return 0;
}

联发科20200915

选择题考点：

  • linux进程间通信有哪些
  • 关于内存泄漏
  • C++函数中参数传递的方式
  • static修饰的局部变量、全局变量、函数、成员变量的作用分别是
  • 列举TCP/IP五层参考模型
  • 可执行程序加载时系统分配的内存可以分为哪几段

编程题1

手写查找子字符串C函数int strstr(char * str1, char * str2)

1
2
输入："abcdefabcdef","def"
输出：3		//找到输出第一个下标 没找到输出-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
int  my_strstr(char* str1, char* str2) {
	if (str2 == NULL) return -1;
	int idx = 0;
	while (*str1 != '\0') {
		if (*str1 != *str2) {
			str1++;
			idx++;
		} else {
			char * p1 = str1;
			char * p2 = str2;
			while (*p2 != '\0') {
				if (*p2 == *p1) {
					p1++; p2++;
				} else {
					break;
				}
			}
			if (*p2 == '\0') return idx;
		}
	}
	return -1;
}

int main() {
	char str1[100];
	char str2[100];
	cin >> str1;
	cin >> str2;
	printf("%d\n", my_strstr(str1, str2));
	return 0;
}