#hihocoder#1039文字消去

自分のコード能力をまとめると、スラグです.仕事を探して、各道の大神が歌を歌って猛進しているのを見て、自分は...そのため痛々しく考えて、困って学んで、悔い改めて自分を改めて、最初から来たことがあります...
タイトル:#1039:文字消去
Hiちゃんは最近文字消去ゲームをしています.大文字「AB C」のみを含む文字列sを与え、消去プロセスは以下のように行われる.

sが1を超える長さの同じアルファベットからなるサブストリングを含む場合、これらのサブストリングは同時に除去され、残りのサブストリングは新しい文字列にスペルされる.例えば、「ABCCBCCC AA」の「CC」、「CCC」と「AA」は同時に消去され、残りの「AB」と「B」は新しい文字列「ABB」につづられる.

上記の消去は、新しい文字列が隣接する同じ文字を含まないまで、1回1回繰り返されます.例えば、「ABCCBCCCAA」は、1ラウンドの消去により「ABB」を得る、さらに1ラウンドの消去により「A」

を得る.
ゲームの各関門のHiは文字列sに直面します.消去開始前のHiは、sの任意の位置(最初の文字の前、最後の文字の後、および隣接する2つの文字の間)に任意の1つの文字(‘A’,’B’または’C’)を挿入して文字列tを得る機会がある.t一連の消去後、Hiちゃんの得点は消去された文字の総数である.
最高得点を得るには、Hiさんが文字を挿入する方法を計算してください.
Input入力の最初の行は、テストデータの数を表す整数T(1<=T<=100)である.その後、T行の各行には「A」B」C’からなる文字列sが1つずつあり、長さは100を超えない.Outputは,各行に入力された文字列に対して,小Hiで最も高い点数を出力する.
Hint第1グループデータ:“ABCBCCCAA”の第2文字の後に‘C’を挿入して“ABCCBCCCAA”を得て、除去して“A”を得て、全部で9文字(挿入した‘C’を含む)を除去します.第2グループのデータ:“AAA”挿入’A’得“AAAA”、消去後得“”、全部で4文字を消去する.第3グループのデータ:文字を挿入して得た“AABC”、“ABBC”それとも“ABCC”はすべて最大2文字を消去する.
Sample Input
3 ABCBCCCAA AAA ABC
Sample Output
9 4 2
この問題は比較的簡単で直接的で,主に文字の操作に対して,元の文字列の各位置(共n+1位置,仮定文字列長n)に「A」,「B」,「C」を順次遍歴する必要がある場合を考察し,合計3*(n+1)の場合がある.次に、各状況の文字列を処理します.隣接する文字が等しいかどうかを順に判断し、カウント変数を設定します.等しい場合、最初は、元の文字列の対応する位置を「D」などの出現しない文字にリセットし、次に除去し、新しく生成された文字列を再帰的に処理することを考えていた.新しい文字列の長さが1の場合、または新しい文字列の長さに変化がない場合は、再帰を停止します.

import java.util.Scanner;

public class Main {

    private static void earse(String input) {
        int res = 0;
        int max = 0;
        char[] cArray = new char[input.length() + 1];
        char[] change = {'A', 'B', 'C'};
        for (int k = 0; k < 3; k++) {
            for (int i = 0; i < input.length() + 1; i++) {
                cArray[i] = change[k];
                for (int j = 0; j < i; j++) {
                    cArray[j] = input.charAt(j);
                }
                for (int j = i + 1; j < input.length() + 1; j++) {
                    cArray[j] = input.charAt(j-1);
                }
                res = earse(cArray);
                if (res > max) {
                    max = res;
                }
            }
        }
        System.out.println(max);
    }

    private static int earse(char[] cArray) {
        if (cArray.length <= 1) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < cArray.length; i++) {
            int cnt = 1;
            while (i < cArray.length - 1 && cArray[i+1] == cArray[i]) {
                i++;
                cnt++;
            }
            res += (cnt != 1 ? cnt : 0);
            if (cnt != 1) {
                for (int j = i + 1 - cnt; j <= i; j++) {
                    cArray[j] = 'D';
                }
            }
        }
        if (String.valueOf(cArray).matches(".*D.*") && cArray.length - res >= 2) {
            char[] nChar = new char[cArray.length - res];
            int j = 0;
            for (int i = 0; i < cArray.length; i++) {
                if (cArray[i] != 'D') {
                    nChar[j++] = cArray[i];
                }
            }
            return res + earse(nChar);
        } else {
            return res;
        }
    }

    public static void main(String[] args) {
        Scanner sin = new Scanner(System.in);
        int N = sin.nextInt(); 
        while(N-- != 0){
            String P = sin.next();
            earse(P);
        }
    }

}

文字に対する操作があるため,最初はchar配列を用い,操作が煩雑であったが,後でStringクラスを用いることを考慮し,タイトルにStringの接合が多いためStringbuilderクラスを用いた.本来StringBuilderの操作はchar配列より少し遅いが、char配列は何か事前にサイズを定義する必要があるため、途中で「D」の操作について一歩多くなり、全体の速度はかえっていっぱいになった.

import java.util.Scanner;

public class Main {
    private static void earse(StringBuilder input) {
        int res = 0;
        int max = 0;
        StringBuilder cArray = new StringBuilder(); 
        char[] change = {'A', 'B', 'C'};
        for (int k = 0; k < 3; k++) {
            for (int i = 0; i < input.length() + 1; i++) {
                if (i == 0) {
                    cArray.append(change[k]).append(input);
                } else if (i == input.length()) {
                    cArray.append(input).append(change[k]);
                } else {
                    cArray.append(input.subSequence(0, i))
                    .append(change[k]).
                    append(input.subSequence(i, input.length()));
                }
                res = earse2(cArray);
                if (res > max) {
                    max = res;
                }
                cArray.delete(0, cArray.length());
            }
        }
        System.out.println(max);
    }

    private static int earse2(StringBuilder cArray) {
        if (cArray.length() <= 1) {
            return 0;
        }
        int res = 0;
        StringBuilder nChar = new StringBuilder();
        for (int i = 0; i < cArray.length(); i++) {
            int cnt = 1;
            while (i < cArray.length() - 1 && cArray.charAt(i+1) == cArray.charAt(i)) {
                i++;
                cnt++;
            }
            if (cnt == 1) {
                //       ，      ，      
                nChar.append(cArray.charAt(i)); 
            } else {
                res += cnt;   
            }
        }
        if (cArray.length() - nChar.length() > 0 
            && nChar.length() >= 2) {
            return res + earse2(nChar);
        } else {
            return res;
        }
    }

    public static void main(String[] args) {
        Scanner sin = new Scanner(System.in);
        int N = sin.nextInt(); 
        while(N-- != 0){
            String P = sin.next();
            earse(new StringBuilder(P));
        }
    }
}

微末道行、しばらくこのようにして、更に多く自分のコードを修正する时間があります.しばらくして振り返って自分を見て、自分がどうしてこんなにクズになったのかと思って、表面はそれは功力が今より良いです...
Javaの知識点:1.StringクラスとStringBuilderクラスの違い

Stringオブジェクトに対する変更は元のオブジェクトには影響しません.関連する変更操作は新しいオブジェクト

を生成します.

String str="hello world"とString str=new String("hello world")の違い(新しいオブジェクトが生成されるかどうか)

String、StringBufferおよびStringBuilderの違い(新しい文字列が生成されるかどうか、スレッドセキュリティ)

2.char配列とStringクラスの違い