1

例如，有一个给定的字符串，它由1s和组成0s：

s = "00000000001111111111100001111111110000";
  • 获取 s 中最长 1s 子串计数的有效方法是什么？( 11)
  • 获取 s 中最长 0s 子串计数的有效方法是什么？( 10)

我很欣赏这个问题会从算法的角度来回答。

4

3 回答 3

0

我认为最直接的方法是遍历位串，同时记录所有0和所有1子串的最大长度。正如其他人所建议的那样，这很O (n)复杂。

如果您负担得起某种数据并行计算，您可能希望查看此处解释的并行模式。具体来说，看看并行归约。O (log n)我认为如果你能负担得起其中一种方法，这个问题可以及时解决。

我正在尝试为这个问题考虑并行减少：

  1. 在减少的第一级，每个线程将处理 8 位字符串块（取决于您拥有的线程数和字符串的长度）并生成位字符串的摘要，例如：0 -> x, 1 -> y, 0 -> z, ....

  2. 在下一个级别，每个线程会将这些摘要中的两个合并为一个，在此阶段将执行任何可能的连接（基本上，如果上一个摘要以0( 1) 结尾，下一个摘要以0( 1) 开头，那么最后一个条目并且两个摘要的第一个条目可以折叠成一个）。

  3. 在顶层只有一个结构，其中包含位串的整体摘要，您必须逐步找出最大的序列（但这次它们都是摘要形式，所以应该更快） . 或者，您可以让每个摘要结构跟踪大字符串0和1子字符串，这样就无需遍历最终结构。

我想这种方法只在非常有限的范围内有意义，但因为你似乎非常热衷于变得比O (n)......

于 2012-11-21T11:53:14.863 回答
0

好的，这是我想出的一种解决方案，我不确定这是否没有错误。如果您发现错误或建议更好的方法，请纠正我。如果您同意此解决方案，请投票。谢谢！

#include <iostream>

using namespace std;

int main(){

    int s[] = {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0};
    int length = sizeof(s) / sizeof(s[0]);

    int one_start = 0;
    int one_n = 0;
    int max_one_n = 0;

    int zero_start = 0;
    int zero_n = 0;
    int max_zero_n = 0;

    for(int i=0; i<length; i++){
        // Calculate 1s
        if(one_start==0 && s[i]==1){
            one_start = 1;
            one_n++;
        }
        else if(one_start==1 && s[i]==1){
            one_n++;
        }
        else if(one_start==1 && s[i]==0){
            one_start = 0;
            if(one_n > max_one_n){
                max_one_n = one_n;
            }
            one_n = 0;      // Reset 
        }

        // Calculate 0s
        if(zero_start==0 && s[i]==0){
            zero_start = 1;
            zero_n++;
        }
        else if(zero_start==1 && s[i]==0){
            zero_n++;
        }
        else if(one_start==1 && s[i]==1){
            zero_start = 0;
            if(zero_n > max_zero_n){
                max_zero_n = zero_n;
            }
            zero_n = 0;     // Reset 
        }
    }

    if(one_n > max_one_n){
        max_one_n = one_n;
    }
    if(zero_n > max_zero_n){
        max_zero_n = zero_n;
    }

    cout << "max_one_n: " << max_one_n << endl;
    cout << "max_zero_n: " << max_zero_n << endl;

    return 0;
}
于 2012-11-21T17:18:20.823 回答
0

最坏的情况总是 O(n)，你总能找到强制算法检查每一位的输入。

但是你可能会得到比这更好的平均值（更简单的是，如果你只扫描 0 或 1，而不是两者），因为你可以跳过当前找到的最长序列的长度并向后扫描。至少这会减少 O(n) 的常数因子，但至少在随机输入的情况下，更多的项目也意味着更长的序列，因此越长越长。但是与 O(n) 的差异不会太大...

于 2012-11-21T18:14:11.540 回答