小马智行（pony.ai）9.26笔试AC情况

我至今不知道为啥我没笔试😅

如果有大佬AC了请发布一下思路。。题目是小马智行第二套卷，我投递的是算法工程师，非常感谢

第一题直接排序；第二题二分答案，然后枚举a到z利用滑动窗口求解答案是否合法；第三题并查集裸题，第四题50%的数据应该爆搜可过，100%求大佬解答；不得不说小马的题出的确实不错，随便贴一下前三题代码:https://paste.ubuntu.com/p/75tYHvNRJS/

第三题自己怎么测都没问题 一交就是0

题目难度为easy,medium,medium,hard AK了 10点贴个cpp代码

我真醉了，第一题就是排序啊？第三题就是并查集啊？？我本地测了好几个用例全是对的，提交就是百分之0啊？？？结果你告诉我int换long long ？？？我还以为我算法本身错了，但是我测了好几个用例都是对的 我擦，本来前三题直接秒了，结果一直0%，看半天不知道为什么，心态炸了都没做第四题

第三题并查集为啥0% 搞不懂啊明明

xdm 求个第二题哇

50min全a，希望能帮助到大家 我主页有全部代码 1 // 排个序 还用想？ 因为是平方呀 2 // 这题可能有点麻烦？ 首先求最小肯定可以二分 // 主要是看枚举每个字母看一段区间里面有没有 我直接用前缀和差的， 这样方便写 // 其实也可以直接记录一个最尾部的字母位置来判断 3 // 这个题比较明显，其实一开始想的是并查集，但一想不就是个联通分量吗，直接dfs即可 4 /* 这个题我喜欢 首先根据第二个样例就能发现难点在哪里 到底在哪里呢？ 1 1 1 1 前两个[1,1] 可以和后两个[1,1] 组合 也就是说前面如果有一段 合法组合 后面也有一段合法组合 ，那么就能合并 如何合并呢？ 我们先想不合并的： 如果以i为起点的话，后面的选择是不是c(n-i,a[i]) (组合数从i+1到n中选a[i]个 ) 加上合并不合法的就是 ： 从i开头选一个第一段的结束位置 ，假设这个位置是j ， 那么以i开头的方案数 就是(i到j)的方案数 *(后面以j+1,j+2,j+3.....开头的方案数+1) 组合数用的打表 加 乘法逆元，大家没acm基础的可以看这个： https://blog.csdn.net/weixin_43916298/article/details/103919099 当然这题目应该有直接计数dp的写法，我感觉我的思路比较明显就直接写了 */

看起来第二题不到mid的难度。

大概多少可以进面试？

可以看看我们公司，也是做无人驾驶的，没有笔试哟，私戳我给内推码

还好给我免笔试了。我知道难没想到这么难

我这个第三题为啥一直0%呀 求大佬解答

1-60，2-50。。。

第一题是瞧不起C++吗? int 改 long long 直接通过率0变100%。

前三题很快解决，第四题开始想用dp，想不出来，想爆搜感觉也不太行，关键是他有分割的，求个思路

题目和LZ的一样 第一题排序 第二题算每个字母的最大间隔，然后取这些最大间隔的最小值。注意要假设在字符串头尾补上万能字符 第三题并查集 前三题AC了 第四题dp做的，30%

第二题这种有个通用解法叫做“二分答案验证”，时间复杂度nlogn。

今天的题就是正常leetcode周赛难度吧，easy medium medium hard。然而我还是做不出hard