Tiktok Intern OA

第三题是dfs+memo模版题。和第二题几乎一样，只不过多了一点维度。

shenjiaqing 发表于 2022-10-03 22:27:18
第三题是dfs+memo模版题。和第二题几乎一样，只不过多了一点维度。

后来想想是对的，三维dp很好搞，但是当时因为用树状数组，下标从0开始一直死循环，后面思路跟不上了，哎，没关系

匿名用户 发表于 2022-10-03 22:17:36
想请问第一题楼主是用什么语言做的遇到卡常了呀 听做过的朋友说好像python c++ js没有这个问题

我用的cpp，我十分肯定不是我的问题，因为一个log而已，正常的算法题不该卡这个，尤其是笔试

匿名用户 发表于 2022-10-3 22:17
想请问第一题楼主是用什么语言做的遇到卡常了呀 听做过的朋友说好像python c++ js没有这个问题

我Java被卡了，一整个心态搞崩了，主要是input type有点恶心，一时间没想起来别的语言怎么string变integer。。。

LeoLv 发表于 2022-10-4 11:41
哦哦懂了 请问第一题是要求O(n)的么

O(nlogn)也可以

匿名用户 发表于 2022-10-4 13:17
想请问第一题楼主是用什么语言做的遇到卡常了呀 听做过的朋友说好像python c++ js没有这个问题

C++,这题卡常，身边朋友都遇到了

爱吃虾的老虎 发表于 2022-10-4 14:39
我Java被卡了，一整个心态搞崩了，主要是input type有点恶心，一时间没想起来别的语言怎么string变intege ...

这个倒不难写，c++的stl有类似的东西可以直接读，但是这个传参方式就让人很不爽

米少看不了，可以贴回复里吗？

第一道coding题请问是哪种方法过不了测试呀
还有时间复杂度是多少

微信用户_7038874 发表于 2022-10-5 01:05
米少看不了，可以贴回复里吗？

前面两道选择题，都很简单，没啥问题
算法第一题，给出一个序列a和序列b，问能不能通过给序列a的一部分或者全部元素 + 1，让a成为b的一个permutation
都2202年了，还有人把数组以string形式传参，差评！！而且这题卡常，差评x2！！不是很懂又考输入处理又卡常有啥意义，没活整了可以咬个打火机。最后做了一些常数级别优化过了。
第二题，给出n个雨伞，每个雨伞能覆盖a[i]个人，有无限把，问m个人最少需要几把雨伞能覆盖掉
这个很裸，不多赘述了
第三题，就是给出一个01矩阵，每次横切或者竖切，横切上半部分丢弃，下半部分继续，竖切左边丢掉，右边继续，问有多少种方法切成k块，使得每一块包含至少一个1
这个不给范围，但是hidden case的cout能看输入范围，n，k是50。没啥思路，二维前缀和不会，用二维树状数组写‍‌‍‌‍‍‍‌‍‌‌‍‌‌‌‌‍‍‌‍的一个n^5大dp，最后t了一个点，挺复杂的，写到最后人都麻了。
然后总结，整体体验很一般。a了2题多，看脸了。