盛趣游戏2020秋招笔试真题

1、最长公共部分

【题目描述】求出两个给定串的最长公共部分

输入描述

输入两行字符串

输出描述

输出公共部分

示例1

输入

11223344
112223344

输出

223344

【解题思路】

经典动态规划问题。最长公共子串

【参考代码】

#include <stdio.h>
#include <string.h>
 
int main() {
    char str[50000], patter[50000];
    scanf("%s", str);
    scanf("%s", patter);
    if (strlen(str) < strlen(patter)) {
        char temp[50000];
        strcpy(temp, str);
        strcpy(str, patter);
        strcpy(patter, temp);
    }
    int len = 0, maxlen = 0;
    char *res;
    for (int i = strlen(str) - 1; i >= strlen(patter); --i) {
        for (int k = strlen(patter) - 1; k >= 0; --k) {
            if (str[k + i - strlen(patter) + 1] == patter[k]) {
                len++;
            } else if (len > maxlen) {
                maxlen = len;
                res = &str[i + k - len];
                len = 0;
            } else
                len = 0;
        }
    }
    for (int i = 0; i < maxlen; ++i) {
        printf("%c", *(res + i));
    }
    printf("\n");
    return 0;
}

2、计算bits个数

【题目描述】给定一个64bit整数, 计算bit位为1的个数

输入描述

收入一个64bit的整数, 例如3

输出描述

输出2

示例1

输入

17

输出

2

【解题思路】

位运算，拆分64位整数的每一位。

【参考代码】

#include <iostream>
using namespace std;
int main() {
    long long int a;
    cin >> a;
    int count = 0;
    for (int i = 0; i < 64; i++) {
        if (a >> i & 1)
            count++;
    }
    cout << count;
}

3、购买玩具

【题目描述】现在有一笔钱, 要去采购玩具, 最多可以买多少种玩具

输入描述

输入一个玩具价格的数组和总钱数,例如: [1, 2, 3, 4, 5],10

输出描述

输出可以购买的玩具种类个数:4

示例1

输入

[1,2,3,4,5],10

输出

4

【解题思路】

贪心，优先购买价格低的玩具。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
int main() {
    string vec;
    getline(cin, vec);
    int mey;
    cin >> mey;
    vector<int> arr;
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i] == ' ')
            continue;
        int num = 0;
        if (vec[i] <= '9' && vec[i] >= '0') {
            while (vec[i] <= '9' && vec[i] >= '0') {
                num = num * 10 + vec[i] - '0';
                i++;
            }
            arr.push_back(num);
        }
    }
 
    sort(arr.begin(), arr.end());
    int count = 0;
    int j = 0;
    while (mey >= 0 && j < a