美团点评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层即为2ⁱ，那么易得答案即为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;}
};