Go Javaアルゴリズムの出現シーケンスを実装する方法

出現シーケンス

正の整数 n を指定すると、出現シーケンスの n 番目の項目を出力します。

「出現シーケンス」は、1 から始まる整数のシーケンスであり、シーケンス内の各項目は前の項目の説明です。

これは、再帰式で定義された一連の数値文字列と考えることができます:

countAndSay(1) = "1"

countAndSay(n)これは countAndSay(n-1) の説明であり、別の数値文字列に変換されます。

最初の 5 つの項目は次のとおりです:

• 1, 1 —— 最初の項目は番号 1

• 2, 11 - 前の項目を説明します。この番号は 1、つまり「1」で、「11」として記録されます。

• 3, 21 - を説明します。前の項目の項目、この番号は 11、つまり「2 つの 1」、「21」として記録されます

• 4, 1211 - 前の項目の説明、この番号は 21、つまり「」 one 2" One 1"、「1211」

• ##5、111221 として記録 - 前の項目を説明します。この番号は 1211、つまり「one 1、one 2、two 1」です。 、「111221」として記録されます

方法 1: トラバーサル生成 (Java)

いわゆる「出現シーケンス」は、実際には同じものの連続数を数えているだけです。文字列内の文字数。

質問にある再帰式で定義される数値列列は次のとおりです:

countAndSay(1) = "1";

countAndSay(n ) countAndSay(n-1) の記述を別の数値列に変換します。

countAndSay(i) を表す文字列 S_{i} を定義します。S_{n} が必要な場合は、まず S_{n-1} を見つけてから、上記の説明に従う必要があります。メソッドの生成。つまり、文字列 S_{n-1} 内の連続する同一文字の最大数を左から右にスキャンし、統計的な文字数を数値文字列に変換し、対応する文字を連結します。

class Solution {
    public String countAndSay(int n) {
        String str = "1";
        for (int i = 2; i <= n; ++i) {
            StringBuilder sb = new StringBuilder();
            int start = 0;
            int pos = 0;
            while (pos < str.length()) {
                while (pos < str.length() && str.charAt(pos) == str.charAt(start)) {
                    pos++;
                }
                sb.append(Integer.toString(pos - start)).append(str.charAt(start));
                start = pos;
            }
            str = sb.toString();
        }
        return str;
    }
}

N は指定された正の整数、M は生成される文字列の最大長です

時間計算量: O(N * M)

空間計算量:O(M )

方法 2: 再帰的 (Go)

具体的な方法の分析は上に記載されています

毎回取得されるデータは上記から取得されるため、結果は 1 回だけですが、したがって、最後の結果が得られたと仮定して、操作を続行できます。これは再帰を使用します。

func countAndSay(n int) string {
    if n == 1 {
        return "1"
    }
    s := countAndSay(n - 1)
    i, res := 0, ""
    length := len(s)
    for j := 0; j < length; j++ {
        if s[j] != s[i] {
            res += strconv.Itoa(j-i) + string(s[i])
            i = j
        }
    }
    res += strconv.Itoa(length-i) + string(s[i])
    return res
}

N は指定された正の整数、M は生成される文字列の最大長です

時間計算量: O(N * M)

空間計算量:O(M )

以上がGo Javaアルゴリズムの出現シーケンスを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。