4.3 微软笔试题回忆
昨晚笔试被微软爸爸虐哭😰其实是我太菜了hh 虽然做题做得要自闭了…还是先记录一下以便之后再想解法。以下是我自己理解的题意,如有纰漏请大家指正~
1. 击鼓传花
嗯…突发奇想给这题起了个名😂
N个人每个人编号1-N,编号能整除的两个人互相连通,从编号为i的人开始传,最后要传回i手上,要在T次之内传完,问最多有几种传法?
测试
参数:N=3, i=2, T=2
路径:2-1-2
返回:1
参数:N=3, i=2, T=4
2-1-2
2-1-3-1-2
2-1-2-1-2
返回:3
思路
1. DFS
2. DP
2. 最少射击几次
N个瓶子都有编号,每次能射击1个或多个瓶子,如果是回文的就能一次性击倒。最少几次能全击倒?
测试
输入:[1, 2]
输出:2
输入:[1,3,4,1,5]
输出:3
说明:第一次先射3,变成[1,3,1,5],因为有[1,3,1]回文可以一次击倒,剩下[5]再一次
思路
本来看到回文就一直在想怎么找回文,后来感觉不对啊,好像方向走偏了…
看大佬评论说可以用DP,不过状态转移方程还没想明白…
3. 排队
N个人排队编号1-N,可能3种情况:
E1: 排在队首的人离开
E2: 队伍中编号为K的人离开
E3: 返回编号为X的人在队伍中的位置
输入一组query,返回所有E3累加的结果
测试
N=5 query=3
[1,0] [2,3] [3,2]
输出:1
说明:第一次队首编号1的人走了,第二次编号为3的人走了,第三次编号2的人排在队伍中的第一个
思路
感觉这题是4题里相对最容易的了,可是我还是有2个测试用例没过TAT
我想得比较简单,用一个数组pos保存每个人在队中的位置,E1则每人pos-1;E2则K之后的人pos-1,K之前的不变;E3则将pos[x]累加。
4. 蜜蜂采蜜
蜜蜂从家里出发,有几朵花和几处仓库(有坐标),每朵花有一份蜂蜜,蜜蜂一次只能带一份蜂蜜,可以先把采好的蜂蜜送到仓库,最后要回到家里。蜜蜂飞一单位的距离就会消耗一单位的时间(欧式距离),在限定时间T内,蜜蜂最多能采多少蜂蜜?
测试
这题数据太多记不清了…只记得参数了:
• home坐标:[x, y]
• m朵花
• n个仓库
• 花的坐标 二维数组
• 仓库坐标 二维数组
• 限定时间 T
思路
这题其实不太会…本来想用贪心,每次找最近的花/仓库,但是还要保证最后能在规定时间里到家,所以应该还要保存之前的路径?后来选择放弃这题了…
最后总结一下,微软的编程题首先是理解题目,其实每题都是用应用场景包装了一层,要从中抽象出核心的问题。
时间其实不是太大问题…因为真不会的题就算耗很多时间也搞不出来…所以平时不太刷算法题就很吃亏。另外感觉DP的挺常用的,不过自己DP还用得不熟,所以有些题只是有思路但跑不出来…以后要多多练习!