美团2020秋招笔试真题

1、LRU缓存机制

【题目描述】设计和实现一个LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据get和写入数据 put 。

获取数据get(key)-如果密钥 (key)存在于缓存中，则获取密钥的值（总是正数），否则返回-1。

写入数据put(key, value)-如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

输入描述

第一行输入缓存容量，包含一个整数N，1≤N≤10。

接下来，每一行是一个put或者get的操作。

若输入一个get+一个数字，则代表get操作和指定的key；

若输入一个put+两个数字，则代表put操作后面为key和value，进行put操作。

读到文件结束

输出描述

输出多行，每一行两个数字表示缓存中的key 和value。按照访问时间或者插入时间，越早的越先输出。

示例1

输入

2
put 1 1
put 2 2
get 1
put 3 3
get 1

输出

3 3
1 1

【解题思路】

根据题设要求实现两个操作，用hash表来维护数据。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
void get(int key, unordered_map<int, int> &hash, list<int> &l) {
    if (hash.find(key) == hash.end())
        return;
    for (auto it = l.begin(); it != l.end(); it++) {
        if (*it == key) {
            l.erase(it);
            break;
        }
    }
    l.push_back(key);
    // return hash[key];
}
void put(int key, int value, unordered_map<int, int> &hash, list<int> &l,
         int N) {
    if (hash.find(key) != hash.end()) {
        for (auto it = l.begin(); it != l.end(); it++) {
            if (*it == key) {
                l.erase(it);
                break;
            }
        }
    }
    l.push_back(key);
    hash[key] = value;
    if (l.size() > N) {
        hash.erase(*l.begin());
        l.pop_front();
    }
}
int main() {
    int N;
    cin >> N;
    unordered_map<int, int> hash;
    list<int> l;
    string s;
    int a, b;
    while (cin >> s) {
        if (s == "put") {
            cin >> a >> b;
            put(a, b, hash, l, N);
        } else if (s == "get") {
            cin >> a;
            get(a, hash, l);
        }
    }
    for (auto it = l.begin(); it != l.end(); it++) {
        cout << (*it) << " " << hash[(*it)] << endl;
    }
    return 0;
}

2、代金券组合

【题目描述】近期某商场由于周年庆，开启了“0元购”活动。活动中，消费者可以通过组合手中的代金券，实现0元购买指定商品。

聪明的小团想要用算法来帮助他快速计算：对于指定价格的商品，使用代金券凑出其价格即可，但所使用的代金券总面额不可超过商品价格。由于代金券数量有限，使用较少的代金券张数则可以实现价值最大化，即最佳优惠。

假设现有100元的商品，而代金券有50元、30元、20元、5元四种，则最佳优惠是两张50元面额的代金券；而如果现有65元的商品，则最佳优惠是两张30元代金券以及一张5元代金券。

请你帮助小团使用一段代码来实现代金券计算。

输入描述

多组输入输出，读到s=0时结束

输入可以有多个测试样例，每个测试由两行组成。

其中第一行包含一个整数P，表示商品的价格，1≤P≤10000；输入P为0时表示结束。

第二行包含若干整数，使用空格分割。其中第一个整数N（1≤N≤20）表示有多少种代金券，其后跟随M个整数，表示手中持有的代金券面额（1≤N≤1000），每种代金券数量不限。

输出描述

找到最少张数的代金券，使其面额恰好等于商品价格。输出所使用的代金券数量；

如果有多个最优解，只输出其中一种即可；

如果无解，则需输出“Impossible”。

示例1

输入

65
4 50 30 20 5
0

输出

【解题思路】

经典背包问题，使用动态规划即可。

【参考代码】

#include <iostream>
using namespace std;
int n, m, dp[100001], temp, a[20];
int main() {
    while (cin >> n) {
        for (int i = 0; i <= 100000; i++) {
            dp[i] = -1;
        }
        if (n == 0) {
            break;
        }
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> temp;
            a[i] = temp;
            if (temp <= n) {
                dp[temp] = 1;
            }
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[j] < i && dp[i - a[j]] != -1) {
                    if (dp[i] == -1) {
                        dp[i] = dp[i - a[j]] + 1;
                    } else {
                        dp[i] = min(dp[i], dp[i - a[j]] + 1);
                    }
                }
            }
        }
        if (dp[n] == -1) {
            cout << "Impossible" << endl;
        } else {
            cout << dp[n] << endl;
        }
    }
    return 0;
}