0

私は単語の正規形を作ることに行き詰まっています（単語の正規形には元の単語と同じ文字が含まれていますが、ソートされた順序になっています。たとえば、「コンピュータ」の正規形は「cemoprtu」です（アルファベット順を考慮してください）、 「プログラム」のそれは「agmoprr」です。）

次のコードを使用して、mergeSort を使用して単語の文字を並べ替えます。それでも、標準的な形式ではなく、元の単語が表示されるだけです。誰かが私のコードの何が問題なのか教えてもらえますか?

public static String canonicalForm(String word) {
    char[] string = new char[word.length()];
    for (int i = 0; i < word.length(); i ++) {
        string[i] = word.charAt(i);
    }
    mergeSort(string);
    String result = "";
    for (char ch: string) {
        result += ch;
    }
    System.out.println(result);
}

public static void mergeSort(char[] string) {
    if (string.length > 1) {
        char[] left = Arrays.copyOfRange(string, 0, string.length/2);
        char[] right = Arrays.copyOfRange(string, string.length/2, string.length);
        mergeSort(left);
        mergeSort(right);
        merge(string, left, right);
    }
}

public static void merge(char[] string, char[] left, char[] right) {
    int i1 = 0;
    int i2 = 0;
    for (int i = 0; i < string.length; i ++) {
        if (i1 < left.length) {
            if (left[i1] - right[i2] <= 0) {
                string[i] = left[i1];
                i1 ++;
            }
        } else if (i2 >= right.length) {
            string[i] = left[i1];
            i1 ++;
        } else {
            string[i] = right[i2];
            i2 ++;
        }
    }
}
}
4

2 に答える 2

3

欠陥は、 left[i1] - right[i2] > 0の場合、マージが右側の部分からシンボルをコピーしないことです。

これは機能します：

public static void merge(char[] string, char[] left, char[] right) {
    int i1 = 0;
    int i2 = 0;
    for (int i = 0; i < string.length; i++) {
        if (i1 < left.length && i2 < right.length) {
            if (left[i1] - right[i2] <= 0) {
                string[i] = left[i1];
                i1++;
            } else {
                string[i] = right[i2];
                i2++;
            }
        } else if (i2 >= right.length) {
            string[i] = left[i1];
            i1++;
        } else {
            string[i] = right[i2];
            i2++;
        }
    }
}

次の 3 つのケースがあります。

  1. 両方のパーツで使用できるシンボルがあります。値が最も小さいものを 1 つ取ります。
  2. 左部分のみに使用できる記号があります。それらをコピーします。
  3. 右側のみに使用できる記号があります。それらをコピーします。
于 2014-04-15T09:09:35.157 に答える
2

なぜあなたが車輪を再発明しているのかはわかりませんが、これはソート、文字列連結などのカスタム実装なしで書くことができます.

public static String canonicalForm(final String word) {
    final char[] string = word.toCharArray();
    Arrays.sort(string);
    final String result = new String(string);
    System.out.println(result);
    return result;
}
于 2014-04-15T09:14:57.417 に答える