P****e 发帖数: 56 | 1 leetcode上没有的:
有N片叶子和一个毛毛虫。这个毛毛虫身上被写了几个编号.
毛毛虫站在0的位置,然后跳到第1片叶子 ... 最后到第N片。 它在第K片叶子时,如果
K能被任何一个它的编号整除,它就会把这片叶子吃了,然后继续往前走。
输入N ( 1<=N<=1000000000)表示叶子片数, 和一个array A( 2<=size<=20) array里
包含毛毛虫所有的编号。求最后没有被吃掉的叶子总和。
比如: N=10, A = 2,4,5, 输出: 4 (第2,4,5,6,8,10 片叶子都被吃了)。
注意时间和空间的代价。 | d*******n 发帖数: 43 | 2 上次没看清题是有序的 被大家嘲笑
这次我再来试试
这个应该是类似筛法求素数 假设编号数组有序
2 2*2 2*3 2*4 2*5 2*6
3 3*3 3*4
4 4*4
5 5*5
这样空间是N 时间也是N
其实我想到了lc上一个很类似的题 也是2 3 5做为种子 然后求能被其中两个整除还是
怎么样
【在 P****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : leetcode上没有的: : 有N片叶子和一个毛毛虫。这个毛毛虫身上被写了几个编号. : 毛毛虫站在0的位置,然后跳到第1片叶子 ... 最后到第N片。 它在第K片叶子时,如果 : K能被任何一个它的编号整除,它就会把这片叶子吃了,然后继续往前走。 : 输入N ( 1<=N<=1000000000)表示叶子片数, 和一个array A( 2<=size<=20) array里 : 包含毛毛虫所有的编号。求最后没有被吃掉的叶子总和。 : 比如: N=10, A = 2,4,5, 输出: 4 (第2,4,5,6,8,10 片叶子都被吃了)。 : 注意时间和空间的代价。
| N******G 发帖数: 33 | 3 容斥原理,O(2^20)时间复杂度,O(size)空间复杂度 | z*********n 发帖数: 1451 | 4
时间应该 O(2^10)= O(1000)就够了。
2 4 5这种情况,跟2 5一样,4可以忽略
所以最多就是11,12,13,14。。。20
如果任何小于10的数n存在,那么,他可以替换掉n*2的数。
比如7存在,那么14就多余了,需要考虑的总数还是不超过10个。
空间O(array.size)没错。
【在 N******G 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 容斥原理,O(2^20)时间复杂度,O(size)空间复杂度
| g****y 发帖数: 2810 | 5 1、 楼上提到了 array A里面的数字必须是相互不能整除的。这样可以做第一步的优化
。所以{2,4,5}就变成了{2,5}。
2、在A中只有一个数字情况下,这个问题很简单结果就是N-N/a[0]。在例子中就是10-
10/5=5。剩下的数字为:1,3,5,7,9,被去掉的是:2,4,6,8,10。
3、那么第二个数怎么解决呢?直观的来说就是N-N/a[1],可是不可避免的会有数字被
减去了多次。去掉的数字是5和10,这里的10被去掉了两次。但是幸运的事我们发现了
被重复去掉的都是能整除2、5的最小公倍数的。所以我们的最终结果就是
N-N/a[0]-N/a[1]+N/lcm(a[0],a[1])=10-5-2+1=4。
这里假设我们有lcm函数求最小公倍数(least common multiple)。他的时间复杂度是
O(logN)。
4、多余2个被除数的情况可以以此类推。我们假设N=30, a={2,3,5},结果就是:
N-N/a[0]-N/a[1]-N/a[2]+ N/lcm(a[0],a[1])+ N/lcm(a[0],a[2]) + N/lcm(a[1],a[2]
)-N/lcm(a[0],a[1],a[3]) = 30-30/2-30/3-30/5+30/6+30/10+30/15-30/30=8
剩下的数字为:1,7,11,13,17,19,23,29,正好8个数啦。
时间复杂度是O(2^A*logN),logN是上面提到的最小公倍数,空间就是O(A)了。这里A是a
.size。
5、代码不好写,我就不给了。lcm需要求gcd的互除法。
:leetcode上没有的:
:有N片叶子和一个毛毛虫。这个毛毛虫身上被写了几个编号.
:毛毛虫站在0的位置,然后跳到第1片叶子 ... 最后到第N片。 它在第K片叶子时,如
果K能被任何一个它的编号整除,它就会把这片叶子吃了,然后继续往前走。
:输入N ( 1<=N<=1000000000)表示叶子片数, 和一个array A( 2<=size<=20) array里
:包含毛毛虫所有的编号。求最后没有被吃掉的叶子总和。
:比如: N=10, A = 2,4,5, 输出: 4 (第2,4,5,6,8,10 片叶子都被吃了)。
:注意时间和空间的代价。
【在 P****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : leetcode上没有的: : 有N片叶子和一个毛毛虫。这个毛毛虫身上被写了几个编号. : 毛毛虫站在0的位置,然后跳到第1片叶子 ... 最后到第N片。 它在第K片叶子时,如果 : K能被任何一个它的编号整除,它就会把这片叶子吃了,然后继续往前走。 : 输入N ( 1<=N<=1000000000)表示叶子片数, 和一个array A( 2<=size<=20) array里 : 包含毛毛虫所有的编号。求最后没有被吃掉的叶子总和。 : 比如: N=10, A = 2,4,5, 输出: 4 (第2,4,5,6,8,10 片叶子都被吃了)。 : 注意时间和空间的代价。
|
|