Google : 求最长等差数列

把差hash到1,2,3,4...不就行了（最多只有O(N^2)种差）回复 10# wwwyhx

把差hash到1,2,3,4...不就行了（最多只有O(N^2)种差）回复  wwwyhx
swordsnow 发表于 2011-9-5 20:28

    可以是可以,一个是这个方法太ugly了, 还有一个是要用hash还不如用二楼的方法更直接

epic 发表于 2011-7-28 15:34
平方的算法应该还是不难的吧？
首先做一个hash表，维护key={a,b} value=c，含义是以a开始的差为b的等差数列 ...

我觉得这个方法有问题。
hash表查找num[i], num[i]-num[j]之后，如何更新呢？
这个hash表示的是最长的长度，而不是有多少个差是b的值？
请指教。

sing1ee 发表于 2013-9-5 11:31
我觉得这个方法有问题。
hash表查找num, num-num[j]之后，如何更新呢？
这个hash表示的是最长的长度，而 ...

1. 我发现我确实是打错了,是查num[j],num[j]-num[i]的值来更新num[i],num[j]-num[i]……
   
2. 
   
3. for (int i = n-1; i>=0; --i) //注意顺序
   
4. for (int j = i+1;j<n;++j)
   
5. {
   
6.      差 d = num[j] - num[i]
   
7.      MAP[num[i],d] = MAP [num[j],d] + 1
   
8. }

复制代码

1. 
   
2. #include <iostream>
   
3. #include <algorithm>
   
4. #include <cstring>
   
5. 
   
6. using namespace std;
   
7. 
   
8. int n;
   
9. int a[10001];
   
10. 
    
11. //let's assume that sequence s(n) = a[i] s(n+1) = a[j]
    
12. //dp_matrix[i][j] represent the count of sequence in s
    
13. short int dp_matrix[10001][10001];
    
14. 
    
15. int main()
    
16. {
    
17.     cin >> n;
    
18.     for (int i = 0; i < n; ++i)
    
19.         cin >> a[i];
    
20.     memset(dp_matrix, 0, sizeof(dp_matrix[0][0]) * 10001 * 10001);
    
21.     short int max_len = 0;
    
22. 
    
23.     for (int i = 0; i < n; ++i)
    
24.     {   
    
25.         for (int j = i + 1; j < n; ++j)
    
26.         {   
    
27.             bool delta_is_match = false;
    
28.             int cur_delta = a[j] - a[i];
    
29.             for (int k = i-1; k >= 0; --k)
    
30.             {   
    
31.                 int delta_i_to_k = a[i] - a[k];
    
32.                 if (delta_i_to_k == cur_delta)
    
33.                 {   
    
34.                     if (dp_matrix[i][j] < dp_matrix[k][i] + 1)
    
35.                         dp_matrix[i][j] = dp_matrix[k][i] + 1;
    
36.                     else
    
37.                         cout << "k:" << k << " i:" << i << " j:" << j << endl;
    
38.                     delta_is_match = true;
    
39.                     break;
    
40.                 }   
    
41.             }   
    
42.             if (delta_is_match == false)
    
43.             {   
    
44.                 dp_matrix[i][j] = 2;
    
45.             }   
    
46.             if (dp_matrix[i][j] > max_len)
    
47.             {   
    
48.                 max_len = dp_matrix[i][j];
    
49.             }   
    
50.         }   
    
51.     }   
    
52.     //for_each(&dp_matrix[0], &dp_matrix[n], [=](short int p[]){for_each(&p[0], &p[n],[](short int n){cout<<n<<' ';});cout<<endl;});
    
53.     cout << max_len << endl;
    
54.     return 0;
    
55. }
    

复制代码

我的代码我觉得应该是对的  但是wa, 我还在想为什么..我算出来的结果比正确结果低  有一个正确结果是25  我算出来是7....

知道了....
他的意思是给出的数据不是一个数列 array 而是一个集合 set
让你在set里面找能够拼出来最长的, 这样的情况只要对set进行排序就可以按照上面的code解了....
但是目前还会tle  算法性能要优化一下, 我得看看

给个case, 输入:
100
1627
757
3019
4933
4237
2787
2265
6035
699
4121
235
2091
6325
4411
1859
3947
4527
6093
641
1047
2497
5107
1105
1975
5281
5687
3599
4585
4469
119
6383
5165
5513
409
3309
3367
1801
4353
3077
1569
2555
583
6267
3135
351
815
1395
2033
3541
5629
1453
1163
6151
2613
4991
3193
2323
2381
61
4005
5397
177
467
1685
2845
4817
931
5455
4179
3483
873
525
1917
1337
5919
5861
4759
4063
3657
3889
3773
3425
2439
3251
2207
5745
293
4643
5571
2671
2149
5049
1511
989
5339
4295
1743
3831
4701
5803

输出
25

darksteel 发表于 2011-7-29 13:11
不过我这个好像要升序的数组才行。。{:4_84:}

排序是0（nlogn）低于n^2完全可以先排序

1. 
   
2. 
   
3. #include <iostream>
   
4. #include <algorithm>
   
5. #include <cstdio>
   
6. #include <cstdlib>
   
7. #include <cstring>
   
8. #include <unordered_map>
   
9. #include <unordered_set>
   
10. 
    
11. using namespace std;
    
12. 
    
13. int n;
    
14. int a[10001];
    
15. 
    
16. //let's assume that sequence s(n) = a[i] s(n+1) = a[j]
    
17. //dp_matrix[i][j] represent the count of sequence in s
    
18. short int dp_matrix[10001][10001];
    
19. 
    
20. int main()
    
21. {
    
22.     //cin >> n;
    
23.     scanf("%d", &n);
    
24.     for (int i = 0; i < n; ++i)
    
25.         //cin >> a[i];
    
26.         scanf("%d", &a[i]);
    
27.     sort(&a[0], &a[n]);
    
28.     unordered_map<int, int> element_map;
    
29.     for (int i = 0; i < n; ++i)
    
30.     {   
    
31.         element_map[a[i]] = i;
    
32.     }   
    
33.     memset(dp_matrix, 0, sizeof(dp_matrix[0][0]) * 10001 * 10001);
    
34.     short int max_len = 0;
    
35.     const auto iter_end = element_map.end();
    
36. 
    
37.     for (int i = 0; i < n; ++i)
    
38.     {   
    
39.         for (int j = i + 1; j < n; ++j)
    
40.         {   
    
41.             int cur_delta = a[j] - a[i];
    
42.             int k_value = a[i] - cur_delta;
    
43.             auto iter = element_map.find(k_value);
    
44.             if (iter != iter_end)
    
45.             {   
    
46.                 dp_matrix[i][j] = dp_matrix[iter->second][i] + 1;
    
47.             }   
    
48.             else
    
49.             {   
    
50.                 dp_matrix[i][j] = 2;
    
51.             }   
    
52.             if (dp_matrix[i][j] > max_len)
    
53.             {   
    
54.                 max_len = dp_matrix[i][j];
    
55.             }   
    
56.         }   
    
57.     }   
    
58.     cout << max_len << endl;
    
59.     return 0;
    
60. }
    
61. 
    

复制代码

这个代码还是tle了  实在过不去了~~~~ 咋办?

laoxie09 发表于 2015-6-30 11:59
排序是0（nlogn）低于n^2完全可以先排序

甲骨文大大见信好,  我在http://www.1point3acres.com/bbs/ ... 8&page=1#pid1935366 发了个贴, 是关于求最长等数列的
我的代码目前的状态是tle  没有超时的case都是ac的
我能想到的优化方法都试过了, 但是还是差一点, 时间限制是2s, 我最长的case跑2500ms, 我不知道该从什么地方下手优化了.不知道您有没有什么好的建议?, 另附case:

case随附件附上, 太大了, 贴不上来
太大了贴不上来我也没找到怎么贴附件
(http:)

pan.baidu.com/s/1dDGrF6D

已经AC了, 把自己的代码贴上来, 这个地方需要自己写个哈希, 系统自带的__gnu_cxx::hash_map要快于unordered_map, 但是还是tle,
自己写的则快很多:

1. 
   
2. #include <iostream>
   
3. #include <algorithm>
   
4. #include <cstdio>
   
5. #include <cstdlib>
   
6. #include <cstring>
   
7. #include <map>
   
8. #include <unordered_map>
   
9. #include <unordered_set>
   
10. #include <ext/hash_map>
    
11. 
    
12. using namespace std;
    
13. using __gnu_cxx::hash_map;
    
14. 
    
15. int n;
    
16. int a[10001];
    
17. 
    
18. const int BUCKET_SIZE   = 42839;
    
19. const int NEXT_POS      = 7;
    
20. 
    
21. typedef struct _my_hash
    
22. {
    
23.     int _bucket[BUCKET_SIZE];
    
24.     int _key[BUCKET_SIZE];
    
25.     _my_hash()
    
26.     {
    
27.         memset(_bucket, 0, sizeof(_bucket[0]) * BUCKET_SIZE);
    
28.         memset(_key, 0, sizeof(_key[0]) * BUCKET_SIZE);
    
29.     }
    
30.     void insert(int key, int value)
    
31.     {
    
32.         int mod = key % BUCKET_SIZE;
    
33.         while (_key[mod] != 0)
    
34.         {
    
35.             mod = (mod + NEXT_POS) % BUCKET_SIZE;
    
36.         }
    
37.         _bucket[mod]    = value;
    
38.         _key[mod]       = key;
    
39.     }
    
40.     int find(int key)
    
41.     {
    
42.         int origin = key % BUCKET_SIZE;
    
43.         int mod = key % BUCKET_SIZE;
    
44.         while (_key[mod] != 0)
    
45.         {
    
46.             if (_key[mod] == key)
    
47.             {
    
48.                 return _bucket[mod];
    
49.             }
    
50.             mod = (mod + NEXT_POS) % BUCKET_SIZE;
    
51.             if (mod == origin)
    
52.             {
    
53.                 return -1;
    
54.             }
    
55.         }
    
56.         return -1;
    
57.     }
    
58. }my_hash_t;
    
59. 
    
60. //let's assume that sequence s(n) = a[i] s(n+1) = a[j]
    
61. //dp_matrix[i][j] represent the count of sequence in s
    
62. short int dp_matrix[10001][10001];
    
63. 
    
64. int main()
    
65. {
    
66.     //cin >> n;
    
67.     scanf("%d", &n);
    
68.     for (int i = 0; i < n; ++i)
    
69.         //cin >> a[i];
    
70.         scanf("%d", &a[i]);
    
71.     sort(&a[0], &a[n]);
    
72.     //unordered_map<int, int> element_map;
    
73.     //map<int, int> element_map;
    
74.     //hash_map<int, int> element_map(42839);
    
75.     my_hash_t my_hash;
    
76.     //hash_map<int, int> element_map;
    
77.     for (int i = 0; i < n; ++i)
    
78.     {
    
79.         //element_map[a[i]] = i;
    
80.         my_hash.insert(a[i], i);
    
81.     }
    
82.     memset(dp_matrix, 0, sizeof(dp_matrix[0][0]) * 10001 * 10001);
    
83.     short int max_len = 0;
    
84.     //const auto iter_end = element_map.end();
    
85. 
    
86.     for (int i = 0; i < n; ++i)
    
87.     {
    
88.         for (int j = i + 1; j < n; ++j)
    
89.         {
    
90.             int cur_delta = a[j] - a[i];
    
91.             int k_value = a[i] - cur_delta;
    
92.             //auto iter = element_map.find(k_value);
    
93.             //auto iter = element_map.end();
    
94.             int ret = my_hash.find(k_value);
    
95.             //if (iter != iter_end)
    
96.             if (ret != -1)
    
97.             {
    
98.                 //dp_matrix[i][j] = dp_matrix[iter->second][i] + 1;
    
99.                 dp_matrix[i][j] = dp_matrix[ret][i] + 1;
    
100.             }
     
101.             else
     
102.             {
     
103.                 dp_matrix[i][j] = 2;
     
104.             }
     
105.             if (dp_matrix[i][j] > max_len)
     
106.             {
     
107.                 max_len = dp_matrix[i][j];
     
108.             }
     
109.         }
     
110.     }
     
111.     cout << max_len << endl;
     
112.     return 0;
     
113. }
     

复制代码