問題描述

---

問題分析

問題的核心是找到將數字 b 插入到數字 a 的某個位置后，使形成的數字盡可能大。需要仔細分析以下幾個要點：

1. 分析數字的特性

• 輸入的兩個數字：
  • a 是一個正整數（例如 76543）。
  • b 是一個非負整數（例如 4）。
• 目標：
  將 b 插入 a 的某個位置后，獲得最大的數字。

2. 數字的插入方式

• 數字插入可以通過 將 b 放在 a 的每兩個相鄰數字之間 來實現。
  • 例如，對于 a = 76543 和 b = 4：
    • 插入到開頭：476543
    • 插入到 7 和 6 之間：746543
    • 插入到 6 和 5 之間：765443
    • 插入到 5 和 4 之間：765453
    • 插入到末尾：765434
  • 按位置遍歷所有可能的插入結果，找到其中最大的數字。

3. 需要考慮的情況

Case 1: b 插入的最佳位置

插入后的數字大小取決于：

• b 是否比當前數字大（例如 b = 4 和 a = 76543，將 4 插在比它小的數字前可能獲得最大值）。
• 必須比較插入前后數字的大小，確保選擇最大的。

Case 2: 邊界條件

• a 的長度：a 可以是任意正整數，單個數字（如 1）、多位數字（如 54321）都需要正確處理。
• b = 0 的特殊情況：
  • 插入 0 時，由于 0 的數值較小，可能需要插在數字的末尾（除非插在較小的數字后可以形成更大的結果）。
  • 例如 a = 1, b = 0，正確結果為 10。

Case 3: 插入到字符串的末尾

插入的位置還包括 末尾，即需要遍歷的插入點包括從第 0 位到最后一位（length + 1 次嘗試）。

4. 如何實現

1. 將數字轉換為字符串：便于操作每個插入點。
2. 生成每個插入結果：遍歷可能的插入位置，將 b 插入到 a 的字符串中，形成一個新的字符串。
3. 比較最大值：在遍歷過程中，比較所有生成的結果，保留其中的最大值。
4. 返回結果：最后輸出最大值。

5. 示例分析

示例 1:

輸入：a = 76543, b = 4

插入操作：

• 插入到第 0 位：476543
• 插入到第 1 位：746543
• 插入到第 2 位：765443 (最大)
• 插入到第 3 位：765453
• 插入到末尾：765434

最大結果：765443

示例 2:

輸入：a = 1, b = 0

插入操作：

• 插入到第 0 位：01（等價于 10）
• 插入到末尾：10

最大結果：10

6. 問題解決的關鍵

• 明確數字插入的每一種可能性。
• 在每個可能性中，選擇能構成最大值的結果。
• 注意邊界條件（例如 b = 0，或 a 為單個數字時的處理）。

---

參考代碼（Java）

public class Main {public static int solution(int a, int b) {// 將整數a轉換為字符串以便操作String aStr = String.valueOf(a);String bStr = String.valueOf(b);// 初始化最大結果String maxResult = "";// 遍歷a的每個插入位置for (int i = 0; i <= aStr.length(); i++) {// 在第i位置插入bString current = aStr.substring(0, i) + bStr + aStr.substring(i);// 更新最大值if (maxResult.isEmpty() || Integer.parseInt(current) > Integer.parseInt(maxResult)) {maxResult = current;}}// 返回結果轉換為整數return Integer.parseInt(maxResult);}public static void main(String[] args) {System.out.println(solution(76543, 4) == 765443); System.out.println(solution(1, 0) == 10);         System.out.println(solution(44, 5) == 544);       System.out.println(solution(666, 6) == 6666);     }
}

代碼分析

solution 方法分析

1. 輸入處理

String aStr = String.valueOf(a);
String bStr = String.valueOf(b);

• 目的：將輸入的整數 a 和 b 轉換為字符串。
• 原因：便于操作字符串中的每一位數字，同時允許插入操作變得簡單。
• 例如：a = 76543 被轉換為 "76543"，b = 4 被轉換為 "4"。

2. 最大值初始化

String maxResult = "";

• 初始化最大結果為空字符串。
• 之后通過比較插入結果，不斷更新 maxResult。

3. 遍歷插入位置

for (int i = 0; i <= aStr.length(); i++) {String current = aStr.substring(0, i) + bStr + aStr.substring(i);...
}

• 遍歷范圍：從 i = 0 到 i = aStr.length()，共 length + 1 次循環。
  • 例如，對于 "76543" 和 "4"：
    • 插入到第 0 位（開頭）：476543
    • 插入到第 1 位：746543
    • 插入到第 2 位：765443
    • 插入到第 3 位：765453
    • 插入到末尾：765434
• 字符串操作：
  • aStr.substring(0, i)：獲取從起始位置到第 i 位之前的字符串。
  • bStr：將 b 插入當前位置。
  • aStr.substring(i)：獲取從第 i 位到字符串末尾的內容。
  • 最終拼接生成插入后的新字符串。

4. 比較最大值

if (maxResult.isEmpty() || Integer.parseInt(current) > Integer.parseInt(maxResult)) {maxResult = current;
}

• maxResult.isEmpty()：初次循環時，直接將第一個結果作為初始值。
• Integer.parseInt：將字符串 current 轉換為整數，便于數值大小比較。
• 更新最大值：如果當前插入結果比之前的最大值大，則更新 maxResult。

5. 返回結果

return Integer.parseInt(maxResult);

• 最后將字符串形式的最大值 maxResult 轉換為整數并返回。

代碼性能分析

1. 時間復雜度：
   • 遍歷插入點需要 O(n) 次操作（n 是 a 的位數）。
   • 每次插入后比較大小需要將字符串轉換為整數（O(k)，k 為插入后字符串的位數）。
   • 總時間復雜度：O(n * k)。
2. 空間復雜度：
   • aStr 和 bStr 占用 O(n + 1) 的空間（n 為 a 的長度，1 為 b 的長度）。
   • 中間字符串 current 也占用 O(n + 1) 的空間。
   • 總空間復雜度：O(n)。