FB电面

1.  leetcode 原题 move zeros  还要求证明算法的正确性。

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

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

6, 7, 9, 10, 12, 14,

您好！
本帖隐藏的内容需要积分高于 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

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

也来一个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应该无所谓吧，还是另有玄机？

第一题证明算法正确性什么意思？非0元素要保持原有顺序不变吗？

第二题的B数组什么意思？

就是为什么你的算法就是正确的。
第二题的B数组的值指的是对应prime number可以相乘的最多次数。

第二题还要求用尽量少的空间。在输出的过程中，不能保存已经output的数

pineapple1985 发表于 2016-10-14 11:39
第二题还要求用尽量少的空间。在输出的过程中，不能保存已经output的数

那第二题就是backtracking喽？

第一题楼主什么方法做的？和LC那题一模一样还是有区别？

iPhD 发表于 2016-10-14 11:41
那第二题就是backtracking喽？

第一题楼主什么方法做的？和LC那题一模一样还是有区别？

第一题一模一样。
第二题backtracking是合理的。我用了递归。

pineapple1985 发表于 2016-10-14 11:43
第一题一模一样。
第二题backtracking是合理的。我用了递归。

楼主多久收到结果的呀？

iPhD 发表于 2016-10-14 11:46
楼主多久收到结果的呀？

面完几个小时后。

iPhD 发表于 2016-10-14 11:46
楼主多久收到结果的呀？

能否解释一下backtracking的做法啊。不是很懂那道题是什么意思。 为什么输出会出现1？不是A组数字之间想乘么？

1是第一个书。相当于1 = 2^0 * 3^0 * 5^0 * 7^0