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时候没时间测试，而且没有记录题目的测试例子，所以不一定正确

fish444555 发表于 2016-8-23 06:36
不确定是否正确，只测试了简单的例子

int[] nums1 = { 8, 9, 10, 1, 2, 3, 4};

你这样discard是不对吧。
他说discard应该是最多discard多少张，来让你找到最长的subsequence。就是说你要的sequence里面除了discard其他是连续的。 但是你没必要从头开始找。 也就是说你两头的不算discard
比如  7 6 5 7 19 23 2 43 48 12 11  discard 2  那应该是 5 7 19 123 43 48 中间的2 被discard了。 这样返回最长的subsequence。
如果按你这样 那可以直接找最长subsequence就好了。 然后算他是不是长度于原数组长度小于discard的个数。那就没意义了吧。

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

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

chris-sun 发表于 2016-9-3 03:07
第四题用backtrack 写了一下 感觉 复杂度很高啊， 也不知道对不对， 感觉应该会有DP的解法

你有没有考虑这种情况
40 50 500 700 1 2 3 4 5 6 7 8 9   discard 2
应该是从1 到 9 不discrad的。。。
而不是从头开始算。。。因为是subsequence 处于中间影响的可以被discard 刚开始不再开头选的话就是不算discard
这样的话 只需要把你写的算法 for 循环给每一个index 搞一遍就行 获取该index开始的最长sequence。
然后如果剩余元素小于这个sequence 循环就提前结束。
但是这样感觉复杂度很高啊。

zyoppy008 发表于 2016-9-14 08:17
你有没有考虑这种情况
40 50 500 700 1 2 3 4 5 6 7 8 9   discard 2
应该是从1 到 9 不discrad的。。 ...

说实话，我不太清楚题目的意思，如果按照你的输入，而且discard = 2的话，就感觉最多只能 discard 2 个数。按照我之前的想法，感觉不能构成单调递增序列，所以输出空, 我对比过41楼的代码，他使用你的输入，输出为 [40 50 500 700 ], 主要没有记录官方的测试例子，我也不确定真的题目的意图

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

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

fish444555 发表于 2016-9-14 08:51
说实话，我不太清楚题目的意思，如果按照你的输入，而且discard = 2的话，就感觉最多只能 discard 2 个数 ...

如果是我说的意思，那就很难做出高效的方法。
不过我觉得应该是这样的。。
不然直接求最长递增数列就行了。因为最长的递增数列 那他的剩余的数肯定最少 所以要么是他要么为空 那这个题不就是leetcode 原题  最后加一个判断条件嘛。。那啥dfs都没必要了。。
但是那样这个题就没啥意义了感觉。。

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

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