美团点评2016研发工程师编程题(二)题解
程序员文章站
2022-06-07 13:05:59
...
【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;
}
};