微软中国2020 OA

一共三题 1.5h 太难了呀

我就记得一题了 是给你一个数组A和A的长度K，A里每个数字代表气球，有个人射击气球，一次射击一个气球OR射击一排回文气球，输出最小射击次数
比如 A = [1 3 5 4 5 3 2 4 7 4]  那就是先射35453，再474 最后就剩下1和2 一共射击4次
比如A = [1 4 5 1] 那就得先射5，再141 一共射击2次
我本来一开心 oh这不是leetcode上做过的 找回文吗 while循环 找所有回文最后剩下几个气球就加几
后来一想不对。。。凉了凉了
应该用DP做👍

还有一题是星球大战还是啥 就是给你数组A，代表每个人的战斗值，要求了一组几个人。然后每组的战斗值差距 = 最大战斗值 - 最小战斗值，并且一组里的战斗值不能相等。问所有组的战斗值差距之和最小是多少。
比如A = [2 2 3 3 4 4 5 5 6 6 7 7], 分成3组，那就是【2 3 4 5】【2 3 6 7】【4 5 6 7】（应该是这样吧。。？）那么3 + 5 + 3 = 11 是最小的。返回11。类似这样子。

最后一题忘记了😢
求米求米谢谢大家呜呜👍

我打满了全场，然而一道题都没写出来……

第一道题 蠡口 burst ballons 先求出回文表，再用dp公式 dp[i][j] = isPalindrome[i][j] ? 1 : dp[i][k - 1] +dp[k +1][j] +1
第二道题 dp别想了，老老实实dfs暴力回溯。用dp的话将四个bit为1的mask收集为一个列表，然后用01背包整出最终结果，时间复杂度C(n, k)*(n / k)，肯定比回溯最优化剪枝要慢
第三道题感觉用dijkstra能做？

补充一下第三题 如果有人挑战一下智力极限
赛车问题 求最短时间 到达终点。n个城市 每个城市有自己的属性 Cop(直接淘汰) Sand(接下来两段路速度减半，在当前速度基础上) Nitro((接下来两段路速度加倍，在当前速度基础上) Crash(下一段路程耗时+一小时)
给了一个array of length n储存所有城市的属性
给了array of size [x][2] 每一行 [x][0]是一条路的起点城市[x][1]是这条路的终点城市 所以有x条路可以走
从一个城市出发 求到终点所需最短时间

Victor vshbd 发表于 2020/03/25 22:41:17
我打满了全场，然而一道题都没写出来……

我也是…

Victor vshbd 发表于 2020-3-25 22:41
我打满了全场，然而一道题都没写出来……

真的太难了。。。仔细一想全是DP

tokitoki 发表于 2020/03/26 00:06:00
真的太难了。。。仔细一想全是DP

第三题我用back-tracking做的

Victor vshbd 发表于 2020-3-25 09:41
我打满了全场，然而一道题都没写出来……

哈哈哈哈哈哈哈我也是！没事没事，下次再战

sooyaaa 发表于 2020-3-26 04:18
哈哈哈哈哈哈哈我也是！没事没事，下次再战

嗯嗯😂 奥利给

哈哈哈哈哈哈心路历程和我一模一样！看到那道回文题还在暗喜碰到原题了，结果越写越不对orz

OA这么难吗orz 还好我没做

因为时差弄错了时间没做😂
现在看来做了也白做😂