22年微软秋招笔试

微软笔试一共四轮（取最高成绩），攒人品加总结一下前三轮的笔试内容，第四轮结束后会再做总结！

微软笔试共3道题，其中第一题是较为简单的，一般用贪心来做，第二题较难，第三题复杂但难度适中。

属于开卷考试，因此可以查一些资料来辅助做题，但是题目基本上也很难找到原型，不如自己去思考后做答，要相信自己的实力

第一轮：220806

可能是很久没参加笔试的原因，稍稍有些紧张了，只AC了第一题，后面第二道题思路受限了，网上查一下后发现有人用逆序数的方法来做，虽然能做，但是思路复杂了，没必要，不如双指针来的清楚。第二题卡了太久导致第三题没时间做了，本来是已经有了思路，奈何实现起来并没有非常熟练，导致第三题也没有做完，下次注意分配好时间，难易程度和题号关系不大。

填坑修路问题（贪心）

题目描述：给定一条路S和材料B份，已知路上有很多坑，用'x'表示，平路用'.'表示，我们的任务就是填坑，连续的n个坑所需要的材料是n+1份，共有B份材料，问最多可填多少坑？
样例：S = "...xxx..x....xxx", B = 7，此时可填5个坑
解题思路：因为每填连续的n个坑都需要额外的1份材料，因此贪心策略就是尽可能先填长坑，再填短坑
- 技巧：用优先队列存储坑的长度
- 复杂度：时间\(O(N)\)，空间\(O( 1 )\).

C++代码：

int solution(string &S, int B) 
{
    // write your code in C++ (C++14 (g++ 6.2.0))
    if(B <= 1)
    {
        return 0;
    }    
    // cout << S << B << endl;
    priority_queue<int> pq; // store the needs of each consecutive potholes
    int sum = 0;
    for(int i=0; i<S.size(); ++i)
    {
        int sep = 0;
        while(S[i]=='x')
        {
            sep++;
            sum++;
            i++;
        }
        if(sep > 0)
        {
            // cout << sep + 1;
            pq.push(sep+1);
        }
    }
    int n = pq.size();
    int res = 0;
    bool flag = false;
    for(int i=0; i<n; ++i)
    {
        if(B<=1) return res;
        int sep = pq.top();
        if(B>=sep) 
        {
            B -= sep;
            res += sep-1;
        }
        else
        {
            res += B-1;
            B = 0;
        }
        pq.pop();
    }
    return res;
}

红白球互换问题（双指针）

题目描述：给定字符串S，其中包括红球R和白球W，一次可以两个交换相邻球的位置，求使得红球都靠在一起的最小交换次数
输入样例：S = "WWRWRWRRWW"，输出3，因为第3和第4个W向左移动3次可以成为"WWWWRRRRWW"
解题思路：双指针从两端向中间遍历，记录当前位置左侧和右侧出现的R数量，来决定下一步走哪一个指针以及遇到W时该加多少（将当前W换到外侧所需要的交换次数=min(左侧R数量，右侧R数量)）
- 技巧：当双指针相遇时并不结束，而是当l>r时才结束
- 复杂度：时间复杂度为\(O(N)\), 空间复杂度也是\(O(N)\)，\(N\)为字符串长度

C++代码：

int solution1(string &S)
{
	int l=0, r=S.size()-1;
	int lR=0, rR=0; // 记录l左边位置红球的数量，记录r右边红球的数量 
	int res=0;
	while(l<=r)
	{
//		cout << "l:" << l << " r:" << r << " lR:" << lR << " rR:" << rR << " res:"<< res << endl;
		if(lR<=rR)
		{
			if(S[l]=='W')
			{
				res += lR;
			}
			if(S[l]=='R')
			{
				lR++;
			}
			l++;
 		} 
 		else
 		{
 			if(S[r]=='W')
 			{
 				res += rR;
// 				cout << "true";
	 		}
	 		if(S[r]=='R')
	 		{
	 			rR++; 
		 	}
		 	r--; 
		}
	}
	return res;
} 

int main()
{
	string S = "WWRWRWRRWW";
	cout << S << " " << solution1(S);
	system("pause");
	return 0;
}

医生排班问题（拓扑排序）

题目描述：看病问题，每个病人i有A[i]B[i]两个预约时段，S代表预约时间，判断每个人是不是都能预约上。
解题思路：我的做法就是先把每个时间点的人的编号存到对应时间的set中，然后找到所有只有一个人的时间点，然后指定这个人在这个时间就医（在这个人就医时间对应的set中把他删掉），然后while循环，直至不存在这样的人。此时剩下的时间点中，如果每个时间点都只有两人或没有人就医，则可以达成题意，否则不行。
- 方法类似于求拓扑序列：即在有向图中寻找入度为0的点，删除该点与他所连出去的边，直至无法不存在入度为0的点；此时如果删除的顶点数等于图的顶点数，则图无环，删除的序列为拓扑序列（也叫拓扑排序）；否则为有环图。
- 实现技巧：用桶的思想，每个时间点一个桶，桶用unordered_set来表示，方便后续删除操作。vector<unordered_set<int>> cnt(S, {-1});set的初始化为{-1}，这里还真不会写初始化为{}的长度为S的vector。实现起来稍微有些混乱，可以纸上模拟一下。
- 复杂度分析：时间复杂度\(min(O(N), O(S))\)，空间复杂度\(O(S+N)\).

C++实现：

#include<bits/stdc++.h>
using namespace std; 

bool solution(vector<int> &A, vector<int> &B, int S) 
{
    int n = A.size();
    if(n > S) return false;
    
    vector<unordered_set<int>> cnt(S, {-1});
    // cout << cnt.size();
    for(int i=0; i<n; ++i)
    {
        if(A[i] >= S || B[i] >= S): return false;
        cnt[A[i]].insert(i);
        cnt[B[i]].insert(i);
    }
    

    while(true)
    {
        bool flag = false;
        for(int i=0; i<S; ++i) // traverse the available time slot
        {
            if(cnt[i].size()==2) // remove the unclashed person
            {
            	int num = 0;
            	flag = true;
            	for(auto it=cnt[i].begin(); it!=cnt[i].end(); ++it)
            	{
            		if(*it != -1)
            		{
            			num = *it;
            			break;
					}
				}
				cout << num << "$$$" << endl;
				cnt[A[num]].erase(num);
				cnt[B[num]].erase(num);
            }
        }
        if(!flag) break;
    }
//    for(int i=0; i<S; ++i)
//    {
//    	cout << i << ": ";
//    	for(auto it = cnt[i].begin(); it!=cnt[i].end(); ++it)
//    	{
//    		cout << *it << ", ";
//		}
//		cout << endl;
//	}
    
    bool res = true;
    for(int i=0; i<S; ++i)
    {
        if(cnt[i].size()>3) // remove the unclashed person
        {
            res = false;
        }
    }
    return res;
}

int main()
{
	vector<int> A = {1, 2, 3, 4};
	vector<int> B = {2, 3, 1, 1};
	cout << solution(A, B, 5);
	return 0; 
}

第二轮：220813

第二轮笔试做题时感觉非常顺，第一题不到10分钟就搞定了，整套题可能1个小时多一点就做完了且AC了。但是！第二题读题读错了，太亏了！"choose a pair of fractions that sum up to 1"，也只能怪自己审题不清，写了一个递归来找组合数求和为1的数量，之后要多做些英文题，减少读题的失误

工厂排污减半（贪心）

题目描述：输入为一个长度为N的字符数组，每个数代表着1个工厂的排污数，已知1个filter可以将污水减半，两个filter就减为原来的1/4，问至少需要多少个filter才能将所有工厂污水减半
题目样例：A=[5,9,18,1]，全部污水为5+9+18+1=33，需要3个filters将污水减为14.75<16.5
做题思路：
- 技巧：用优先队列来模拟一个最大堆，使得每次都在污水排除最多的工厂加filter，这样每一个filter都是当前的最优放置位置。处理完后的工厂记得减半后放回队列中。
- 复杂度：优先队列的插入和删除都是\(O(logN)\)的复杂度，共需要插入N个数据，因此时间复杂度为\(O(logN)\)；空间复杂度为\(O(N)\)

C++代码：

#include<bits/stdc++.h>
using namespace std;

int solution(vector<int> &A) 
{
    // write your code in C++ (C++14 (g++ 6.2.0))
    int n = A.size();
    priority_queue<double> pq; // 注意这里用double类型来存储
    double sum = 0;
    for(int i=0; i<n; ++i)
    {
        sum += double(A[i]);
        pq.push(double(A[i]));
    }
    double cur = sum;
    int res = 0;
    while(sum/2 < cur)
    {
        res++;
        double m = pq.top();
        m /= 2;
        cur -= m;
        // cout << m << " " << cur << "; ";
        pq.pop();
        pq.push(m);
    }
    return res;
}

小数求和为1（最小公约数gbd+map）

题目描述：输入为两个等长的字符数组X和Y，其中X存储分子，Y存储分母。寻找所有两个可以求和为1的组合数
解题思路：看了牛客网的面经，直接暴力搜索的话时间复杂度是\(O(N^2)\)，这里N为1e5，复杂度会超过十亿，应该会超时，因此尝试用hashmap来减少检索的时间，但因为还涉及到假分数，因此需要先找到最小公约数进行约分后存入hashmap。求最小公约数的时间复杂度为\(O(Nlog(M))\)，这里\(log(M)=10\)，因此可以理解为\(O(N)\)
- 解题技巧：用gcd算法（辗转相除法）求最小公约数。用map([up, down], n)（不能用unordered_map，不支持pair）来存储该分数出现的次数。遍历时因为数的大小无序，因此需要用set（不能用unordered_set，不支持pair）存储哪个分数被用掉过
- 复杂度分析：时间复杂度\(O(Nlog(M)+O(N))\)，空间复杂度\(O(N)\)

代码：

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int gbd(int a, int b) // 辗转相除法计算最小公约数
{
	if(b!=0)
	{
		return gbd(b, a%b);
	}
	return a;
}

int solution(vector<int> & X, vector<int> & Y)
{
	int MOD = 1e9+7;
	map<pair<int, int>, int> bin; // 存储分子分母到其出现次数的映射，这里不能用unordered_map 
	int n = X.size();
	for(int i=0; i<n; ++i)
	{
		int divisor = gbd(X[i], Y[i]);
		pair<int, int> tmp(X[i]/divisor, Y[i]/divisor);
		if(bin.find(tmp) != bin.end())
		{
			bin[tmp] ++;
		}
		else
		{
			bin[tmp] = 1;
		}
	}
	
	set<pair<int, int>> used; // 存储目前已经配对过的分子分母，也是不能用unordered_set 
	int res = 0;
	for(auto it=bin.begin(); it!=bin.end(); ++it)
	{
		int up = it->first.first;
		int down = it->first.second;
		int num = it->second;
		
		cout << up <<" / " << down << " " << num << endl;
		// 当已经配对的值出现后，直接跳过 
		if(used.find(it->first) != used.end()) continue;
		// 当自己＋自己等于1时（其实就是1/2时），可以组成对的数量为C(2,num) 
		if(up == down - up)
		{
			res += (num*(num-1)/2) % MOD;
 		} 
 		else // 寻找另一半 
 		{
 			pair<int, int> target(down-up, down);
			if(bin.find(target) != bin.end()) // 当另一半存在时，可以组成对的数量是num1*num2 
			{
//				cout << "$ " << bin.find(target)->second << " " << num << endl;
				res += (bin.find(target)->second * num) % MOD;
				used.emplace(target);
		 	} 
		}
	}
	return res; 
}

int main()
{
	vector<int> X = {1,1,2};// {1,2,3,1,2,12,8,4};
	vector<int> Y = {3,2,3};// {5,10,15,2,4,15,10,5};
	int res = solution(X, Y); 
	cout << res << endl;
	return 0;
}

看病费用最小（双指针）

题目描述：给定N个看病日的费用和病人需要去看病的次数X，以及每次的间隔Y，求看病的最小费用
解题思路：可以遍历数组Y遍，遍历的起始点分别为0...Y-1，每次遍历的序列的下标为x, x+Y, x+2Y, ...,对改子序列用双指针记录左右端点和当前sum值，并同时向右移动指针来计算新的sum值
- 技巧：双指针遍历时只用考虑
- 复杂度分析：时间复杂度上，因为每个值只用遍历一遍，因此时间复杂度为\(O(N)\)，空间复杂度为\(O(1)\)

C++代码：

#include<bits/stdc++.h>
using namespace std;
int solution(vector<int> &A, int X, int Y) 
{
    long int res = 0xffffffffff;
    // cout << res << "# ";
    int flag = 0;
    for(int i=0; i<Y; ++i) // traverse first starting points
    {
        int left = i, right = i;
        int sum = 0;
        int count = 0;
        while(right < n)
        {
            sum += A[right];
            right += Y;
            count++;
            if(count == X)
            {
                res = min(res, sum);
                sum -= A[left];
                left += Y;
                count--;
            }
        } 
    }
    return int(res);
}

第三轮：220819

这次笔试第三题读题加想思路耗时比较久，还是对数据结构不太熟练导致的，搭建数据结构，再写算法整个耗时了1小时，最后没时间debug了，哎，攒人品，加油！！

填坑修路问题2（贪心）

题目描述：给定一个矩阵路面，X，Y数组分别存储坑的x，y坐标，现有一个宽度为W的推土机，推土机一次会推过整个y轴宽度为W的区域，问至少多少次可以把路修平
解题策略：贪心法，只用考虑X轴，因此先把X从小到到大排序，然后遍历X数组，推土机每次从x位置出发，宽度x+W区域都推平，下次从x+W+1的位置找新的坑
- 编程技巧：sort(X.begin(), X.end());用自带的排序算法
- 复杂度分析：排序时间复杂度为\(O(NlogN)\)，后续操作为\(O(N)\)，空间复杂度为\(O(1)\)

C++代码：

// #include <algorithm>
#include<bits/stdc++.h>
using namespace std;
int solution(vector<int> &X, vector<int> &Y, int W) 
{
    // write your code in C++ (C++14 (g++ 6.2.0))
    sort(X.begin(), X.end());
    int res = 0, l = 0, n = X.size();

    if(W >= X[n-1]-X[0]) return 1; // pruning

    for(int i=0; i<X.size(); )
    {
        l = X[i];
        res++;
        // cout << X[i] << ", ";
        while(i < n && l+W >= X[i])
        {
            i++;
        }
    }
    return res;
}

生成最大回文数（贪心）

题目描述：输入字符串S，S仅包含数字0-9，返回可以用这些数组组成的最大回文数
样例：输入S=999554433221100008877765，输出987543210090012345789
解题思路：先将数字出现的次数存到0-9的桶里，从9-0遍历，如果该字符存在的数量>=2，则将其模2的值作为当前数字的数量加入到新的字符串中，并删除所用到的字符数。遍历完可能组成回文的字符后，再从9-0遍历一遍，找到当前剩余的最大字符作为中间字符。整体是贪心策略，注意corner case，比如0不能放到首个。
- 编程技巧：获取反转字符串
  1
  2
  3
  #include<algorithm> // reverse函数需要用
  string right = res;
  reverse(right.begin(), right.end());
- 复杂度分析：时间空间复杂度都是\(O(N)\)

C++代码：

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;

string solution(string &S) 
{
    // write your code in C++ (C++14 (g++ 6.2.0))
    string res = "";
    bool flag = false; // become true when the leading number is not zero
    
    vector<int> num(10, 0);  // bucket
    // add number to the bucket 'num'
    for(int i=0; i<S.size(); ++i)
    {
        int tmp = stoi(S.substr(i,1));
        // cout << tmp << ", ";
        num[tmp]++;
    }
    for(int i=num.size()-1; i>=0; --i)
    {
        int cnt = num[i]/2;
        int rmd = num[i]%2;
        if(cnt != 0 && i > 0) // for number 9-1 whose amount >= 2
        {
            flag = true;
            while(cnt--)
            {
                res += to_string(i); 
                // cout << res << "; ";
            }
            num[i] = rmd;
        }
        if(flag && i == 0 && cnt != 0) // for number 0 which is not the leading and the comunt >= 2
        {
            while(cnt--)
            {
                res += to_string(i);
                // cout << res << "; ";
            }
            num[i] = rmd;
        }  
    }
    // get the middle char
    string mid = "";
    for(int i=num.size()-1; i>=0; --i)
    {
        if(num[i]!=0)
        {
            mid += to_string(i);
            break;
        }
    }
    if(!flag) // when the final result is a single number;
    {
        return mid;
    }
    // reverse the left part
    string right = res;
    reverse(right.begin(), right.end());
    // form the final result
    res += mid;
    res += right;
    return res;
}

int main()
{
	string S = "999554433221100008877765";
	S = "0000000000";
	S = "1566666661555";
	S = "00900008999999999123456789";
	S = "0123456789012";
	string res = solution(S);
	cout << res <<endl;
	system("pause");
	return 0; 
}

拼车最少烧油方案（DFS）

题目描述：给定N叉树的边的集合，其中根节点为公司，每个子节点住着一个员工，问这些员工去公司最少需要耗费多少油。其中节点到节点之间1辆车是1升油，最多5个人坐一辆车
解题策略：根据边的输入，用二维的vector数组建立一个邻接表，用来存储节点i到节点j有边相连。通过dfs算法求解，贪心策略就是住的越远的人先开车到父节点，然后父节点集齐人员后再出发。即需要计算当前节点所有子节点个数
- 复杂度分析：递归遍历树的每一个节点，因此时间复杂度为\(O(V+E)\)其中V是结点数，E是边数

C++代码：

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> graph;
int res = 0;

int traverse(int cur, int root)
{
//    cout << cur << ", ";
    if(graph[cur].size() == 1 || (graph[cur].size() == 2 && graph[cur][1] == root)) return 1;
    
    int num = 1;
    for(int i=1; i<graph[cur].size(); ++i)
    {
        if(graph[cur][i] != root)
        {
            int tmp = traverse(graph[cur][i], cur);
            num += tmp;
            res += (tmp+4)/5;
        }
    }
    return num;
}

int solution(vector<int> &A, vector<int> &B) 
{
    // write your code in C++ (C++14 (g++ 6.2.0))
    int n = A.size();
    graph.resize(n+1, vector<int>(1, -1));
    for(int i=0; i<n; ++i)
    {
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }
//	for(int i=0; i<=n; ++i)
//	{
//	 for(int j=1; j<graph[i].size(); ++j)
//	 {
//	     cout << graph[i][j] << ", ";
//	 }
//	 cout << endl;
//	}
    traverse(0, -1);
    return res;
}

int main()
{
//	vector<int> A = {0, 1, 1}, B = {1, 2, 3};
	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); 
	return 0;
}

第四轮：220826

第四次笔试，做对了2.5/3吧，第一题之前确实没见过，想了大概有1小时左右，也没想到最优的思路，主要可能是状态相同的位置所夹的区间就是偶串这个点没想到，前缀和的位压缩存储之前也用的比较少，还是一道很好的题目。以后的笔试多多加油吧，总结还是有好处的，帮助梳理

最长连续偶数子串（前缀和+位运算存储）

题目描述：找到字符串s最长连续子串，满足子串中每个字母出现的次数都为偶数
解题思路：
- 思路一：暴力搜索，遍历所有的起点和重点位置，判断当前字符串是否为偶串，用桶去记录从起点开始到当前终点的字符出现次数（这里可以用位运算来代替），同时用cnt来存储当前奇数字符的个数。当奇数字符数为0时，表示当前为偶串，记录下长度（思路二主要是这里更巧妙了）
  - 复杂度分析：时间复杂度为\(O(N^2)\)，空间为\(O( 1 )\).
- 思路二：前缀和+位存储；从0到当前位置i组成的字符串，和从0开始到位置j组成的字符串，如果包含字符的奇偶性相同时（位存储时就是int数字相等时），则表明从i到j是一个偶串。因为共26个字母，因此可以用int的1个bit来存储一个字母出现的奇偶次数，前缀和体现在我们要记录从0到i这个字符串的奇偶状态，而奇偶状态用int来存储。
  - 实现技巧：用位存储字母出现的奇偶状态；用哈希表存储状态state第一次出现的位置i，方便检索
  - 复杂度分析：时间复杂度\(O(N)\)，空间\(O(N)\)

C++代码（思路一）：

#include<bits/stdc++.h>
using namespace std;
int solution(string &S) 
{
    int res = 0;
    for(int l=0; l<S.size(); ++l)
    {
        vector<int> bin(26, 0);
        int cnt = 0;
        for(int r=l; r<S.size(); ++r)
        {
            int index = S[r] - 'a';
            bin[index] ++;
            if((bin[index] > 0) && (bin[index]%2 == 0)) cnt--;
            else cnt++;
            if(cnt == 0) 
            {
                res = max(res, r-l+1);
            }
        }
    }
    return res;
}

C++代码（思路二）：

#include<bits/stdc++.h>
using namespace std;

int solution(string& s) 
{
	int res = 0;
    unordered_map<int, int> hash;
    int num = 0;
    hash[num] = -1;
	for(int i=0; i<s.size(); ++i)
	{
        int cur = 1 << (s[i]-'a');
        num = num ^ cur;
		if(hash.find(num) != hash.end())
		{
			res = max(res, i - hash[num]);
		}
		else
		{
			hash[num] = i;
		} 
    }
    return res;
}

int main()
{
	string s = "aaabcdabcdxyxyzx";
	cout << s << endl;
	cout << solution(s) << endl;
	return 0;
}

差值可以整除M的最大子集（取模）

题目描述：给定数组A，找到子数组，使得子数组中任意两数的差值可以整除M。数组中可以存在负值
解题思路：其实就是当前数模上M的值，取模的值相同，则就在同一个子集中。这里需要注意负数的取模
- 编程技巧：负数取模操作(A[i]%M)+M)%M
- 复杂度分析：时间复杂度\(O(N)\)，空间复杂度\(O(N)\)

C++代码：

#include<bits/stdc++.h>
using namespace std;
int solution(vector<int> &A, int M) 
{
    int n = A.size();
    if(M==1) return n;
    vector<int> bin(M, 0);
    for(int i=0; i<n; ++i)
    {
        if(A[i]>=0)
        {
            bin[A[i]%M]++;
        }
        else
        {
            bin[((A[i]%M)+M)%M]++;
        }
    }
    int res = 0;
    for(int i=0; i<M; ++i)
    {
        res = max(res, bin[i]);
    }
    return res;
}

未出现的最小值（贪心-多次遍历）

题目描述：给定两个等长数组A和B，对于每个位置i，只取AB中的一个数放入C[i]，求C数组中未出现数字的最小值，取值区间是[1,100000]
解题思路：先遍历一遍AB，把相同的值放入set中；从新遍历不相同的AB，如果A或B的值存在在set中，那么直接插入，如果不存在，则挑出大的放到set中，最后遍历1-100000，找到第一个不存在在set中的数即可
- 复杂度分析：时间复杂度为\(O(N)\)，空间复杂度为\(O(N)\)

C++代码：

#include<bits/stdc++.h>
using namespace std;

int solution(vector<int> &A, vector<int> &B) 
{
    int n = A.size();
    vector<bool> flag(n, false);
    unordered_set<int> S;
    for(int i=0; i<n; ++i)
    {
        if(A[i] == B[i])
        {
            flag[i] = true;
            S.emplace(A[i]);
        }
    }
    for(int i=0; i<n; ++i)
    {
        if(!flag[i])
        {
            if(S.find(A[i]) != S.end())
            {
                continue;
            }
            else if(S.find(B[i]) != S.end())
            {
                continue;
            }
            else
            {
                S.emplace(max(A[i], B[i]));
            }
        }   
    }
    int res = 0;
    for(int i=1; i<=1e6; ++i)
    {
        if(S.find(i) == S.end())
        {
            res = i;
            break;
        }
    }
    return res;
}