Java 字串分割、替換與排序綜合實戰 (OJ 風格題目解析)

解析一道典型演算法題：將輸入字串以 '5' 為分隔符切割，過濾空段，將各段視為**非負整數** (忽略前導零，全零視為 0)、**按降序排序**、以單一空格連接輸出。附帶完整 Java 實作與 JUnit 測試。

題目需求精煉

• 輸入：僅含數字 0-9 的字串，長度 1~1000。
• 分隔符：字元 '5'。
• 每段轉整數：前導零忽略，"000" → 0，超過 100,000,000 視為非法。
• 輸出：降序排序，空格分隔，首尾無空格。非法輸入回傳 -1。

核心實作 (單一方法)

import java.util.*;

public class NumberSorter {
    /** @return 0 成功, -1 失敗 */
    public static int sortByFiveSplit(String input, StringBuilder output) {
        if (input == null || input.length() == 0 || input.length() > 1000) return -1;

        String[] parts = input.split("5"); // 正則分割，"5" 非特殊字元無需轉義
        List<Integer> nums = new ArrayList<>();

        for (String part : parts) {
            if (part.isEmpty()) continue; // 連續 5 產生空段
            try {
                int val = Integer.parseInt(part); // 自動處理前導零
                if (val > 100_000_000) return -1;
                nums.add(val);
            } catch (NumberFormatException e) {
                return -1; // 非數字字元 (題目保證不會發生)
            }
        }

        if (nums.isEmpty()) return -1; // 全為 5

        // 降序排序
        nums.sort(Comparator.reverseOrder());

        // 輸出
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0) output.append(' ');
            output.append(nums.get(i));
        }
        return 0;
    }

    // 主程式測試
    public static void main(String[] args) {
        String[] tests = {
            "1234543215555",           // 正常
            "12345432155556436567",    // 多段
            "123454321555000000000056436567", // 含全零段
            "1234543215510000000000000001556436567" // 超過上限
        };
        for (String t : tests) {
            StringBuilder out = new StringBuilder();
            int rc = sortByFiveSplit(t, out);
            System.out.printf("rc=%d, out=%s%n", rc, out);
        }
    }
}

測試結果

rc=0, out=4321 1234
rc=0, out=6436 4321 1234 67
rc=0, out=6436 4321 1234 67 0
rc=-1, out=

JUnit 4 測試案例

import org.junit.Test;
import static org.junit.Assert.*;

public class NumberSorterTest {
    @Test public void testBasic() {
        StringBuilder out = new StringBuilder();
        assertEquals(0, NumberSorter.sortByFiveSplit("1234543215555", out));
        assertEquals("4321 1234", out.toString());
    }
    @Test public void testMultiSegment() {
        StringBuilder out = new StringBuilder();
        assertEquals(0, NumberSorter.sortByFiveSplit("12345432155556436567", out));
        assertEquals("6436 4321 1234 67", out.toString());
    }
    @Test public void testLeadingZeros() {
        StringBuilder out = new StringBuilder();
        assertEquals(0, NumberSorter.sortByFiveSplit("123454321555000000000056436567", out));
        assertEquals("6436 4321 1234 67 0", out.toString());
    }
    @Test public void testOverflow() {
        StringBuilder out = new StringBuilder();
        assertEquals(-1, NumberSorter.sortByFiveSplit("1234543215510000000000000001556436567", out));
    }
    @Test public void testAllFives() {
        StringBuilder out = new StringBuilder();
        assertEquals(-1, NumberSorter.sortByFiveSplit("55555", out));
    }
}

效能與替代方案

• split("5") 建立陣列 + 列表，記憶體 O(n)。極大輸入可用 StringTokenizer 或手寫掃描 O(1) 額外空間。
• 排序 O(m log m) (m 為段數)。若範圍固定 (≤1億) 可用計數排序 O(m + MAX)，但空間大。
• StringBuilder 輸出避免字串拼接產生大量暫存物件。