美團點評2016研發工程師程式設計題(二)題解

美團點評2016研發工程師程式設計題(二)

【1.字元編碼】

【解題思路】

哈夫曼編碼，用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.奇數位丢棄】

【解題思路】

考慮這是一個樹形結構，即

考慮第一層，即最後剩下的數字的編号一定為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.二維數組列印】

【解題思路】

觀察一下規律，定義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.股票交易日】

【解題思路】

動态規劃，考慮這題的本質是如何讓手裡的錢變的最多，那麼假設一開始擁有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;
    }
};