2

文字列が0と1のみで構成されている場合、10101
と言うと 、減少しない最長のサブシーケンスの長さを見つける方法は??
例えば、

文字列の場合、
10101

減少しない最長のサブシーケンスは

  • 111
  • 001
    なので、3を出力する必要があります

文字列
101001の場合

減少しない最長のサブシーケンスは

  • 0001

だからあなたは
これを見つける方法を4出力する必要がありますか？

制限が設けられている場合、これをどのように行うことができますか。制限間のシーケンス、
たとえば
101001
制限[3,6]
最長の非減少サブシーケンスは

  • 001
    なので、3を出力する必要があります

これはo（strlen）で達成できますか

4

3 に答える 3

1

これはで達成できますO(strlen)か？

はい。減少しないサブシーケンスは、次の3つの形式のいずれかになることに注意してください。

0........0 // Only zeros
1........1 // Only ones
0...01...1 // Some zeros followed by some ones

O(1)最初の2つの形式は、すべて0を数え、すべて1を数えることで簡単にチェックインできます。

最後の1つは少し難しいです。これまでに見たゼロのカウンターと、これまでに0...01...1発見した最も長いフォームの文字列の長さを維持しながら、文字列を調べる必要があります。文字列に表示される各ステップで1、3番目の形式の最長のサブシーケンスの長さは、ゼロの数に1を加えたもの、または0...01...1これまでに見た中で最も長いシーケンスに1を加えたものの大きい方になります。

Cでの上記のアプローチの実装は次のとおりです。

char *str = "10101001";
int longest0=0, longest1=0;
for (char *p = str ; *p ; p++) {
    if (*p == '0') {
        longest0++;
    } else { // *p must be 1
        longest1 = max(longest0, longest1)+1;
    }
}
printf("%d\n", max(longest0, longest1));

max次のように定義されます。

#define max( a, b ) ( ((a) > (b)) ? (a) : (b) )

これがideoneのデモへのリンクです。

于 2012-12-26T17:52:24.257 に答える
1

動的計画法を使用します。文字列を左から右に実行し、2つの変数を追跡します。

  • zero：0で終わる最長部分列の長さ
  • one：1で終わる最長部分列の長さ

0が表示された場合、これを0で終わるプレフィックスに追加できるため、を増やしzeroます。1が表示された場合は、0で終わるプレフィックスまたは1で終わるプレフィックスに追加できるため、one最も長いプレフィックスを設定します。C99の場合：

int max(int a, int b) {
  return a > b ? a : b;
}

int longest(char *string) {
  int zero = 0;
  int one = 0;
  for (; *string; ++string) {
    switch (*string) {
      case '0':
        ++zero;
        break;
      case '1':
        one = max(zero, one) + 1;
        break;
    }
  }
  return max(zero, one);
}
于 2012-12-26T17:58:25.413 に答える
0 
do {
    count++;
    if (array[i] < prev) {
        if (count > max)
            max = count;
        count = 0;
    }
    prev = array[i];
} while (++i < length);

シングルパス。1と0だけでなく、任意の数値でも機能します。

制限の場合-i開始番号に設定し、配列の長さの代わりに終了を使用します。

于 2012-12-26T18:07:56.203 に答える