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 的大作中提到】
: 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 的大作中提到】
: 容斥原理,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 的大作中提到】
: 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 片叶子都被吃了）。
: 注意时间和空间的代价。
|
|
