欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

美团点评2016研发工程师编程题(二)题解

程序员文章站 2022-06-07 13:05:59
...

美团点评2016研发工程师编程题(二)

【1.字符编码】

美团点评2016研发工程师编程题(二)题解

【解题思路】
哈夫曼编码,用map记录每个字母的出现次数,然后用优先队列进行模拟即可

【AC代码】

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    while(cin >> s) {
        priority_queue<int, vector<int>, greater<int> > que;
        map<char, int> mp;
        int l = s.length();
        for(int i = 0; i < l; ++i) {
            ++mp[s[i]];
        }
        for(auto& it : mp) {
            que.push(it.second);
        }
        int sum = 0;
        while(que.size() > 1) {
            int u = que.top();
            que.pop();
            int U = que.top();
            que.pop();
            int temp = u + U;
            que.push(temp);
            sum += temp;
        }
        printf("%d\n", sum);
    }
    return 0;
}

【2.奇数位丢弃】

美团点评2016研发工程师编程题(二)题解

【解题思路】
考虑这是一个树形结构,即
美团点评2016研发工程师编程题(二)题解

考虑第一层,即最后剩下的数字的编号一定为1,那么第二层该数字为2,…,第i层即为2i,那么易得答案即为2[log2(n)] - 1,因为原序列从0开始

【AC代码】

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    while(~scanf("%d", &n)) {
        int t = 1;
        while(t < n) {
            t <<= 1;
        }
        t >>= 1;
        printf("%d\n", t - 1);
    }
    return 0;
}

【3.二维数组打印】

美团点评2016研发工程师编程题(二)题解

【解题思路】
观察一下规律,定义row和col表示当前起始点的坐标,首先让col–,然后让row++

【AC代码】

class Printer {
public:
    vector<int> arrayPrint(vector<vector<int> > arr, int n) {
        vector<int> ans;
        int row = 0, col = n - 1;
        while(row < n) {
            int i = row, j = col;
            while(i < n && j < n) {
                ans.push_back(arr[i][j]);
                ++i, ++j;
            }
            if(col == 0) ++row;
            if(col > 0) --col;
        }
        return ans;
    }
};

【4.股票交易日】

美团点评2016研发工程师编程题(二)题解

【解题思路】
动态规划,考虑这题的本质是如何让手里的钱变的最多,那么假设一开始拥有0元钱

对于第一次买,会让自己手里的钱减少prices[i],这时拥有的钱为firstbuy = 0 - prices[i]

第一次卖,会让自己的钱增加prices[i],此时钱数为firstsale = firstbuy + prices[i]

同样第二次买会让自己手里的钱减少prices[i],secondbuy = firstsale - prices[i]

第二次卖会让自己的钱增加prices[i],secondsale = secondbuy + price[i]

每一次买和卖都取最大值,就可以保证结果的正确性,返回secondsale即可

【AC代码】

class Stock {
public:
    int maxProfit(vector<int> prices, int n) {
        int firstbuy = -0x3f3f3f3f, firstsale = -0x3f3f3f3f, secondbuy = -0x3f3f3f3f, secondsale = -0x3f3f3f3f;
        for(int i = 0; i < n; ++i) {
            firstbuy = max(firstbuy, -prices[i]);  //第一次买
            firstsale = max(firstsale, firstbuy + prices[i]);  //第一次卖
            secondbuy = max(secondbuy, firstsale - prices[i]);  //第二次买
            secondsale = max(secondsale, secondbuy + prices[i]);  //第二次卖
        }
        return secondsale;
    }
};
相关标签: 牛客