微软8.19第三次笔试， 附题目及题解
菜狗第一次做微软笔试，本来AK了美滋滋，交了之后发现自己第二题边界忘记判掉好难过。还剩一次机会，加油。考试结束之后整理下题解。
牛客编辑器排版太差了，凑合着看吧orz
// 第一题主要思路，的对x坐标贪心 O(nlog(n))
// 应该也可以直接修改原数组，但怕出问题copy
int solution(vector<int> &X, vector<int> &Y, int W) {
vector<int> puddles = X;
sort(puddles.begin(), puddles.end());
int ans = 0, border = -1; // border为最后一次drive的右边界
for(auto x : puddles){
if(border < x){
ans ++;
border = x + W;
}
}
return ans;
}
//o(n)
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
string solution(string &S) {
vector<int> cnts(10, 0);
string lstr, ans;
//开个size = 10的数组记录下每位数出现的次数
for(auto c : S)
cnts[c - '0'] ++;
//首先构建回文串的左边lstr，构建有两个原则：
// 1.枚举所有数字，将数字出现的次数除二加到左子串
// 2.为了结果最大，从9到0枚举（0开头非法，要判掉，忘记了，😭）
for(int i = 9; i >= 1; i --){
int t = cnts[i] >> 1;
lstr += string(t, char('0' + i));
}
if(lstr.size() > 0) lstr += string(cnts[0], '0');
ans += lstr;
//如果有数字出现次数为奇数，找到一个最大的放到中间
for(int i = 9; i >= 0; i --){
if(cnts[i] % 2){
ans += char('0' + i);
break;
}
if(i == 0 && cnts[i] && !lstr.size())
ans += '0';
}
//左子串逆序加到后面。
reverse(lstr.begin(), lstr.end());
ans += lstr;
return ans;
} 第三题.拓扑排序，dfs也可以做. p[i]记录每个点的乘客数目，初值为1；
d[N] 记录每个点的度，当度减为1时（意味着，所有应当经过该点的乘客已经到达该点）， 将所有人送到下个点，计算代价。
1.目的地的度数减1
2.费用为乘客数/5 向上取整，
为了加速，用数组模拟队列。
#include<iostream>
#include<cstring>
#include<algorithm>
const int N = 1e5 + 10, M = N * 2;
int h[N], e[M], ne[M], idx = 0; //邻接表辅助数组
int d[N], q[M], p[N]; //q为拓扑排序的队列
void add(int a, int b) //邻接表添加边
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int solution(vector<int> &A, vector<int> &B) {
int n = A.size(), fee = 0;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i ++) p[i] = 1; //init（）
for(int i = 0; i < n; i ++)
add(A[i], B[i]), add(B[i], A[i]), d[A[i]] ++, d[B[i]] ++; //加边，同时统计每个点的度数；
int hh = 0, tt = -1; //队列下标
for (int i = 1; i <= n; i ++ ) //遍历所有点，将所有叶节点入队
if (d[i] == 1){
q[ ++ tt] = i;
}
while (hh <= tt)
{
int t = q[hh ++ ];
if(t == 0) continue; //判掉0号点
fee += (p[t] + 4) / 5;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
p[j] += p[t];
if (-- d[j] == 1)
q[ ++ tt] = j;
}
}
return fee;
} 
