【每日一题】相伴一生；及构造最大数分析

arron刘

今日面试题：相伴一生

给定一个数组，数组中只包含0和1。请找到一个最长的子序列，其中0和1的数量是相同的。
例1：10101010 结果就是其本身。
例2：1101000    结果是110100
请大家展开自己的思路。



=========================
构造最大数分析
原题

给定只包含正数的数组，给出一个方法，将数组中的数拼接起来，得到的数，是最大的。 例如： [4, 94, 9, 14, 1] 拼接之后，所得最大数为：9944141



一个巧妙的方法

我们在上面的方法中，相当于，比较两个数字的时候，把两个数字拆开，逐位进行比较。那我们接下来，就是将这两个数字，作为一个整体，进行比较。然后一次排序，就得到了结果。给定例子：5,54,56

比较5和54，实际上就是比较545和554哪个大

比较5和56，实际上就是比较556和565哪个大

比较54和56，实际上就是比较5456和5654哪个大

那我们对快排程序做一下变化，当两个数字a和b进行比较时，比较的是ab和ba两个数字的大小即可。只是比较发生了变化，剩下的和快排都是一样的。

相比较而言，后面这种方法，更简单易懂一些，而且，看上去要美很多，但是确不容易那么直接的想到。我们在平时积累的过程中，就要尝试多多的方法，即使看起来不那么美的方法，这些思路的开拓，会帮助我们举一反三，帮助我们在遇到新的题目的时候，游刃有余。

【分析完毕】

dextercu

我感觉这个题就是 统计 1 和 0的数目，较小的那个 *2 就是 长度了。知道长度以后，再扫描一遍 验证一下就行了。 应该可以O(n) 解决。

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. string les(const string & str) {
   
8.     int c[2] = {0, 0};
   
9.     for (int i = 0; i < str.size();i++)
   
10.         c[str[i] - '0']++;
    
11.     int length = min (c[0], c[1]) * 2;
    
12.     int begin = 0, end = 0;
    
13.     c[0] = 0;
    
14.     c[1] = 0;
    
15.     while (end < length) {
    
16.         c[str[end] - '0']++;
    
17.         end++;
    
18.     }
    
19.     while (c[0] != c[1]) {
    
20.         c[str[begin++] - '0']--;
    
21.         c[str[end++] - '0']++;
    
22.     }
    
23.     return str.substr(begin, length);
    
24. }
    
25. 
    
26. int main() {
    
27. 
    
28.     string case1 = "10101010";
    
29.     string case2 = "1101000";
    
30. 
    
31.     cout << les(case1) << endl;
    
32.     cout << les(case2) << endl;
    
33. 
    
34.     return 0;
    
35. }

复制代码

dextercu

才发现我的解法是错的，因为有10001这样的情况。
我觉得正确的解法是，扫描一遍数组，记下到目前为止多出的1的数目，把结果记在一个数组里，这个结果数组中 最大的 相同数字的跨度就是最长的01字符串。

1. #include <iostream>
   
2. #include <map>
   
3. #include <algorithm>
   
4. #include <map>
   
5. 
   
6. using namespace std;
   
7. 
   
8. string les(const string & str) {
   
9.     int* table = new int[str.size() + 1];
   
10.     table[0] = 0;
    
11.     for (int i = 0; i < str.size(); i++)
    
12.         table[i + 1] = table[i] + (str[i] == '1' ? 1 : -1);
    
13.     map<int, int> m;
    
14.     int begin = 0, end = 0, longest = 0;
    
15.     for (int i = 0; i <= str.size(); i++) {
    
16.         pair<map<int,int>::iterator, bool> result = m.insert(pair<int, int>(table[i], i));
    
17.         if (!result.second) {
    
18.             if (i - m[table[i]] > longest) {
    
19.                 longest = i - m[table[i]];
    
20.                 begin = m[table[i]];
    
21.                 end = i;
    
22.             }
    
23.         }
    
24.     }
    
25.     delete [] table;
    
26.     return str.substr(begin, end - begin);
    
27. }
    
28. 
    
29. int main() {
    
30. 
    
31.     string case1 = "10101010";
    
32.     string case2 = "1101000";
    
33.     string case3 = "0001000100010001000";
    
34. 
    
35.     cout << les(case1) << endl;
    
36.     cout << les(case2) << endl;
    
37.     cout << les(case3) << endl;
    
38. 
    
39.     return 0;
    
40. }
    

复制代码

sublx

我怎么觉得原题中的分析，在比较两个数大小的时候，比如列举的，5和54，5只有一位，54两位，两个数第一位相同，那么5就应该比54大，因为5后面可以接任何数字。也就是说两个数a 和 b ，如果假设b的长度(n+x)比a(n)长，前面n位都一样，那么a就应该排在b前面。
不知道这样理解对不对。

uuuououlcz

回复 1# arron刘

同样是O(n)，感觉还是这样好一些：设置一个变量标志sum，从头开始遍历，遇到1，则sum +=1，遇到0，则sum -= 1，如果a之后sum = 0的时候，标志着从0到i的1和0的数目相等，这样子记录最大值的下标就是要求的子串