[面试经验] Wish intern OA

需要

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

myang39 发表于 2019-1-19 04:25
能问一下lz怎么优化时间复杂度吗? 我现在的想法是:
1. brute force,就是loop through the roll array, 一 ...

假设new_roll = new int[s.size()], 我们很容易知道new_roll[0] = len(roll), new_roll[1] 等于多少呢, new_roll[1] = new_roll[0] - (1在roll中的个数), 因此可以写出一个转移方程: new_roll[i] = new_roll[i-1] - (i在roll中的个数)。而i在roll中的个数只要统计一次roll放在hash里面就可以了，时间复杂度O(len(s) + len(roll))

能问一下lz怎么优化时间复杂度吗? 我现在的想法是:
1. brute force,就是loop through the roll array, 一个一个去update s里的char
2. 先main一个new_roll[s.size()],物理意思是new_roll[i] 记录了第i个char需要update几次, 但是要fill这个new_roll, 也需要loop through the roll array 才能填完, 时间复杂度是一样的.

sandered 发表于 2019-1-20 02:03
就是统计每个字母需要(最终)移动多少次，到最后再来生成移动后的字符串。

楼主请问怎么统计呢 是不是先把roll数组排个序 然后二分查找啊

非常有用，请问楼主只有一道题吗？

想远眺的金蓝鸟 发表于 2018-12-21 10:33
非常有用，请问楼主只有一道题吗？

是的只有一道题

楼主是什么方向的？

楼主是内推的吗

除了这题 => Sol，再贡献一题比较简单

就是统计每个字母需要(最终)移动多少次，到最后再来生成移动后的字符串。