微软8.19笔试分享

非常佛系的做笔试做着玩的。算法菜鸡，分享一下自己朴素简单的理解，样例都过了，但是不知道是否准确，欢迎大家来讨论，（下图做纪念）

第一题

总结后的题面：在二维矩阵上有很多个点，需要多少条平行于y轴的宽度为W的带子才能将所有的点全覆盖。
感觉这整个Y数组都用不到啊，直接对X数组进行一个排序，然后进行一个去重。然后遍历整个数组，一条条带子的添加，最后就是答案了。下面是原始题面和我的简陋代码。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int solution(vector<int> &X, vector<int> &Y, int W){
    sort(X.begin(), X.end());
    int c = unique(X.begin(), X.end()) - X.begin();
    int left = X[0];
    int ans = 1;
    for(int i = 1; i < c; i++){
        if(X[i] - left > W){
            ans++;
            left = X[i];
        }
    }
    // cout << ans;
    return ans;

}

int main(){
    vector<int> a = {2,4,2,6,7,1}, b = {0,5,3,2,1,5};
    cout << solution(a,b,2);
}

第二题

总结后的题面：给你一个字符串，用这个字符串中的字符获得一个值最大的回文串。
想法，借用c++中高端的数据结构map统计所有字符出现的次数。因为map本身是有序的，所以直接到时逆序遍历map就知道了哪些大的数可以拿来造回文串。同时回文串长度如果是奇数的话，就还需要中间夹一个尽可能大的数，所以在逆序遍历的同时去记录第一个遍历到的可以作为中间数的数。这里偷懒了，字符串部分写的不是很优美。。然后记得特判一下0相关的（今天早上起床想起昨晚的判0没判好，虽然样例过了，但是应该是错了）。可能没说太清楚，但是代码应该很好理解。

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

string solution(string &s){
    int n = s.size();
    map<char, int> hash;
    for(int i = 0; i < n; i++){
        if(hash.find(s[i]) == hash.end()){
            hash[s[i]] = 1;
        } else {
            hash[s[i]]++;
        }
    }   // 这里统计每个字符出现的次数
    string ans;
    char sep = 0;    // 这个用来存夹在中间的数
    for(map<char,int>::reverse_iterator i = hash.rbegin(); i !=hash.rend(); i++){  // 逆序遍历map
        if(i->second % 2 != 0 && sep == 0) {   // 第一个出现次数不是偶数的数，应该要被作为夹在中间的数
            sep = i->first;
        }
        if(i->second % 2 == 0 && i->first!='0'){  // 回文时，不能以0开头，但是这里判错了，这样会导致整个回文串都没有0了（早上起床才想到）。
            char temp = i->second;
            while(temp != 1){
                ans += i->first;
                temp /= 2;
            }
        }
    }

    if(ans.empty() && sep == 0) return "0";  // 如果回文串啥都没有，就返回0
    string ans1 = ans;
    reverse(ans1.begin(), ans1.end());
    ans += sep + ans1;                      // 在这造回文串
    return ans;
}

int main(){
    string s = "9999788";
    cout << solution(s);

}

浅浅修改一下上面的错误

   int flag = 0;     // 添加一个标志，表示是否有遇到首个非0的作为回文开头
   for(map<char,int>::reverse_iterator i = hash.rbegin(); i !=hash.rend(); i++){
        if(i->second % 2 != 0 && sep == 0) {
            sep = i->first;
        }
        if(i->second % 2 == 0 && (i->first!='0' || flag)){  //然后在这里加判断
            flag = 1;
            char temp = i->second;
            while(temp != 1){
                ans += i->first;
                temp /= 2;
            }
        }
    }

第三题

有很多个house, 1-N每个house有一个人和一辆车，有的house间是相连的，所有人都想去0号house办公室里。一辆车从一个house到另一个house消耗1单位的燃料，一辆车最多坐5个人，问最优情况下消耗多少燃料能让所有人到0号办公室。（看个截图中的example2应该就能看懂啥意思了）
想法：菜鸡的朴素理解，不知道对不对（测试样例和自己测试了几个都是过了），每次搜索叶子节点，让叶子节点的人去对应的父节点位置，同时计算相应的燃料消耗。直到所有人都到达了0号办公室。
以example2为例画了个图，应该比较清楚。

个人感觉这个思路应该是没问题的，但是代码上就不好实现了（整个图在收缩，找到新的叶子节点的复杂度可能有点高），悲。uu们有没有什么更优秀更好实现的办法。

下面是我的简陋的代码

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
const int N = 100010;

int num[N];                     // 存每个点的人数
vector<vector<int>> G1(N);      // 存图
vector<int> vis;                // 存是否访问过该点
vector<int> indegree(N,0);      // 存动态变化的每个点的入度

int solution(vector<int> &A, vector<int> &B){
    int n = A.size();
    int maxn = 0;

    for(int i = 0 ; i < n; i++){
        G1[B[i]].push_back(A[i]);  
        G1[A[i]].push_back(B[i]);  
        indegree[B[i]]++;
        indegree[A[i]]++;
        maxn = max(max(maxn,A[i]),B[i]);          // 这个for循环造图，维护入度，顺便知道了下当前有多少个节点（maxn个）
    }

    for(int i = 0; i <= maxn; i++){               // 每个点最开始都是一个人
        num[i] = 1;
    }

    vis.resize(maxn + 1);
    int ans = 0;                                 // 燃料消耗
    int flag = 1;                                // 是否继续收缩的标志位

    while(flag){         
        flag = 0;
        for(int i = 1; i <= maxn; i++){         // 开始找叶子节点
            if(indegree[i] == 1 && !vis[i]){    // 入度为1且没有访问过
                flag = 1;                       // 能找到叶子节点，flag置1
                int target;
                for(auto j : G1[i]){            // 找到其父节点
                    if(!vis[j]){
                        target = j;
                    }
                }
                indegree[target] -= 1;        // 进行一个入度的更新，人口的移动，燃料的更新，vis的更新
                num[target] += num[i];
                ans += (num[i] - 1 )/ 5  + 1;
                vis[i] = 1;
            }
        }
    }
   return ans;
}

int main(){
    vector<int> a = {1,1,1,9,9,9,9,7,8}, b = {2,0,3,1,6,5,4,0,0};
    cout << solution(a,b);
}

评价一下，个人感觉自己的算法能力是比较弱的，可能上面的代码有很大的问题，欢迎大家给我点建议，帮助我提升一下算法能力。不过感觉这三题应该还是算不太难的（毕竟连本菜都写出来了）
最后祝大火都能拿到心仪offer.