面试中遇到的一道题目

感觉多年不刷lc的我水平已经被秒了

简单dp呀^_^
lz你需要刷刷题

这道题还要考虑负数的情况，所以要先排序（假如数组是无序的），然后再HashMap正负各走一遍。
复杂度NlogN，如果数组有序的话直接就是N

南宫狗剩 发表于 2022-04-11 14:19:06
这道题还要考虑负数的情况，所以要先排序（假如数组是无序的），然后再HashMap正负各走一遍。
复杂度NlogN，如果数组有序的话直接就是N

和负数有什么关系。而且看题意，sublist排序顺序乱了不行吧。unsorted也没关系。hashmap存一个数和它往前最多多长的sublist。从前往后遍历一遍就行了吧

补充内容 (2022-04-12 06:01 +08:00):
嗯。。确实和负数有关。不过扫一遍就够了。另外不能排序吧，按题意感觉顺序不能换。不需要sorted数组也能做的。比方说第一个数是3，map存{3,1}。第二个数是6，6／2为3，map[3]为1，所以map存{6，2}。第三个数是4，4／2=2不在map里就存{4,1}。以此类推。不过负数是乘2，比如第四个数是－8，就要检查－16在不在map里。

nyufufu 发表于 2022-4-11 16:54
和负数有什么关系。而且看题意，sublist排序顺序乱了不行吧。unsorted也没关系。hashmap存一个数和它往前 ...

必须要排序。举个反例 list = [4,2,1]，你的map里会是map[4] = 1; map[2] = 1; map[1] = 1。

dacheng0413 发表于 2022-4-10 21:37
用set存｛数字｝，把数字放到deque，用map找double的新数字，有的话length++，map remove数字，没有的话 le ...

此乃正解！

南宫狗剩 发表于 2022-4-11 17:45
必须要排序。举个反例 list = [4,2,1]，你的map里会是map[4] = 1; map[2] = 1; map[1] = 1。

我觉得sublist里的数的循序应该和list一致才对。[4,3,2,1]不能组成[1,2,4]。嘛具体得问面试官了

O(N) O(N)
感觉不用排序，负数无所谓，把数都存到set，确保只过一遍。
不论从哪个数开始，*2 和 /2 两个方向试到尽头。
(Python没有integer不能随便除的问题, 0也可以)

1. def get_length(input):
   
2.     unvisited = set(input)
   
3.     max_cnt = 0
   
4.     for baseX in input:
   
5.         if baseX in unvisited:
   
6.             cnt = 1
   
7.             unvisited.remove(baseX)
   
8.             # Multiplication direction
   
9.             x = baseX
   
10.             while x * 2 in unvisited:
    
11.                 x *= 2
    
12.                 cnt +=1
    
13.                 unvisited.remove(x)
    
14.             # Division direction
    
15.             x = baseX
    
16.             while x / 2 in unvisited:
    
17.                 x /= 2
    
18.                 cnt +=1
    
19.                 unvisited.remove(x)
    
20.             # Record current sublist length
    
21.             max_cnt = max(max_cnt, cnt)
    
22.     return max_cnt

复制代码