Go Java 알고리즘의 출현 순서를 구현하는 방법

Appearance 순서

양의 정수 n이 주어지면, 모양 순서의 n번째 항목을 출력합니다.

"외모 순서"는 숫자 1부터 시작하는 정수의 순서이며, 순서의 각 항목은 이전 항목에 대한 설명입니다.

재귀 공식으로 정의된 일련의 숫자 문자열로 생각할 수 있습니다.

countAndSay(1) = "1"

countAndSay(n)은 countAndSay(n-1)에 대한 설명입니다. 다른 숫자 문자열로 변환됩니다.

처음 5개 항목은 다음과 같습니다.

• 1, 1 —— 첫 번째 항목은 1

• 2, 11 —— 이는 "a 1", "11"

• 3, 21 - 이전 항목을 설명하면 이 숫자는 11이며 "two 1"이며 "21"

• 4, 1211로 기록됩니다. 설명 이전 항목에 대한 설명은 번호 21, 즉 "a 2 + a 1", 기록된 "1211"

• 5, 111221 - 이전 항목 설명, 번호는 1211, 즉 "a 1 + a 2 + Two 1 ", "111221"로 기록됨

방법 1: 순회 생성(Java)

소위 "표시 순서"는 실제로 문자열에서 연속된 동일한 문자의 수를 계산하는 것입니다.

질문에 주어진 재귀 공식에 의해 정의된 숫자 문자열 시퀀스는 다음과 같습니다.

countAndSay(1) = "1";

countAndSay(n)은 countAndSay(n-1)에 대한 설명입니다. 다른 A 숫자 문자열로 변환됩니다.

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)

구체적인 방법 분석은 위에서 설명했습니다

매번 얻은 데이터는 이전 결과에서 나온 것이기 때문에 마지막 결과를 얻었다고 가정하고 계산을 진행할 수 있습니다. 이것은 재귀를 사용합니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!