2023-08-27

字数统计: 4.3k字 | 阅读时长: 21分

2023美团编程题

5. 小美的数组操作2

小美拿到了一个数组，她每次可以进行如下操作：
选择两个元素，一个加 1，另一个减 1。
小美总共进行了k次操作。她希望你回答最终数组是否是非降序，你能帮帮她吗？
请注意，元素可能会被减成负数！

输入描述：

第一行输入一个正整数 ，代表询问次数。
每次询问首先第一行输入两个正整数和，代表数组长度和操作次数。
接下来的一行输入个正整数 ，代表初始数组。
接下来的行，每行输入两个正整数，代表使得第个元素加 1，第个元素减 1。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int count, i, j;
    int n, k, num, flag;
    vector <int> vec;
    bool result;
    cin >> count;
    while(count--) {
        cin >> n >> k;
        vec.resize(n);
        for(int i = 0; i < n; i++) {
            cin >> num;
            vec[i] = num;
        }
        while(k--) {
            cin >> i >> j;
            vec[i - 1]++;
            vec[j - 1]--;
        }
        flag = 0;
        for(int i = 0; i < vec.size() - 1; i++) {
            if(vec[i] > vec[i + 1]) {
                flag = 1;
                continue;
            }
            //cout << vec[i] << ' ';
        }
        if(flag == 0)
            cout << "Yes" << endl;
        if(flag == 1)
            cout << "No" << endl;
    }
}
// 64 位输出请用 printf("%lld")

7.美团商家注册系统

请你开发一个美团商家测试系统，并用等价划分法确认商家注册信息是否成功。
商家信息必须满足以下条件：

系统中第一次注册的商家名字，被视为主店。
系统中若出现重名商家，需要判断地址是否已存在该商家。若存在，则注册失败。否则注册成功，该商家被视为分店。
商家的名字和地址必须由小写的英文字母组成，否则注册失败。
请你输出每个商家的信息，按商家名字的字典序升序输出。需要输出商家名字，商家主店地址，商家分店数量。

输入描述：

第一行输入一个正整数，代表注册信息数量。
接下来的行，每行输入两个字符串，用空格隔开。分别代表商家名字和商家地址。

给定的商家名字和商家地址字符串长度不超过 20，且不包含空格。

输出描述：

1	按商家名字字典序输出全部商家信息。每行输出一个，分别输出商家名字，商家主店地址，商家分店数量，用空格隔开。

#include <iostream>
#include <map>
#include <unordered_map>
#include <set>
#include <vector>
using namespace std;

int main() {
    unordered_map<string, int> map2;	//计数，分店的数量，实际上不用也行，tmp2的set的size实际上就是分店的数量
    map <string, string> tmp;
    unordered_map<string, set <string>> tmp2;
    set <string> result;
    int count, flag, flag2, k = 0;
    cin >> count;
    string company_name, company_address;
    while(count--) {
        flag = 0;
        flag2 = 0;
        cin >> company_name >> company_address;
        for(int i = 0; i < company_name.size(); i++) {
            if((company_name[i] > 'z' || company_name[i] < 'a') && company_name[i] != ' ') {
                flag = 1;
            }
        }
        for(int i = 0; i < company_address.size(); i++) {
            if((company_address[i] > 'z' || company_address[i] < 'a') && company_address[i] != ' ') {
                flag = 1;
            }
        }
        if(flag == 0) {
            if(tmp2.find(company_name) != tmp2.end()) {
                for(auto i = tmp2[company_name].begin(); i != tmp2[company_name].end(); i++) {
                    if(*i == company_address)
                        flag2 = 1;
                        continue;
                }
                if(flag2 == 0) {
                    tmp2[company_name].insert(company_address);
                    map2[company_name]++;
                }
            }
            else {
                tmp2[company_name].insert(company_address);
            }
            if(map2[company_name] == 0) {
                tmp[company_name] = company_address;
            }
            // cout << company_name << ' ' << tmp[company_name] << ' ' << map[company_name] << endl;
            // string s = company_name + ' ' + tmp[company_name];
            // result.insert(s);
        }
    }
    for(auto i = tmp.begin(); i != tmp.end(); i++) {
        cout << i->first << ' ' << i->second << ' ' << map2[i->first] << endl;
    }
}

第一次编程

1.小美的外卖订单

小美正在设计美团外卖的定价信息。已知外卖定价的规则如下：

每道菜有折扣价和原价。折扣价不能超过原价。
订单有满x元减y元的优惠。当购买的菜的价格总和不小于x元时，总价格可以减y元。“减”的价格不能超过“满”的价格。
满减优惠和折扣价是互斥的，当且仅当每个菜都选择了原价才可以触发满减。
系统会自动为客户计算最低价格的方案。

在设计定价时，原价、折扣价和满减的价格都必须是正实数。如果设计的定价发生问题，则会提示数据错误。

#include <iostream>
using namespace std;

int main() {
    double food_num, highprice, lowprice, manjian, jiangjia;	//注意要用double，float精度不够高，会计算错误
    cin >> food_num;
    double sum = 0.00;
    double total = 0.00;
    double result;
    while(food_num--) {
        cin >> highprice >> lowprice;
        if(highprice < lowprice || highprice <= 0 || lowprice <= 0) {
            cout << "error" << endl;
            return 0;
        }
        sum = sum + highprice;
        total = total + lowprice;
    }
    cin >> manjian >> jiangjia;
    if(manjian < 0 || jiangjia <= 0 || manjian < jiangjia) {
        cout << "error" << endl;
        return 0;
    }
    if(sum >= manjian) {
        sum = sum - jiangjia;
    }
    result = min(sum, total);
    printf("%.2f\n", result);
    return 0;
}
// 64 位输出请用 printf("%lld")

2.小美的字符串匹配度

#include <any>
#include <iostream>
#include <linux/limits.h>
#include <utility>
using namespace std;
string myswap(string t, int i, int j) {
    string t1 = t;
    char tmp = t1[i];
    t1[i] = t1[j];
    t1[j] = tmp;
    return t1;
}
int main() {
    int n, count, result = 0;
    string s, t;
    cin >> n;
    cin >> s;
    cin >> t;
    for(int i = 0; i < t.size() - 1; i++) {
        for(int j = i + 1; j < t.size(); j++) {
            count = 0;
            string t1 = myswap(t, i, j);
            //cout << t1 << endl;
            for(int k = 0; k < n; k++) {
                if(s[k] == t1[k]) {
                count++;
                }
            }
            // cout << count << endl;
            result = max(result, count);
        }
    }
    cout << result << endl;
}

3.小美的树上染色

小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。

小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。

小美想知道，自己最多可以染红多少个节点？

#include <cmath>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
using namespace std;

int main() {
    int color = 0, quanzhi, e1, e2;
    int n;
    vector <long long int> vec;
    map<int, set <int>> edgemap;
    cin >> n; //节点数量
    int e = n - 1;
    int result = 0;
    vector <int> degree(n);
    while(n--) {
        cin >> quanzhi;
        vec.push_back(quanzhi);
    }
    // cout << vec.size();
    while(e--) {
        cin >> e1 >> e2;
        vector <long long int> edgetmp;
        edgetmp.clear();
        long long int matrix = vec[e1 - 1] * vec[e2 - 1];
        int num = sqrt(matrix);
        if(num * num == matrix) {
            edgemap[e1].insert(e2);
            edgemap[e2].insert(e1);
        }
        //cout << e1 << ' ' << e2 << endl;
    }
    auto iter = edgemap.begin();
    Goto:
    for(iter = edgemap.begin(); iter != edgemap.end(); iter++) {
        //找到度为 1 的节点
        if(iter->second.size() == 1) {
            result += 2;
            //找到度为 1 的节点的邻居n
            int neighbor = *iter->second.begin();
            //找到这个邻居n的所有邻居表的编号，找到这些编号节点对应的邻居表，把n给删掉
            for(auto it = edgemap[neighbor].begin(); it != edgemap[neighbor].end(); it++) {
                // 找到这些编号节点对应的邻居表，把n给删掉
                edgemap[*it].erase(neighbor);
                // 如果节点的邻居表为0，直接把邻居表删掉，1节点染色
                if(edgemap[*it].size() == 0) {
                    edgemap.erase(*it);
                }
            }
            //直接把n节点删掉，说明染色了
            edgemap.erase(neighbor);
            goto Goto;	//这里需要跳两层循环，不知道除了goto有没有更好的方法
        }
    }
    cout << result << endl;
}
// 64 位输出请用 printf("%lld")

4.小美的排列询问

小美拿到了一个排列。她想知道在这个排列中，x和y是否是相邻的。你能帮帮她吗？

排列是指一个长度为n的数组，其中 1 到n每个元素恰好出现一次。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, num, x, y;
    cin >> n;
    vector <int> vec;
    bool result = false;
    while(n--) {
        cin >> num;
        vec.push_back(num);
    }
    cin >> x >> y;
    for(int i = 0; i < vec.size(); i++) {
        if(vec[i] == x) {
            if(i >= 1 && i < vec.size() - 1) {
                if(vec[i - 1] == y || vec[i + 1] == y) {
                    result = true;
                }
            }
            else if(i == 0) {
                if(vec[1] == y) {
                    result = true;
                }
            }
            else if(i == vec.size() - 1) {
                if(vec[i - 1] == y) {
                    result = true;
                }
            }
        }
    }
    if(result == true) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}
// 64 位输出请用 printf("%lld")

5.小美的排列构造

小美定义一个数组a的权值计算如下：

首先将a的每一对相邻两项求和，得到一个b数组。那么b数组的最大值减最小值即为a数组的权值。

例如，若=[2,1,3]a=[2,1,3]，那么=[3,4]b=[3,4]，b数组的极差是1。因此a数组的权值为1。

现在小美希望你能构造一个长度为n*的排列，满足权值尽可能小。你能帮帮她吗？

排列是指一个长度为n的数组，其中 1 到n每个元素恰好出现一次。

#include <iostream>
using namespace std;
//实际上只需要a[i] 和a[i + 2]都差1就行了
int main() {
    int n;
    cin >> n;
    if(n % 2 == 0) {
        for(int i = 1; i <= n/2; i++) {
            cout << i << ' ' << n - i + 1 << ' ';
        }
    }
    if(n % 2 == 1) {
        for(int i = 1; i <= n/2; i++) {
            cout << i << ' ' << n - i + 1 << ' ';
        }
        cout << (n + 1) / 2 << ' ';
    }
}
// 64 位输出请用 printf("%lld")

6.小美走公路

有一个环形的公路，上面共有n站，现在给定了顺时针第i站到第i+1站之间的距离（特殊的，也给出了第n站到第 1 站的距离）。小美想沿着公路第x站走到第y站，她想知道最短的距离是多少？

#include <iostream>
#include <vector>
using namespace std;

int main() {
    long long int n, distance, src, dest;
    cin >> n;
    vector <int> vec;
    long long int sum = 0;
    long long int left = 0;
    while(n--) {
        cin >> distance;
        vec.push_back(distance);
        sum = sum + distance;
    }
    cin >> src >> dest;
    if(src > dest) {
        swap(src, dest);
    }
    for(int i = src - 1; i < dest - 1; i++) {
        left = left + vec[i];
    }
    cout << min(left, sum - left) << endl;
}
// 64 位输出请用 printf("%lld")

7.小美的好矩阵

小美定义一个矩阵是好矩阵，当且仅当该矩阵满足：

矩阵仅由’A’、’B’、’C’三种字符组成。且三种字符都出现过。
矩阵相邻的字符都不相等。

#include <iostream>
#include <vector>
using namespace std;
vector<vector <char>> matrix;
//暴躁判断所有情况
bool good(int i, int j) {
    bool flagA = false;
    bool flagB = false;
    bool flagC = false;
    if(matrix[i][j] == matrix[i + 1][j] || matrix[i][j] == matrix[i][j + 1] || 
    matrix[i + 2][j] == matrix[i + 1][j] || matrix[i + 2][j] == matrix[i + 2][j + 1] ||
    matrix[i][j + 2] == matrix[i][j + 1] || matrix[i][j + 2] == matrix[i + 1][j + 2] || 
    matrix[i + 2][j + 2] == matrix[i + 2][j + 1] || matrix[i + 2][j + 2] == matrix[i + 1][j + 2] || 
    matrix[i + 1][j + 1] == matrix[i][j + 1] || matrix[i + 1][j + 1] == matrix[i + 2][j + 1] || 
    matrix[i + 1][j + 1] == matrix[i + 1][j] || matrix[i + 1][j + 1] == matrix[i + 1][j + 2]) {
        return false;
    }
    for(int m = i; m <= i + 2; m++) {
        for(int n = j; n <= j + 2; n++) {
            if(matrix[m][n] > 'C' || matrix[m][n] < 'A') {
                return false;
            }
            if(matrix[m][n] == 'A') 
                flagA = true;
            if(matrix[m][n] == 'B')
                flagB = true;
            if(matrix[m][n] == 'C')
                flagC = true;
        }
    }
    if(flagA && flagB && flagC)
        return true;
    else
        return false;
}
int main() {
    int row, col;
    char c;
    cin >> row >> col;
    matrix.resize(row);
    for(int i = 0; i < row; i++) {
        matrix[i].resize(col);
    }
    int result = 0;
    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) {
            cin >> c; 
            matrix[i][j] = c;
        }
    }
    for(int i = 0; i < row - 2; i++) {
        for(int j = 0; j < col - 2; j++) {
            if(good(i, j)) {
                result++;
            }
        }
    }
    cout << result << endl;
}
// 64 位输出请用 printf("%lld")

8.小美的蛋糕切割

小美有一个矩形的蛋糕，共分成了n 行 m 列，共 n×m 个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。她想切一刀把蛋糕切成两部分，自己吃一部分，小团吃另一部分。

小美希望两个人吃的部分的美味度之和尽可能接近，请你输出∣s1−s2∣的最小值。（其中s1代表小美吃的美味度，s2代表小团吃的美味度）。

请务必保证，切下来的区域都是完整的，即不能把某个小正方形切成两个小区域。

#include <climits>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    #define int long long
    int num;
    int n, m, total;
    int sum = 0;
    cin >> n >> m;
    int result = INT_MAX;
    vector <vector <int>> tmp(n, vector<int>(m));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> num;
            tmp[i][j] = num;
            sum = sum + num;
        }
    }
    for(int k = 0; k < n; k++) {
        total = 0;
        for(int i = 0; i <= k; i++) {
            for(int j = 0; j < m; j++) {
                total = total + tmp[i][j];
            }
        }
        //cout << abs(sum - total - total) << endl;
        result = min(result, abs(sum - total - total));
    }
    for(int k = 0; k < m; k++) {
        total = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= k; j++) {
                total = total + tmp[i][j];
            }
        }
        //cout << abs(sum - total - total) << endl;
        result = min(result, abs(sum - total - total));
    }
    cout << result << endl;

}
// 64 位输出请用 printf("%lld")

9.小美的字符串变换

小美拿到了一个长度为n的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有x行y列，必须保证x∗y=n，即每y个字符换行，共x行）。

该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？

#include <climits>
#include <iostream>
#include <vector>
using namespace std;
bool isvalid(int i, int j, int row, int col) {
    if(i < 0 || i >= row || j < 0 || j >= col) 
        return false;
    else {
        return true;
    }
}
void dfs(vector <vector <char>> &matrix, int i, int j, char c) {
    if (!isvalid(i, j, matrix.size(), matrix[0].size())) {
        return;
    }
    if(matrix[i][j] == c) {
    matrix[i][j] = ' ';
    dfs(matrix, i + 1, j, c);
    dfs(matrix, i - 1, j, c);
    dfs(matrix, i, j + 1, c);
    dfs(matrix, i, j - 1, c);
    }
}
int liantongshu(vector <vector <char>> &matrix) {
    int result = 0;
    int m = matrix.size();
    int n = matrix[0].size();
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(matrix[i][j] != ' ') {
                dfs(matrix, i, j, matrix[i][j]);
                result++;
            }
        }
    }
    return result;
}
int main() {
    int num, k, row, col;
    int result = INT_MAX;
    char c;
    cin >> num;
    vector <char> tmp2;
    vector<vector<char>> tmp;
    for(int i = 0; i < num; i++) {
        cin >> c;
        tmp2.push_back(c);
    }
    for(row = 1; row < num; row++) {
        col = num / row;
        k = 0;
        if(row * col == num) {
            //cout << row << ' ' << col << endl;
            tmp.resize(row);
            for(int i = 0; i < row; i++) {
                tmp[i].resize(col);
            }
            for(int i = 0; i < row; i++) {
                for(int j = 0; j < col; j++) {
                    tmp[i][j] = tmp2[k++];
                }
            }
            
            result = min(result, liantongshu(tmp));
        }
    }
    cout << result << endl;
}
// 64 位输出请用 printf("%lld")

华为研发工程师编程题

1.汽水瓶

某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。

小张手上有n个空汽水瓶，她想知道自己最多可以喝到多少瓶汽水。

数据范围：输入的正整数满足 1≤n≤100

#include <iostream>
using namespace std;
 
int main() {
    int n, result;
    while(1) {
        result = 0;
        cin >> n;
        if(n == 0) {
            break;
        }
        else {
            while(n >= 2) {
                n = n - 2;
                result++;
            }
            cout << result << endl;
        }
    }
}

2.明明的随机数

明明生成了N个1到500之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。

#include <iostream>
#include <vector>
#include <set>
using namespace std;
//直接用set去重和排序
int main() {
    int n, num;
    cin >> n;
    set <int> set;
    for(int i = 0; i < n; i++) {
        cin >> num;
        set.insert(num);
    }
    for(auto iter = set.begin(); iter != set.end(); iter++) {
        cout << *iter << endl;
    }
}

3.进制转换

写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。

#include <iostream>
using namespace std;
int char2num(char c) {
    if(c == 'A')
        return 10;
    else if(c == 'B')
        return 11;
    else if(c == 'C')
        return 12;
    else if(c == 'D')
        return 13;
    else if(c == 'E')
        return 14;
    else if(c == 'F')
        return 15;
    else
        return c - '0';
}
int main() {
    string s;
    cin >> s;
    int result = 0;
    for(int i = 2; i < s.size(); i++) {
        result = result * 16;
        int num = char2num(s[i]);
        result = result + num;
    }
    cout << result << endl;
}