美团23秋招笔试后端

2022-08-27 美团笔试

第一题

样例：

input:
7 3
abcaacc
a*c

output:
3

// 美团0827第一题

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

/**
m 是短的那个子串的长度
*/
//bool check(string s1, string s2, int m)
//{
//    cout << s2 << endl;
//    for (int i = 0; i < m; i++)
//    {
//        if (s1[i] != '*' && s1[i] != s2[i])
//            return false;
//    }
//    return true;
//}


int main()
{
    LL n,m;
    cin >> n >> m;

    string s1, s2;

    cin >> s1 >> s2; // s1 : abcaacc, s2: a*c
    LL res = 0;
    ////////////////////////
//    for (int i = 0; i <= n - m; i++)
//        // s1.substr(0, 3)左闭右开 -> s1[0,2],
//        // 取s1的部分子串和 s2 进行比较，判断是否匹配，是返回1
//        res += check(s2, s1.substr(i, m), m) ? 1 : 0;
//
//    cout << res;

    ////////////////////////

    for (int i = 0; i <= n - m; i ++)
    {
        bool flag = true; // 初始为true，如果s2和s1的子串tmp有不匹配的，就为false

        string tmp = s1.substr(i, m); // 子串的长度为 m
        for (int j = 0; j < m; j++)
        {
            if (s2[j] != '*' && tmp[j] != s2[j])
                flag = false;
        }

        // 如果满足m个字符都匹配，就把结果res ++;
        if (flag) res ++;
    }
    cout << res;
    return 0;
}

第二题

c++版本

/*
input:
5 3
5 4 3

5 3
3 4 3

output:
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
*3 4 5 1 2*
*/

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 50010;
// int a[N]; 使用vector而不是数组

int main()
{

    int n, m;
    cin >> n >> m;

    vector<int> a(n, 0); // 初始化vector

    for (int i = 1; i <= n; i ++) {
        a[i - 1] = i;
    }

    for (int i = 0; i < m ; i++)
    {
        int x;
        cin >> x;
        // 需要把x放到a数组的最左边，也就是先找到x并删除，再把x插入到a的首部
        a.erase(find(a.begin(), a.end(), x));
        a.insert(a.begin(), x);
    }

    for (auto x : a)
        printf("%d ", x);
    return 0;
}

c++与Java的容器对着

Java版本

其中 c++ 的 map 就是 Java 的 TreeMap, key-value映射，按照key有序

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        Map<Integer, Integer> k2v = new HashMap<>();
		
		// 有序 map 的定义
        TreeMap<Integer, Integer> v2k = new TreeMap<>((x, y) -> y - x);
        for (int i = 0; i < m; i++) {
            int num = sc.nextInt();
            if (k2v.containsKey(num)) {
                int v = k2v.get(num);
                v2k.remove(v);
                k2v.put(num, i);
                v2k.put(i, num);
            }
            k2v.put(num, i);
            v2k.put(i, num);
        }
        for (int v : v2k.keySet()) System.out.print(v2k.get(v) + " ");
        for (int i = 1; i <= n; i++) {
            if (!k2v.containsKey(i)) System.out.print(i + " ");
        }
    }
}

• 第三题

• 第四题

• 第五题