Akuna Capital OA

第四题用backtrack 写了一下 感觉 复杂度很高啊， 也不知道对不对， 感觉应该会有DP的解法

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. int getSum(vector<int>& A) {
   
6.         int res = 0;
   
7.         for(const auto& n : A)
   
8.                 res += n;
   
9.         return res;
   
10. }
    
11. 
    
12. void dfs(vector<int>& A, vector<int>& res, vector<int>& cur, int start, int skipCount){
    
13.         if(start == A.size() || skipCount < 0){
    
14.                
    
15.                 if (cur.size() == res.size()){
    
16.                         if (getSum(res) < getSum(cur)) {
    
17.                                 res = cur;
    
18.                         }
    
19.                 }else if(cur.size() > res.size()){
    
20.                         res = cur;
    
21.                 }
    
22.                 return;
    
23.         }
    
24.         if (cur.empty() || A[start] > cur.back()) {
    
25.                 cur.push_back(A[start]);
    
26.                 dfs(A, res, cur, start+1, skipCount);
    
27.                 cur.pop_back();
    
28.                 dfs(A, res, cur, start+1, skipCount-1);
    
29.         }else{
    
30.                 dfs(A, res, cur, start+1, skipCount-1);
    
31.         }
    
32. }
    
33. 
    
34. vector<int> subrange(vector<int>& A, int m){
    
35.         vector<int> res;
    
36.         vector<int> cur;
    
37.         dfs(A, res, cur, 0, m);
    
38.         return res;
    
39. }
    
40. 
    
41. int main() {
    
42.         vector<int> test0 = {1,2,3,1,5,7,0};
    
43.         vector<int> res;
    
44.         res = subrange(test0, 3);
    
45.         for(auto& n : res){
    
46.                 cout << n <<" ";
    
47.         }       
    
48. }

复制代码

多谢LZ分享，OA不能用java啊？坑爹啊

lookbackinanger 发表于 2016-9-3 01:28
请问下第四题是一定要skip恰好是m个数么? 还是可以skip up to m个数?

我觉得是最多skip m 个，因为是找最长串，但是我做OA时候没时间测试，而且没有记录题目的测试例子，所以不一定正确

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

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

zyoppy008 发表于 2016-9-14 07:33
你这样discard是不对吧。
他说discard应该是最多discard多少张，来让你找到最长的subsequence。就是说你 ...

感谢回复，确实因为我做OA的时候来不及测试，所以也不太清楚自己的答案是否正确，还是题未刷够.........

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

fish444555 发表于 2016-8-22 08:59
我应该是投这个，基本是点进去那题才能看到用什么语言，大部分题都是 c++ & python 3， 我看到有一道题还 ...

问下楼主每一题都要用python 3写吗？
用python 2行不行

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

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

aangel 发表于 2016-9-14 11:37
问下楼主每一题都要用python 3写吗？
用python 2行不行

我看过几题（没有全部看）的语言选择，基本都有c++ & python 3, 只有1题可以用 python 2