问题描述

---

问题分析

问题的核心是找到将数字 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）

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位置插入b
            String 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. 输入处理

java">String aStr = String.valueOf(a);
String bStr = String.valueOf(b);

• 目的：将输入的整数 a 和 b 转换为字符串。
• 原因：便于操作字符串中的每一位数字，同时允许插入操作变得简单。
• 例如：a = 76543 被转换为 "76543"，b = 4 被转换为 "4"。

2. 最大值初始化

java">String maxResult = "";

• 初始化最大结果为空字符串。
• 之后通过比较插入结果，不断更新 maxResult。

3. 遍历插入位置

java">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. 比较最大值

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

• maxResult.isEmpty()：初次循环时，直接将第一个结果作为初始值。
• Integer.parseInt：将字符串 current 转换为整数，便于数值大小比较。
• 更新最大值：如果当前插入结果比之前的最大值大，则更新 maxResult。

5. 返回结果

java">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)。