微软笔试

贴一下题目吧，从别的帖子捞过来的😂😂😂 微软笔试是两点结束吗？那就等会再发吧 上周的笔试写完第一题后就点了submit，然后就结束了，哭死😂😂😂。希望这次能过吧，贴一下代码，供大家参考第二题的时间复杂度不知道顶不顶得住，其他两题感觉应该还ok   // 第一题：将A中的某个数字减少一半，最少需要多少次后，数组的和小于等于原来数组和的一半 // 思路：贪心，大根堆 public int solution(int[] A) { // write your code in Java 8 (Java SE 8) PriorityQueue<Double> heap = new ...

今日份（8-19）的微软笔试：第一题：直接求解+二分优化。数据量N是10^5，数据大小M是10^9，从左往右直接求解，再使用二分优化一下，复杂度O(lg M)。当然，最大的问题在于无法证明这种做法是最优解，但是快就完事了！第二题：贪心+堆优化。统计所有数出现的次数，对于任意两个数，当他们的数量都大于2、或者值都为1时，值更大的优先级更高；否则数量大于2的优先级更高。每次选择当前优先级最高的数，用于从两端向内组成回文，直至优先级最高的数无法再用于组成回文。第三题：DFS。每次 DFS 返回一个 cost 和人数，当前点的 cost 、人数分别为由深层DFS返回的 cost 之和、人数之和，在当前非0的点返回前再对 cost 加上 ceil(当前人数/5)。

三题感觉都不难，比上次简单。。。   第一题：给一个数，从中移除一个‘5’，求剩下的数的最大值。暴力即可。   import java.util.*; public class Test01 {     public static void main(String[] args) {         Test01 s = new Test01();         int N = -54325;         int res = s.solution(N);         System.out.println(res);     }     public int solution(int ...

滴滴~有今天也是参加微软笔试的同学吗~

8.20晚上微软的三道题第一题：给定一个数组列表，我们从中抽取出两个数字，希望这两个数字的和最大，这两个数字的条件就是每个位上的数字相加能够相等。例如[17,71,24,42]中有两个一对，[17,71],[24,42],但是最大的是17+71=88第二题：给定M个1*1和N个2*2的瓦片，组成最大的正方形长度。可以不用完把所有的瓦片。第三题：有一个m*n的小镇，镇上有很多户人家，我们想在这个镇上开店，店到每户人家的距离小于等于K(距离就是店到每户人家的格子数，即使格子经过每户人家)，求出在这个镇上开店的候选地址个数

1.      时间:O(n), 空间：O(min(2^26, n)) = O(n);   思路：      题意是找到字符串s最长子串，满足子串中每个字母出现的次数都为偶数   借用类似前缀和的思想，遍历一边就好了。想o(n)的做法卡了一会，有点慌，   我们考虑小写字母总共只有为26个，所以用一个维护个sum的低0 ～ 25位来表示字符串s[0] ~ s[i]中所有小写字母的奇偶性状态.（sum 二进制第 k 位为1时代表前i个字符中char(’a’ + k)出现次数为奇数）   哈希表m记录每个状态第1次出现时下标L，当遍历到R时如果这个状态再次出现，那么R - L就是一个满足条件的子串...

1.xxxx.....xx.....一条路最多能填多少坑，X代表坑，.代表没有坑。 import java.util.*; class Solution {     public int solution(String S, int B) {         // write your code in Java 11 (Java SE 11)         int N = S.length();         List<Integer> count = new ArrayList<>();         int req = 0;         for (int ...

哈喽！今天微软笔试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());          ...

Task1  题目     思路对撞指针。用一个数组来统计字符串中每个字母出现的次数，如果数组中每个元素出现的次数都为偶数，则代表该字符串符合题目要求。左右指针对撞，如果当前l和r所指的字符的出现次数都为偶数，则判断当前子串是否符合要求，符合则返回当前字符串长度；不符合，左右指针都向中间靠拢一步，对应的字符出现次数数组中的值减一；如果l和r所指字符出现次数都为奇数，则判断是否所指字符是否相等，如果相等则移动任意一个指针，对应次数减一；如果不相等，左右都移动然后次数减一 code  //对撞指针 public int task1(String S) { int l = 0, r = S.leng...

题目就不发了吧，外企 想要的私我  #include <algorithm> int solution(vector<int> &X, vector<int> &Y, int W) { int n=X.size(); sort(X.begin(),X.end()); int ans=0, e=-1, i=0; while(i<n){ e=X[i]+W; while(i<n&&X[i]<=e) i++; ans++; } return ans; } #include <algorithm> #inc...

有参加的同学举个抓抓，java选手，大家都加油！！！

#微软# #微软笔试# 上周五参加了微软校招笔试，今天收到邮件“你本周的笔试时间已被调整”，里面带的rpmsg邮件看不到，请问有人知道这是什么意思？这周五不还有一场吗？

题目：   1. X-Y坐标轴上有多个凹槽需要填平，给出一个X数组，X[i]记录第i个凹槽的x坐标；给出一个Y数组，Y[i]记录第i个凹槽的y坐标。填平使用的仪器每次从X轴的某个点向y轴正方向出发，宽度为W，即如果从(x, 0)出发，那么可以覆盖填平范围从X = x到X = x + W（两边都是闭区间）两条线内所有凹槽。问最少用多少次可以填平所有凹槽。   2. 给出一个字符串，只包含0-9的数字，要求使用这些数字构成最大的回文数字（字符串），如给出"39878"，则应返回"898"；如给出"00900"，则应返回"9&qu...

test example过了，不确定有没有别的错。   1. 去掉一个5后得到的最大数字。我看题目说注重正确性，不在意性能，那是直接暴力法？   class Solution {     public int solution(int N) {         // write your code in Java 8 (Java SE 8)         String str = String.valueOf(N);         List<Integer> list = new ArrayList<>();         for (int i = 0; i &l...