FB电面

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

pineapple1985 发表于 2016-10-14 12:14
如果B里面全是0， 你这个code好像没输出。但是输出应该是1。
另外time应该是times吧？ 这个code会不会有 ...

对，要提前打印一个1出来，我写的太急了。

一亩三分地的编辑器有问题，把我代码弄乱了，是times(i).

pineapple1985 发表于 2016-10-14 12:14
如果B里面全是0， 你这个code好像没输出。但是输出应该是1。
另外time应该是times吧？ 这个code会不会有 ...

质数想乘不会有重复结果的

输出没有要求是排好序的吧？

也来一个backtracking的

1. void prime_product(vector<int> &res, int product, vector<int> &primes, vector<int> &nums, int i)
   
2. {   
   
3.     if (i == (int)primes.size()) {
   
4.         res.push_back(product);
   
5.         return;
   
6.     }
   
7.    
   
8.     int p = 1;
   
9.     for (int j = 0; j <= nums[i]; j++) {
   
10.         prime_product(res, product * p, primes, nums, i+1);
    
11.         p = p * primes[i];
    
12.     }
    
13. }
    
14. 
    
15. int main()
    
16. {
    
17.     vector<int> res;
    
18.     vector<int> primes = {2, 3, 5, 7};
    
19.     vector<int> nums = {1, 2, 1, 3};
    
20. 
    
21.     prime_product(res, 1, primes, nums, 0);
    
22. 
    
23.     //Does the output need to be sorted?
    
24.     //sort(res.begin(), res.end());
    
25. 
    
26.     for (int i: res)
    
27.         cout << i << " ";
    
28.     cout << endl;
    
29. 
    
30.     return 0;
    
31. }
    

复制代码

补充内容 (2016-10-14 12:46):
别外，这个是不是prime应该无所谓吧，还是另有玄机？

iPhD 发表于 2016-10-14 12:18
质数想乘不会有重复结果的

确实会有重复，需要加一个start index，下一次递归时，从i开始，而不是每次都从0开始。

minggr 发表于 2016-10-14 12:44
输出没有要求是排好序的吧？

也来一个backtracking的

啊，了解了，prime才不会产生相同的product

第二个说实话没太看懂，  /* 第二题的B数组的值指的是对应prime number可以相乘的最多次数。 */ 如果b数组厘米对应的是prime number可以相乘的次数，是跟自己相乘吗？如果是，那output里的6是怎么来的？

没排序要求，要求同一个数不能重复输出。空间复杂度要求O(n), n是数组 A, B的长度。所以要求primes都是不同的

2^1 * 3^1 * 5^0 * 7^0 = 6