在准备面试时发现了这个问题.
假设一些毛毛虫从底部开始并跳到下一片叶子.他们在跳到下一个之前吃了叶子.我们得到一个数组,代表毛毛虫的跳跃步骤.如果阵列是[2,4,7],这意味着卡特彼勒[0]将吃叶2,4,6 ..卡特彼勒[1]会吃叶4,8,12 ..而卡特彼勒[2]会吃7 ,14,21 ...... 0代表地面.计算未吃叶子的数量.
让我们假设如果吃掉当前的叶子,毛虫会跳到下一个目的地.这意味着,如果毛虫[7]发现叶子28被吃掉,它将继续吃叶子35.
设c为毛毛虫的数量,n为叶子的数量.
显而易见的蛮力解决方案是针对每个毛毛虫在大小为n的布尔阵列上进行迭代,如果吃掉则将其标记为真,否则将其标记为假.它需要O(n*c)时间.我们可以做得更好吗？
假设我们有10个项目,每个项目都有不同的成本
项目:{1,2,3,4,5,6,7,8,9,10}
费用:{2,5,1,1,5,1,1,3,4,10}
和3个客户
{A,B,C}.
每个客户都需要一组项目.他将购买套装中的所有物品或不购买.每个项目只有一个副本.例如,如果
A需要{1,2,4},赚取的总金额= 2 + 5 + 1 = 8
B需要{2,5,10,3},赚取的总金额= 5 + 5 + 10 + 1 = 21
C需要{3,6,7,8,9},赚取的总金额= 1 + 1 + 1 + 3 + 4 = 10
因此,如果我们出售他的物品,B将不会向我们购买,因为我们不再拥有第2项物品.我们希望赚到最多的钱.通过卖B,我们不能卖给A和C.所以,如果我们卖A和C,我们赚18.但只要卖B,我们赚的更多,即21.
我们想到了一个位掩码解决方案,它按顺序呈指数级,但只适用于少量项目.和其他启发式解决方案给了我们非最佳答案.但经过多次尝试后,我们无法真正提出任何快速优化解决方案.
我们想知道这是一个已知问题,还是类似于任何问题？或者这个问题是NP Hard,因此多项式最优解不存在,我们试图实现一些不可能的事情？
此外,如果所有项目的成本相同,问题是否也会改变？
非常感谢.
这是程序:
#include <iostream>
using namespace std;
int removeDuplicates(int* nums, int numsSize) {
int count=1;
if(numsSize==1)
return 1;
else if(numsSize==0)
return 0;
for(int i=1;i<numsSize;i++)
{
while(i<numsSize && nums[i]==nums[i-1])
{
i++;
}
if(i==numsSize)
{
return count;
}
nums[count]=nums[i];
// cout << nums[i] << "-"<<std::endl;
count++;
}
}
int main() {
// your code goes here
int nums[3]={1,1,2};
cout <<"ans "<< removeDuplicates(nums,3);
return 0;
}
请注意评论
// cout << nums[i] << "-"<<std::endl;
在函数removeDuplicates中.在当前状态下,函数返回
3
.在取消注释上述陈述时,它会返回
134520320
至少在ideone上这样做:https://ideone.com/5m8xPj
我看到函数末尾应该有一个return语句.为什么编译器在最后没有看到return语句时会返回错误？为什么评论/取消注释导致返回如此奇怪的结果？
谢谢.