微软笔试

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

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

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

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());       ...

非常佛系的做笔试做着玩的。算法菜鸡，分享一下自己朴素简单的理解，样例都过了，但是不知道是否准确，欢迎大家来讨论，（下图做纪念） 第一题 总结后的题面：在二维矩阵上有很多个点，需要多少条平行于y轴的宽度为W的带子才能将所有的点全覆盖。感觉这整个Y数组都用不到啊，直接对X数组进行一个排序，然后进行一个去重。然后遍历整个数组，一条条带子的添加，最后就是答案了。下面是原始题面和我的简陋代码。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int sol...

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

有参加的同学举个抓抓，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&...

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 &...

感觉不是很难，等晚上笔试结束再贴一下自己的代码~ 第一题 题目： 一个二维坐标系，给了两个数组X[],Y[]，(X[i],Y[i]）代表一个坑，现在有填坑的机器，宽度为W。每次可以沿着平行Y轴的方向修坑。问最少几次可以修完所有的坑。 思路： 类似力扣戳气球，贪心算法，每个坑都一定要修的，每次都选当前剩余的坑中第一个坑作为开始的起点x，这样以x+W以内的坑都能被修好，下次只要考虑X+W以外的坑的情况。 代码： import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer; import j...

我觉得这次比上次简单一点🤣 - 微软的笔试不分啥前后端的，题目都一样，这里主要说明用JS做的题解；（多余说一句，从题干上来说，微软的题和现实生活联系得最紧密） - 题目有老哥贴出来了https://www.nowcoder.com/discuss/1013487 编程题 1. 防治污染 纯暴力解法，每次把最大值过滤下就行了，但是我处理得是每次用Math.max(...arr)去找最大值； 有人说用最大堆，但是JS没有可用的API呀，得自己手写，这样会来不及吧 function solution(A...

早上微软笔试 第一题 优先队列 第二题 两数之和 第三题 滑动窗口（想到滑动窗口能做 但自己采取了不一样的解法 考完后分析了一下 虽然平均复杂度是O(n) 但在极端情况下是O(n²) 所以估计会有用例超时） 下午美团笔试 第一题 魔法外卖 排序+贪心 100% 第二题 扫地机器人 模拟 18% （自己出了点失误，移动机器人的代码写在了if里，导致去过的地方不去了） 第三题 扑克 循环找位置 100% 第四题 合法元组数 暴力 82% 第五题 二叉树路径金钱和 递归遍历 100% 没有把握住这两场难度较低的笔试，...

微软笔试题，根据讨论区内容写了一下前2题，第3题如果之后写出来会再更新 第1题：给定N个数，要求把N个数分为M组，每组内不能有重复的数，求每组最大的数和最小的数差，求所有的差求和最小的结果。 其实没有想到特别直观的方法，如果有比较好的思路请指导。 思路：先去除不可行情况，再最小到大排序、记录每个数的值和出现的次数，然后先从小到大简单贪心，再对后面出现的无法处理的情况贪心的做调整。 /* 1. 讨论去除不可行条件：1. N无法整除M，2. N中存在某个数字出现次数大于M 2. 对于可行条件，先排序，从小到大记录数字和其出现次数 3. 对于M个组，贪心生成每个组，从小到大选取...