問題描述

小U手中有兩個數字 a 和 b。第一個數字是一個任意的正整數，而第二個數字是一個非負整數。她的任務是將第二個數字 b 插入到第一個數字 a 的某個位置，以形成一個最大的可能數字。

你需要幫助小U找到這個插入位置，輸出插入后的最大結果。

測試樣例

樣例1：

輸入：a = 76543, b = 4
輸出：765443

樣例2：

輸入：a = 1, b = 0
輸出：10

樣例3：

輸入：a = 44, b = 5
輸出：544

樣例4：

輸入：a = 666, b = 6
輸出：6666

解題思路

這道題目綜合運用了字符串操作和貪心算法知識，是一道典型的字符串處理問題。題目要求將數字 b 插入到數字 a 的某個位置，以形成一個最大的可能數字。核心信息是找到一個插入位置，使得插入后的數字最大。我們可以通過遍歷 a 的每一位，嘗試將 b 插入到每一個可能的位置，并比較插入后的結果，選擇最大的那個。

解題過程：

1. 字符串轉換：將數字 a 和 b 轉換為字符串形式，便于進行插入操作。
2. 遍歷插入位置：遍歷 a 的每一位，嘗試將 b 插入到每一個可能的位置。
3. 生成新數字：對于每一個插入位置，生成一個新的數字，并將其轉換為整數形式。
4. 比較結果：比較新生成的數字與當前最大值，更新最大值。
5. 返回結果：遍歷結束后，返回最大值。

時間復雜度：O(n)，其中 n 是數字 a 的長度。我們需要遍歷 a 的每一位，嘗試插入 b，并生成新的數字。
空間復雜度：O(1)，我們只使用了常數級別的額外空間來存儲中間結果。

代碼

def solution(a: int, b: int) -> int:# 將數字 a 和 b 轉換為字符串str_a = str(a)str_b = str(b)# 初始化最大結果為插入到最前面的情況max_result = int(str_b + str_a)# 遍歷字符串 a 的每一個位置for i in range(len(str_a) + 1):# 嘗試將 str_b 插入到位置 inew_str = str_a[:i] + str_b + str_a[i:]# 將新字符串轉換為整數new_num = int(new_str)# 比較并更新最大結果if new_num > max_result:max_result = new_numreturn max_resultif __name__ == '__main__':print(solution(76543, 4) == 765443)print(solution(1, 0) == 10)print(solution(44, 5) == 544)print(solution(666, 6) == 6666)

法2：

def solution(a:int, b:int)->int:a = str(a)b = str(b)maxVal = 0for i in range(len(a) + 1):val = int(a[:i] + b + a[i:])if val > maxVal:maxVal = val return maxValif __name__ == '__main__':print(solution(a = 76543, b = 4) == 765443)print(solution(a = 1, b = 0) == 10)print(solution(a = 44, b = 5) == 544)print(solution(a = 666, b = 6) == 6666)