狗家OA 9/16/2021

winner_2018

第二题two pointers，Time: O(n)，加米！

kkkkxxxx

跟lz一个时间段做的oa，lz有收到next step嘛

OatBeverage

winner_2018 发表于 2021-9-20 18:26
第二题two pointers，Time: O(n)，加米！

第二题请问怎么2 pointers实现？

colwind

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

colwind

nikomiko 发表于 2021-9-17 16:14
有人可以发布第一个问题的代码吗？

已发，求加米

匿名用户-KD9H8 *2021-9-23 02:22:27* · 2021-9-23 02:22:27

winner_2018 发表于 2021-9-20 21:26
第二题two pointers，Time: O(n)，加米！

同问2pointers怎么实现？

Shabishabi

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

南宫狗剩

尝试一下第一题：
用一个hashmap，key=array[i] - array[0] - i, val = i，每次碰到新的key就存入map，已经有了的话计算i - map[key]取最大值。
时间O(n)，空间O(n)

南宫狗剩

尝试一下第二题：
第一遍遍历从左往右，计算从左边删达到第i位的最小消耗
第二遍遍历从右往左，计算从右边删达到第i位的最小消耗
然后计算a[i]+b[i+1]的最小值
时间O(n)，空间O(n)

刘樂樂

Shabishabi 发表于 2021-9-23 12:22
双指针i和j初始化为0和n-1，然后再用两个指针做cursor。用cursor向中间遍历，遇到a停下；遇到b时，算下从 ...

其实只要遍历A[i-1]和A[i+1],如果有b就删没b就继续往里走，不知道对不对