1

たとえば、 と で構成される特定の文字列が1sあり0sます。

s = "00000000001111111111100001111111110000";
  • s で最長の 1 部分文字列の数を取得する効率的な方法は何ですか? ( 11)
  • s で最長の 0 部分文字列の数を取得する効率的な方法は何ですか? ( 10)

アルゴリズムの観点から質問に答えていただければ幸いです。

4

3 に答える 3

0

OK、これが私が思いついた解決策の1つですが、これにバグがないかどうかはわかりません。バグを発見した場合、またはそれを行うためのより良い方法を提案した場合は、私を訂正してください。この解決策に同意する場合は、投票してください。ありがとう！

#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 に答える