maxArithmeticLength这题要怎么写啊？

lzl987 · 2019-10-23 02:37:56

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

inputA=[0,4,8,16]
inputB=[0,2,6,12,14,20]
问从B中最多选几个数字能让A成为一个等差数列
这道题实在是没思路，感觉是用DP，但又不知道要怎么写，求大神们指导，会加米的

Joyliu290

遇到过类似的，只不过要最终 answer 的 length 如果把 b 的一些element 加到 a. 比如说 a=[0, 4, 8, 16] b = [0, 2, 6, 12, 14, 20] 答案是 6. 以下是我的code:

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

求大米！！谢谢！

飘然旷野

这个题貌似有一个题设条件，a的长度大于等于2. 首先找到a间隔的最大公约数gcd，对gcd的每一个约数d，进行试探，试探之前把b的元素放于set之中。试探步骤:从a的第一个数字开始，试探是否存在该数字+d于a或者b之中，注意考虑a的第一个元素-d和最后一个元素+d的情况。

loveltyoic · 2019-10-23 23:07:12

codeyy 发表于 2019-10-23 08:02
能帮找一个题号或搜索关键字吗？

抱歉记错了。不过我的一个BF思路是，先把B做成hash map，然后计算A中所有相邻数之差的最大公约数，然后从这个最大公约数向1遍历所有因子，看以这个因子为等差的话是否都能从B中找到需要插入的数，如果都能，当前插入的数量就是最少的。

loveltyoic · 2019-10-23 07:32:03

leetcode原题吧

codeyy · 2019-10-23 08:02:47

loveltyoic 发表于 2019-10-23 07:32
leetcode原题吧

能帮找一个题号或搜索关键字吗？

pcheng11 · 2019-10-28 11:37:40

第四题 a.append(b); a.sort() 然后a里面找longest arithmetic subsequence? LC1027

ChantToGreen

pcheng11 发表于 2019-10-28 11:37
第四题 a.append(b); a.sort() 然后a里面找longest arithmetic subsequence? LC1027

不行吧，A={1，100}，B={2，3，4，5}

Luffy_Tse

题目应该是最少选几个数字吧？
我的想法和二楼一样，从A数列的所有相邻差的最大公约数开始，遍历所有约数从大到小。

lizzielee · 2019-11-10 06:14:45

Joyliu290 发表于 2019-11-7 11:27
遇到过类似的，只不过要最终 answer 的 length 如果把 b 的一些element 加到 a. 比如 ...

原来还要挨着试factor...好麻烦

[高频题] maxArithmeticLength这题要怎么写啊？