【MarsCode】每日一题 （字符串）之 小U的数字插入问题

小U的数字插入问题

1.问题描述

小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

2.思路与题解

1. 理解问题：我们需要将数字 b 插入到数字 a 的某个位置，使得插入后的数字最大。

2. 数据结构选择：将数字 a 和 b 转换为字符串，方便递归操作。

3. 算法步骤

   ：

   • 将数字 a 和 b 转换为字符串。
   • 使用递归函数遍历字符串 a，尝试在每个位置插入 b，并比较结果。
   • 返回最大结果。

2.4代码框架

Java

▼
java
复制代码
public class Main {
    public static int solution(int a, int b) {
        // write code here
        String strA= Integer.toString(a);
        // 将数字 b 转换为字符串
        String strB = Integer.toString(b);
        
        // 初始化最大结果为插入到最前面的情况
        String maxResult = strB + strA;
        
        // 遍历 strA 的每个位置，尝试插入 strB
        for (int i = 0; i <= strA.length(); i++) {
            // 构建插入后的字符串
            String candidate = strA.substring(0, i) + strB + strA.substring(i);
            
            // 比较并更新最大结果
            if (candidate.compareTo(maxResult) > 0) {
                maxResult = candidate;
            }
        }
        
        // 将最大结果转换回整数并返回
        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);
    }
}

C++

▼
c++
复制代码
#include <iostream>
#include <string>
#include <algorithm>

int solution(int a, int b) {
    // 将数字 a 转换为字符串
    std::string strA = std::to_string(a);
    // 将数字 b 转换为字符串
    std::string strB = std::to_string(b);
    
    // 初始化最大结果为插入到最前面的情况
    std::string maxResult = strB + strA;
    
    // 遍历 strA 的每个位置，尝试插入 strB
    for (int i = 0; i <= strA.length(); i++) {
        // 构建插入后的字符串
        std::string candidate = strA.substr(0, i) + strB + strA.substr(i);
        
        // 比较并更新最大结果
        if (candidate > maxResult) {
            maxResult = candidate;
        }
    }
    
    // 将最大结果转换回整数并返回
    return std::stoi(maxResult);
}

int main() {
    std::cout << (solution(76543, 4) == 765443) << std::endl;
    std::cout << (solution(1, 0) == 10) << std::endl;
    std::cout << (solution(44, 5) == 544) << std::endl;
    std::cout << (solution(666, 6) == 6666) << std::endl;
    return 0;
}

Python

▼
python
复制代码
def solution(a, b):
    # 将数字 a 转换为字符串
    strA = str(a)
    # 将数字 b 转换为字符串
    strB = str(b)
    
    # 初始化最大结果为插入到最前面的情况
    maxResult = strB + strA
    
    # 遍历 strA 的每个位置，尝试插入 strB
    for i in range(len(strA) + 1):
        # 构建插入后的字符串
        candidate = strA[:i] + strB + strA[i:]
        
        # 比较并更新最大结果
        if candidate > maxResult:
            maxResult = candidate
    
    # 将最大结果转换回整数并返回
    return int(maxResult)

if __name__ == "__main__":
    print(solution(76543, 4) == 765443)
    print(solution(1, 0) == 10)
    print(solution(44, 5) == 544)
    print(solution(666, 6) == 6666)

Golang

▼
go
复制代码
package main

import (
    "fmt"
    "strconv"
)

func solution(a, b int) int {
    // 将数字 a 转换为字符串
    strA := strconv.Itoa(a)
    // 将数字 b 转换为字符串
    strB := strconv.Itoa(b)
    
    // 初始化最大结果为插入到最前面的情况
    maxResult := strB + strA
    
    // 遍历 strA 的每个位置，尝试插入 strB
    for i := 0; i <= len(strA); i++ {
        // 构建插入后的字符串
        candidate := strA[:i] + strB + strA[i:]
        
        // 比较并更新最大结果
        if candidate > maxResult {
            maxResult = candidate
        }
    }
    
    // 将最大结果转换回整数并返回
    result, _ := strconv.Atoi(maxResult)
    return result
}

func main() {
    fmt.Println(solution(76543, 4) == 765443)
    fmt.Println(solution(1, 0) == 10)
    fmt.Println(solution(44, 5) == 544)
    fmt.Println(solution(666, 6) == 6666)
}

2.5一些疑难的代码解释

1. 字符串转换：将 a 和 b 转换为字符串，方便递归操作。
2. 递归函数：定义递归函数 findMaxInsertion，尝试在每个位置插入 b，并比较结果。
3. 递归终止条件：当 index 超过 strA 的长度时，返回当前结果。
4. 比较结果：比较当前插入结果和下一个位置的插入结果，返回较大的一个。

3.欢迎大佬们关注或莅临本渣的一些个人website

gitee： https://gitee.com/xiao-chenago github：https://github.com/cool-icu0 语雀：https://www.yuque.com/icu0 csdn：https://cool-icu.blog.csdn.net/