题目来源于稀土掘金AI刷题——字节青训营

---

（易）计算从位置x到y的最少步数

问题描述
小F正在进行一个 AB 实验，需要从整数位置x移动到整数位置y。每一步可以将当前位置增加或减少，且每步的增加或减少的值必须是连续的整数（即每步的移动范围是上一步的-1，+0或+1）。首末两步的步长必须是1。求从x到y的最少步数。
输入描述
输入包含两个整数x和y，表示起始位置和目标位置。
输出描述
输出从x到y所需的最小步数。
测试样例

样例1：
输入：$x_{p}osition=12,y_{p}osition=6$
输出：4

样例2：
输入：$x_{p}osition=34,y_{p}osition=45$
输出：6

样例3：
输入：$x_{p}osition=50,y_{p}osition=30$
输出：8

样例4：
输入：$x_{p}osition=0,y_{p}osition=0$
输出：0

解题思路
这个思路似乎不太一样，我们来看，题目有两个关键要求：一个是步数最少，一个是相邻两步之间只能是+1，-1，+0三种情况。
那我们以$$1、2、3、4、3、2、1$$为例,此时的距离是16；而$$1、2、3、4、5、4、3、2、1$$时，此时的距离是25；先得出一个小规律，这样的分布总距离是$n\ast n$(n是最中间的那个数)。
然后呢，我们假设目标距离是20，那是不是只要在第一个数列中间添加一个4，也就是：$$1、2、3、4、4、3、2、1$$，那么最少步数就是8。
那20和25之间还有一段距离，如果目标距离在这一段呢，我们可以在第三个数列的基础上继续添加，那就有疑问了：为什么不是第二个呢？这就涉及到第二个限制条件：相邻两步之间只能是+1，-1，+0，当你的这一组数列中出现5时，5的左右两侧至少各有1个4，符合限制的最短距离和就是25，超出了。所以呢，假设目标距离是23，那么也就是在第三个数组的基础上再插入一个3，也就是：$$1、2、3、4、4、3、3、2、1$$此时的最少步数是9。
此外，还有一种特殊情况：如果两个位置之间的距离是0，那么我们原本思路的对n进行微操似乎就不太合适，那我们就在方法最开始的位置填上一个判断条件，如果距离是0，那么直接返回0即可。

public class Main {
    public static int solution(int xPosition, int yPosition) {
        int len = Math.abs(yPosition-xPosition);
        if(len==0){
            return 0;
        }
        int n=0;
        do {
            n++;
        }while(n*n<=len);
        n--;
        if(len-n*n==0){
            return n+n-1;
        }else if(len-n*n<=n){
            return n*2;
        }else{
            return n*2+1;
        }
    }
    public static void main(String[] args) {
        // You can add more test cases here
        System.out.println(solution(12, 18) == 4);
        System.out.println(solution(34, 45) == 6);
        System.out.println(solution(50, 30) == 8);
        System.out.println(solution(50, 27) == 9);
        System.out.println(solution(50, 35) == 7);
    }
}

---

（易）环状DNA序列的最小表示法

问题描述
小C正在研究一种环状的 DNA 结构，它由四种碱基A、C、G、T构成。这种环状结构的特点是可以从任何位置开始读取序列，因此一个长度为 n 的碱基序列可以有 n 种不同的表示方式。小C的任务是从这些表示中找到字典序最小的序列，即该序列的“最小表示”。

例如：碱基序列 ATCA 从不同位置读取可能的表示有 ATCA, TCAA, CAAT, AATC，其中 AATC 是字典序最小的表示。

测试样例

样例1：
输入：dna_sequence = “ATCA”
输出：‘AATC’

样例2：
输入：dna_sequence = “CGAGTC”
输出：‘AGTCCG’

样例3：
输入：dna_sequence = “TTGAC”
输出：‘ACTTG’

解题思路：
什么是字典序呢？简单来说，就是一个字符的$ASCLL码$。
这道题的意思就是给你一个字符串，以字符串的不同位置作为开头，诶个比较不同字符串中的字符，直到返回字典序最小的那个字符串。以ATCA为例，它的可能序列一共有4种：$$ATCA$$$$TCAA$$$$CAAT$$$$AATC$$那么解题流程也就是比较四组字符串各自的第一个字符，得到$$ATCA$$$$AATC$$比较这两组的第二个字符，得到字典序最小的：$$AATC$$
但是呢，我们将思路用在计算机上，发现如果可能序列足够多的话，这样比较起来会非常冗杂，所以我们需要一个更简洁的思路：那么我们是不是可以尝试两个两个比较，字典序较小的与下一个字符串进行比较，然后再返回较小的，接着进行比较，当我们把所有字符开头的序列都比较过之后，就得到了最终的最小序列。
但是呢，稍微想一想，似乎这里也有一种特殊情况：如果字符串中的所有字符都是同一种字母组成的呢，此时我们原本的比较方法$compare$似乎就不太行了，那这一种我们也可以单拉出来作为一种情况讨论，如果测试字符串仅由一种字母构成，那我们直接返回原字符串。

import java.util.Arrays;

public class Main {
    public static String solution(String dna_sequence) {
        if(allSame(dna_sequence)){
            return dna_sequence;
        }
        int len = dna_sequence.length();
        String min_str = dna_sequence;
        for (int i = 1; i < len; i++) {
//            System.out.println(dna_sequence.substring(i)+dna_sequence.substring(0, i));
            min_str = compare(min_str, dna_sequence.substring(i)+dna_sequence.substring(0, i));
        }
        return min_str;
    }
    // 传入俩个等长的字符串,诶个字母比较谁的字典序更小，传出较小的那一位
    public static String compare(String str1, String str2) {
        for(int i=0;i<str1.length();i++){
            if(str1.charAt(i) < str2.charAt(i)){
                return str1;
            }else if(str1.charAt(i) > str2.charAt(i)){
                return str2;
            }else{
                continue;
            }
        }
        return "";
    }
    public static boolean allSame(String str){
        //判断该字符串中的所有字母都只是同一种字母
        for(int i=0;i<str.length()-1;i++){
            if(str.charAt(i) != str.charAt(i+1)){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        // You can add more test cases here
        System.out.println(solution("ATCA").equals("AATC"));
        System.out.println(solution("CGAGTC").equals("AGTCCG"));
        System.out.println(solution("TCATGGAGTGCTCCTGGAGGCTGAGTCCATCTCCAGTAG").equals("AGGCTGAGTCCATCTCCAGTAGTCATGGAGTGCTCCTGG"));
    }
}

---

（易）打点计时器的区间合并

问题描述
小明想发明一台打点计数器，这个计数器有这样的一个功能：

• 它可以接收一个递增的数据范围（形如[3, 9]），其中第一个数字代表起始，第二个数字代表结束
• 这个数据范围中包含几个数字，打点计数器就会打几个点
• 在传入的多组数据范围中，如果出现了范围的重复，机器则不会重复打点
  你可以帮助小明算一算，在不同的情况下，计数器会打出几个点么？

输入格式
一个二维数组
输出格式
一个整数，表达在输入是这个数组的情况下，计数器打出的点数
输入样例(1)
[ [1,4], [7, 10], [3, 5] ]
输出样例(1)
7
输入样例(2)
[ [1,2], [6, 10], [11, 15] ]
输出样例(2)
9
数据范围

• $数字范围[-10^9,10^9]$，$数组长度 < 2^{16} $

解题思路
这个就很简单啦，我们遍历每个区间，将出现的元素全部存入集合中（集合中元素不会重复），然后再统计元素的个数即可求解。

import java.util.Set;
import java.util.HashSet;

public class Main {
    public static int solution(int[][] inputArray) {
        // Please write your code here
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<inputArray.length;i++){
            for(int j=inputArray[i][0];j<inputArray[i][1];j++){
                set.add(j);
            }
        }
        return set.size();
    }

    public static void main(String[] args) {
        //  You can add more test cases here
        int[][] testArray1 = {{1, 4}, {7, 10}, {3, 5}};
        int[][] testArray2 = {{1, 2}, {6, 10}, {11, 15}};

        System.out.println(solution(testArray1) == 7);
        System.out.println(solution(testArray2) == 9);
    }
}

---

（易）分组飞行器棋子

问题描述
小M和小F在玩飞行棋。游戏结束后，他们需要将桌上的飞行棋棋子分组整理好。现在有 N 个棋子，每个棋子上有一个数字序号。小M的目标是将这些棋子分成 M 组，每组恰好5个，并且组内棋子的序号相同。小M希望知道是否可以按照这种方式对棋子进行分组。

例如，假设棋子序号为 [1, 2, 3, 4, 5]，虽然只有5个棋子，但由于序号不同，因此不能形成有效的分组。如果序号是 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2]，则可以形成两个有效分组，因此输出为 True。

测试样例

样例1：
输入：nums = [1, 2, 3, 4, 5]
输出：“False”

样例2：
输入：nums = [1, 1, 1, 1, 2, 1, 2, 2, 2, 2]
输出：“True”

样例3：
输入：nums = [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
输出：“True”

样例4：
输入：nums = [7, 7, 7, 8, 8, 8, 8, 8, 7, 7]
输出：“True”

样例5：
输入：nums = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
输出：“False”

解题思路

import java.util.Map;
import java.util.HashMap;

public class Main {
    public static String solution(int[] nums) {
        Map<Integer, Integer> countNum = new HashMap<>();
        for (int num : nums) {
            countNum.put(num, countNum.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : countNum.entrySet()) {
            if (entry.getValue()%5==0) {
                continue;
            } else {
                return "False";
            }
        }
        return "True";
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[]{1, 3, 4, 5, 6, 5, 4}).equals("false"));
        System.out.println(solution(new int[]{1, 1, 1, 1, 2, 1, 2, 2, 2, 2}).equals("true"));
        System.out.println(solution(new int[]{11, 45, 49, 37, 45, 38, 3, 47, 35, 49, 26, 16, 24, 4, 45, 39, 28, 26, 14, 22, 4, 49, 18, 4, 4, 26, 47, 14, 1, 21, 9, 26, 17, 12, 44, 28, 24, 24, 10, 31, 33, 32, 23, 41, 41, 19, 17, 24, 28, 46, 28, 4, 18, 23, 48, 45, 7, 21, 12, 40, 2, 19, 19, 28, 32, 6, 27, 43, 6, 18, 8, 27, 9, 6, 6, 31, 37, 15, 26, 20, 43, 3, 14, 40, 20}).equals("false"));
    }
}

---

（易）数列差异的最小化（半成品）

问题描述
给定长度分别为 n 和 m 的两个数列a[n]、b[m]，和一个整数k。求$|(a[i]-b[j]{)}^2-k^2|$的最小值。
输入格式
第一行有 2 个整数 n、m、k，分别表示数列 a、b 的长度，以及公式中的整数 k。
第二行有 n 个整数，表示数列 a 的各个元素。
第三行有 m 个整数，表示数列 b 的各个元素。
输出格式
求上述公式的最小值。
数据范围
其中 20%的数据：$1<=n,m<=3000，-10^9<=a[i],b[j],k<=10^9，foralli,j$
其中 30%的数据：$1<=n,m<=50000，k=0，-10^9<=a[i],b[j]<=10^9，foralli,j$
其中 50%的数据：$1<=n,m<=50000，-10^9<=a[i],b[j],k<=10^9，foralli,j$
输入样例

5 5 1
5 3 4 1 2
0 6 7 9 8

5 5 0
5 3 4 1 2
0 6 7 9 8

输出样例

0
1

解题思路

import java.util.List;

public class Main {
    public static int solution(int n, int m, int k, List<Integer> a, List<Integer> b) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                int temp = sum(a.get(i), b.get(j), k);
                if (temp < min) {
                    min = temp;
                }
            }
        }
        return min;
    }

    public static int sum(int a, int b, int c) {
        return Math.abs((a - b) * (a - b) - c * c);
    }

    public static void main(String[] args) {
        int n = 16;
        int m = 11;
        int k = 25;
        List<Integer> a = List.of(5, 11, 4, 24, 3, 14, 16, 22, 4, 3, 5, 12, 12, 11, 12, 18);
        List<Integer> b = List.of(23, 16, 6, 20, 1, 10, 16, 17, 17, 1, 23);

        System.out.println(solution(n, m, k, a, b));
    }
}

---

（易）完美整数

问题描述
一个整数如果由相同的数字构成，则称为完美整数。例如：

• 1、11、333是完美整数。
• 12、19、101是不完美整数。

现在，你需要计算给定区间 [x, y] 中有多少个整数是完美整数。

测试样例

样例1：
输入：x = 1 ,y = 10
输出：9

样例2：
输入：x = 2 ,y = 22
输出：10

解题思路

public class Main {
    public static int solution(int x, int y) {
        int count = 0;
        for (int i = x; i <= y; i++) {
            if (perfectNum(i)) {
                count++;
            }
        }
        return count;
    }

    public static boolean perfectNum(int x) {
        if (x >= 1 && x <= 9) {
            return true;
        } else if (x >= 10) {
            int lastNum = x % 10;
            x = x / 10;
            while (x > 0) {
                int temp = x % 10;
                if (temp == lastNum) {
                    x = x / 10;
                } else {
                    return false;
                }
            }
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        System.out.println(solution(1, 10) == 9);
        System.out.println(solution(2, 22) == 10);
    }
}

---

（易）版本号比较

问题描述
在某个项目中，每个版本都用版本号标记，由一个或多个修订号组成，修订号之间由点号.分隔。每个修订号可能有多位数字，并且可能会包含前导零。你需要根据两个版本号version1和version2，判断哪个版本更新，或者它们是否相同。

例如，2.5.33和0.1都是有效的版本号。

当比较两个版本时，从左到右依次比较它们的修订号。忽略每个修订号的前导零，直接比较修订号对应的整数值。如果其中一个版本没有足够的修订号，缺失部分默认补为0。

你需要根据以下规则返回比较结果：

• 如果version1 > version2，返回1。
• 如果version1 < version2，返回-1。
• 如果两个版本相等，返回0。

测试样例

样例1：
输入：version1 = “0.1” , version2 = “1.1”
输出：-1

样例2：
输入：version1 = “1.0.1” , version2 = “1”
输出：1

样例3：
输入：version1 = “7.5.2.4” , version2 = “7.5.3”
输出：-1

样例4：
输入：version1 = “1.0” , version2 = “1.0.0”
输出：0

解题思路

public class Main {
    public static void main(String[] args) {
        System.out.println(solution("0.1", "1.1") == -1);
        System.out.println(solution("1.0.1", "1") == 1);
        System.out.println(solution("7.5.2.4", "7.5.3") == -1);
        System.out.println(solution("1.0", "1.0.0") == 0);
    }

    public static int solution(String version1, String version2) {
        // Edit your code here
        String[] v1=version1.split("\\.");
        String[] v2=version2.split("\\.");
        StringBuilder v11=new StringBuilder();
        StringBuilder v22=new StringBuilder();
        for(String part:v1){
            v11.append(part);
        }
        for(String part:v2){
            v22.append(part);
        }
        while(v11.length()>v22.length()){
            v22.append("0");
        }
        while(v11.length()<v22.length()){
            v11.append("0");
        }
        int v111=Integer.parseInt(v11.toString());
        int v222=Integer.parseInt(v22.toString());
        if(v111>v222){
            return 1;
        }else if(v111<v222){
            return -1;
        }else {
            return 0;
        }
    }
}

---

（易）找出整型数组中占比超过一半的数

问题描述
小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。
测试样例

样例1：
输入：array = [1, 3, 8, 2, 3, 1, 3, 3, 3]
输出：3

样例2：
输入：array = [5, 5, 5, 1, 2, 5, 5]
输出：5

样例3：
输入：array = [9, 9, 9, 9, 8, 9, 8, 8]
输出：9

解题思路

import java.util.Map;
import java.util.HashMap;

public class Main {
    public static int solution(int[] array) {
        Map<Integer,Integer> countNum = new HashMap<>();
        for(int num :array){
            countNum.put(num, countNum.getOrDefault(num, 0)+1);
        }
        for(Map.Entry<Integer,Integer> entry:countNum.entrySet()){
            if(entry.getValue()>array.length/2){
                return entry.getKey();
            }
        }
        return 0;
    }
    public static void main(String[] args) {
        System.out.println(solution(new int[]{1, 3, 8, 2, 3, 1, 3, 3, 3}) == 3);
    }
}

---

（易）寻找单独数组卡片

问题描述
在一个班级中，每位同学都拿到了一张卡片，上面有一个整数。有趣的是，除了一个数字之外，所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么。
要求：

• 设计一个算法，使其时间复杂度为$O(n)$，其中$n$是班级的人数。
• 尽量减少额外空间的使用，以体现你的算法优化能力。

测试样例

样例1：
输入：cards = [1, 1, 2, 2, 3, 3, 4, 5, 5]
输出：4
解释：拿到数字 4 的同学是唯一一个没有配对的。

样例2：
输入：cards = [0, 1, 0, 1, 2]
输出：2
解释：数字 2 只出现一次，是独特的卡片。

样例3：
输入：cards = [7, 3, 3, 7, 10]
输出：10
解释：10 是班级中唯一一个不重复的数字卡片。

约束条件

• $1\le cards.length\le 1001$
• $0\le cards[i]\le 1000$
• 班级人数为奇数
• 除了一个数字卡片只出现一次外，其余每个数字卡片都恰好出现两次

解题思路

import java.util.HashMap;

public class Main {
    public static int solution(int[] inp) {
        HashMap<Integer, Integer> count = new HashMap<>();
        // Count the occurrences of each element
        for (int i = 0; i < inp.length; i++) {
            count.put(inp[i], count.getOrDefault(inp[i], 0) + 1);
        }
        // Find the first element that appears exactly once
        for (int i = 0; i < inp.length; i++) {
            if (count.get(inp[i]) == 1) {
                return inp[i];
            }
        }
        
        // If no such element is found, return 0 (or any other appropriate value)
        return 0;
    }

    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(solution(new int[]{1, 1, 2, 2, 3, 3, 4, 5, 5}) == 4);
        System.out.println(solution(new int[]{0, 1, 0, 1, 2}) == 2);
        System.out.println(solution(new int[]{1, 1, 2, 2, 3, 3, 4, 4,0}) == 0);
    }
}

---

（易）寻找最大葫芦

问题描述
在一场经典的德州扑克游戏中，有一种牌型叫做“葫芦”。“葫芦”由五张牌组成，其中包括三张相同牌面值的牌a和另外两张相同牌面值的牌b。如果两个人同时拥有“葫芦”，我们会优先比较牌a的大小，若牌a 相同则再比较牌b 的大小。
在这个问题中，我们对“葫芦”增加了一个限制：组成“葫芦”的五张牌牌面值之和不能超过给定的最大值$max$。牌面值的大小规则为$A>K>Q>J>10>9>...>2$，其中 A 的牌面值为1，K 为13，依此类推。
给定一组牌，你需要找到符合规则的最大的“葫芦”组合，并输出其中三张相同的牌面和两张相同的牌面。如果找不到符合条件的“葫芦”，则输出$“0,0”$。
测试样例

样例1：
输入：n = 9, max = 34, array = [6, 6, 6, 8, 8, 8, 5, 5, 1]
输出：[8, 5]

样例2：
输入：n = 9, max = 37, array = [9, 9, 9, 9, 6, 6, 6, 6, 13]
输出：[6, 9]

样例3：
输入：n = 9, max = 40, array = [1, 11, 13, 12, 7, 8, 11, 5, 6]
输出：[0, 0]

解题思路

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static int[] solution(int n, int max, int[] array) {
        // Edit your code here
        Map<Integer, Integer> table = new HashMap<>();
        for (int num : array) {
            int adjustedNum = num == 1? 14 : num;
            if (table.containsKey(adjustedNum)) {
                table.put(adjustedNum, table.get(adjustedNum) + 1);
            } else {
                table.put(adjustedNum, 1);
            }
        }

        int num3 = 0, num2 = 0;
        int currentSum = 0;
        for (Map.Entry<Integer, Integer> entry : table.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (value >= 3) {
                for (Map.Entry<Integer, Integer> innerEntry : table.entrySet()) {
                    int otherKey = innerEntry.getKey();
                    int otherValue = innerEntry.getValue();
                    if (otherKey!= key && otherValue >= 2) {
                        int sum = calculateSum(key == 14? 1 : key, otherKey == 14? 1 : otherKey);
                        if (key > num3 && sum <= max) {
                            num3 = key;
                            num2 = otherKey;
                            currentSum = sum;
                        } else if (key == num3 && otherKey > num2 && sum <= max) {
                            num2 = otherKey;
                            currentSum = sum;
                        }
                    }
                }
            }
        }

        return currentSum > 0? new int[]{(num3==14?1:num3), (num2==14?1:num2)} : new int[]{0, 0};
    }

    public static int calculateSum(int num1, int num2) {
        return num1 * 3 + num2 * 2;
    }

    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(java.util.Arrays.equals(solution(9, 34, new int[]{6, 6, 6, 8, 8, 8, 5, 5, 1}), new int[]{8, 5}));
        System.out.println(java.util.Arrays.equals(solution(9, 37, new int[]{9, 9, 9, 9, 6, 6, 6, 6, 13}), new int[]{6, 9}));
        System.out.println(java.util.Arrays.equals(solution(9, 40, new int[]{1, 11, 13, 12, 7, 8, 11, 5, 6}), new int[]{0, 0}));
    }
}

（易）小D的abc变换问题

问题描述
小D拿到了一个仅由"abc"三种字母组成的字符串。她每次操作会对所有字符同时进行以下变换：

• 将'a'变成'bc'
• 将'b'变成'ca'
• 将'c'变成'ab'

小D将重复该操作k次。你的任务是输出经过k次变换后，得到的最终字符串。

例如：对于初始字符串"abc"，执行2次操作后，字符串将变为"caababbcbcca"。

测试样例

样例1：
输入：s = “abc”, k = 2
输出：‘caababbcbcca’

样例2：
输入：s = “abca”, k = 3
输出：‘abbcbccabccacaabcaababbcabbcbcca’

样例3：
输入：s = “cba”, k = 1
输出：‘abcabc’

解题分析

public class Main {
    public static String solution(String s, int k) {
        // write code here
        for(int i=1;i<=k;i++){
            StringBuilder temp = new StringBuilder();
            for(char word :s.toCharArray()){
                if(word=='a'){
                    temp.append("bc");
                }else if(word=='b'){
                    temp.append("ca");
                }else if(word=='c'){
                    temp.append("ab");
                }
            }
            s=temp.toString();
        }
        return s;
    }

    public static void main(String[] args) {
        System.out.println(solution("abc", 2).equals("caababbcbcca"));
        System.out.println(solution("abca", 3).equals("abbcbccabccacaabcaababbcabbcbcca"));
        System.out.println(solution("cba", 1).equals("abcabc"));
    }
}

---

（中）数字魔法的加一操作

问题描述
数字魔法师小U发现了一种特殊的数字变换魔法。这个魔法可以对一个数字字符串进行"进位"操作。每次操作规则如下：

• 对字符串中的每个数字进行加一操作
• 当某位数字为9时，加一后变成 0，并在前面补 1

例如：

• “798” 经过一次操作变成 “8109”（7→8, 9→0并向前增加一个1, 8→9）
• “999” 经过一次操作变成 “101010”

现在给定一个数字字符串 num_str（长度为n）和操作次数 k，请计算经过 k 次操作后得到的最终结果。由于结果可能非常大，请将答案对 1000000007 (10^9 + 7) 取模。

输入

• 第一行包含两个整数 n 和 k（1 ≤ n ≤ 50, 1 ≤ k ≤ 100）
• 第二行包含一个长度为n的数字字符串 num_str，仅由数字0-9组成

返回

• 返回一个整数，表示最终结果对 1000000007 取模后的值

测试样例

样例1：
输入：n = 3 ,k = 1 ,num_str = “798”
返回：8109
解释：798 经过一次操作变成 8109

样例2：
输入：n = 3 ,k = 3 ,num_str = “798”
返回：103221

• 第一次操作：798 → 8109
• 第二次操作：8109 → 92110
• 第三次操作：92110 → 103221

样例3：
输入：n = 4 ,k = 3 ,num_str = “7989”
返回：10322132

解题思路
我们呢首先定义一个链表来存储数字字符串，然后将字符串反转进行加一操作（方便第一位进位操作）：如果小于9呢，就将原数字更新为结果；如果等于10呢，则将原位置更新为0，其后边插入一位，元素为1（注意这里是插入，也就是说后续的元素位置都会后移一位；为什么是后边不是前边呢，因为咱们把链表转置了）。然后再反转回来，考虑到结果大小，我们使用BigInteger对象进行接收，然后再返回取余的字符串。

import java.math.BigInteger;
import java.util.LinkedList;

public class Main {
    public static int solution(int n, int k, String numStr) {

        LinkedList<Integer> list = new LinkedList<>();
        for (char word : numStr.toCharArray()) {
            int num = word - '0';
            list.add(num);
        }

        // 使用内置方法反转链表
        java.util.Collections.reverse(list);

        // 逐位加一
        for(int j=0;j<k;j++){
            for (int i = 0; i < list.size(); i++) {
                int value = list.get(i) + 1;
                if (value <= 9) {
                    list.set(i, value);
                } else if (value == 10) {
                    list.set(i, 0);
                    list.add(i + 1, 1);
                    i++;
                }
            }
        }

        // 再次反转回来
        java.util.Collections.reverse(list);
        // 构建 BigInteger 对象
        StringBuilder sb = new StringBuilder();
        for (Integer num : list) {
            sb.append(num);
        }
        BigInteger number = new BigInteger(sb.toString());
        BigInteger text = new BigInteger("1000000007");
//        System.out.println(number.remainder(text).toString());
//        //检查转换后数据的类型
//        System.out.println(number.remainder(text).toString().getClass());
        return number.remainder(text).intValue();
    }

    public static void main(String[] args) {
        int result1 = solution(3, 1, "798");
        System.out.println(result1 == 8109);

        int result2 = solution(4, 1, "8109");
        System.out.println(result2 == 92110);

        int result3 = solution(5, 1, "92110");
        System.out.println(result3 == 103221);
    }
}

---

（中）最优硬币组合问题

问题描述
小C有多种不同面值的硬币，每种硬币的数量是无限的。他希望知道，如何使用最少数量的硬币，凑出给定的总金额N。小C对硬币的组合方式很感兴趣，但他更希望在满足总金额的同时，使用的硬币数量尽可能少。
例如：小C有三种硬币，面值分别为 1, 2, 5。他需要凑出总金额为 18。一种最优的方案是使用三个 5 面值的硬币，一个 2 面值的硬币和一个 1 面值的硬币，总共五个硬币。
测试样例

样例1：
输入：coins = [1, 2, 5], amount = 18
输出：[5, 5, 5, 2, 1]

样例2：
输入：coins = [1, 3, 4], amount = 6
输出：[3, 3]

样例3：
输入：coins = [5], amount = 10
输出：[5, 5]

解题思路
硬币凑数呢，是一个非常典型的动态规划问题。

• 分而治之：
  • 把一个大问题拆分成许多小问题。
  • 解决这些小问题，然后把它们的答案组合起来解决大问题。
• 重用答案：
  • 在解决小问题的过程中，有些小问题是重复出现的。
  • 我们把这些重复的小问题的答案记下来，下次遇到相同的小问题时直接使用之前的结果，避免重复计算。
• 逐步推进：
  • 从最简单的小问题开始，一步步解决更复杂的问题。
  • 每一步都基于之前已经解决的小问题的答案。

还是直接上案例吧：

一、元素排序

• 首先对输入的数组array进行排序。排序是为了后续处理时更容易找到合适的元素组合。

二、初始化动态规划数组

• 创建一个大小为total + 1的数组 dp，用于存储到达每个可能的目标值所需的最小元素数量。
• 初始情况下，除了dp[0] = 0表示目标值为 0 的情况外，
• 其他所有位置都被设置为最大整数值 Integer.MAX_VALUE。

三、填充动态规划数组

• 遍历数组array
  • 外层循环遍历数组array：
    • 对于数组array中的每个元素num，我们依次尝试用这个元素来减少目标值。
  • 内层循环遍历目标值：
    • 对于每个num，从num到total的范围内遍历每个目标值 i。
    • 如果dp[i - num]不是Integer.MAX_VALUE，表示i - num可以通过之前的元素组合达到。
• 更新dp数组：
  • 对于每个i，检查dp[i - num]是否不是 Integer.MAX_VALUE。
  • 如果dp[i - num]不是Integer.MAX_VALUE，则表示可以通过添加当前的num来减少目标值i。
  • 更新dp[i]为Math.min(dp[i], dp[i - num] + 1)，即取dp[i]和dp[i - num] + 1中的较小值。

四、检查结果

• 检查dp[total]是否仍然是Integer.MAX_VALUE，如果是，则说明没有找到满足条件的组合，返回 null。

五、构建结果列表

• 初始化结果列表和剩余目标值
  • 创建一个空的结果列表 result，并初始化剩余目标值remainingTotal为total
• 遍历数组array
  • 循环遍历array中的每个元素num
    • 对于每个num，检查当前的remainingTotal是否大于等于num。
    • 如果remainingTotal大于等于num并且dp[remainingTotal]等于dp[remainingTotal - num] + 1，则说明当前num可以用来减少剩余目标值remainingTotal。
• 具体逻辑分析
  • 条件判断
    • remainingTotal >= num：确保当前num不超过剩余目标值。
    • dp[remainingTotal] == dp[remainingTotal - num] + 1：确保当前num能够减少剩余目标值，并且这是最优选择。
  • 添加元素并更新剩余目标值
    • 将当前num添加到结果列表result中。
    • 更新剩余目标值remainingTotal，减去当前num。
• 循环终止条件：
  • 当remainingTotal小于num或者dp[remainingTotal]不等于dp[remainingTotal - num] + 1时，跳出当前循环，继续下一个num的处理。

六、返回结果列表

• 最后返回结果列表result。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static List<Integer> solution(int[] array, int total) {
        Arrays.sort(array);
        int[] dp = new int[total + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int num : array) {
            for (int i = num; i <= total; i++) {
                if (dp[i - num] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - num] + 1);
                }
            }
        }
        if (dp[total] == Integer.MAX_VALUE) {
            return null;
        }
        List<Integer> result = new ArrayList<>();
        int remainingTotal = total;
        for (int i = array.length - 1; i >= 0; i--) {
            while (remainingTotal >= array[i] && dp[remainingTotal] == dp[remainingTotal - array[i]] + 1) {
                result.add(array[i]);
                remainingTotal -= array[i];
            }
        }
        // System.out.println(result);
        return result;
    }

    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(solution(new int[]{1,2,3,10},21).equals(List.of(10,10,1)));      
        System.out.println(solution(new int[]{1, 2, 5}, 18).equals(List.of(5, 5, 5, 2, 1)));
    }
}

---

（中）有限制的楼梯攀登

问题描述
小U最近决定挑战一座非常高的楼梯，每次他可以选择走一步或两步，但有一个重要的限制：他不能连续走两步。因此，小U想知道他总共有多少种不同的方式可以从楼梯的底部走到顶端。
你需要帮他计算在给定的楼梯层数下，小U有多少种走法。
测试样例

样例1：
输入：n = 2
输出：2

样例2：
输入：n = 3
输出：3

样例3：
输入：n = 4
输出：4

解题思路
首先我们来回顾这道题的常规形式：也就是只有第一个要求的时候，此时当我们要走到第n层楼梯时，一共有两种情况：

• 从n-1层走一步到达n层
• 从n-2层走两步到达n层

$$f(n)=f(n-1)+f(n-2)$$

public class Main {
    public static int solution(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        if (n == 1) {
            return dp[1];
        } else if (n == 2) {
            return dp[2];
        } else {
            for (int i = 3; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }
    }
    public static void main(String[] args) {
        System.out.println(solution(2) == 2);
        System.out.println(solution(3) == 3);
        System.out.println(solution(4) == 5);
        System.out.println(solution(5) == 8);
    }
}

现在，我们来看这道变式题，这道题增加了第二个限制条件：不能连续地走两步。
这意味着任何时刻：

• 如果选择走一步，那么下一步可以走一步或者两步
• 如果选择走两步，那么下一步只能走一步

那么此时当我们到第n层时：

• 从n-1层走一步上来
• 从n-2层走两步上来，但是由于限制勒，这里的n-2层也必须由n-3层走一步上来，也就是$f(n-2)=f(n-3)$，那么我们将原本的$f(n-2)$由$f(n-3)$代替就相当于是加上了这一限制条件。

$$f(n)=f(n-1)+f(n-3)$$

public class Main {
    public static int solution(int n) {
        // Edit your code here
        int[] dp =new int[n+1];
        if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }else if(n==3){
            return 3;
        }
        else{
            dp[0]=0;
            dp[1]=1;
            dp[2]=2;
            dp[3]=3;
            for(int i=4;i<=n;i++){
                dp[i]=dp[i-1]+dp[i-3];
            }
            return dp[n];
        }   
    }
    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(solution(2) == 2);
        System.out.println(solution(3) == 3);
        System.out.println(solution(4) == 4);
        System.out.println(solution(5) == 6);
    }
}

---

（中）摇骰子的胜利概率

问题描述
小U和小S正在玩一个有趣的骰子游戏。每个骰子都有固定数量的面数$k(2<=k<=8)$，每一面的点数分别是1到$k$。
小U拥有$n$个骰子，每个骰子i的面数是$a_i$，摇到每一面的概率均为$1/a_i$。小S则有$m$个骰子，每个骰子j的面数是$b_j$，摇到每一面的概率均为$1/b_j$。
两人分别同时摇各自的骰子，并将摇出的点数相加，得分较高的一方获胜，得分相同则为平局。游戏只进行一次，没有重赛。现在小U想知道他获胜的概率是多少。你能帮他计算吗？
测试样例

样例1：
输入：n = 1, m = 3, arrayN = [8], arrayM = [2, 3, 4]
输出：0.255

样例2：
输入：n = 2, m = 2, arrayN = [3, 4], arrayM = [3, 3]
输出：0.5

样例3：
输入：n = 3, m = 1, arrayN = [2, 2, 2], arrayM = [4]
输出：0.844

解题思路
好了,来看这道题吧，两个人各自$n$个骰子,每个骰子面还不一样,让我们求前者骰子和更大的概率是多少？比较流畅的思路就是单独求他们各自所有可能出现的点数对应的概率,然后呢再逐次比较获得结果。比较应该是好比较的,两个$for$嵌套就可以出来,这道题的关键就在于我们如何把单独一个人所有可能点数对应的概率求出来：
我们以三个骰子，面数分别为$2、3、4$为例：
第一步：初始化概率数组dp

• 所有的可能中最大的点数和为$2+3+4=9$
• 由此我们初始化概率数组dp为$$[1.0,0,0,0,0,0,0,0,0,0]$$,数组长度为10,方便点数与下标一一对应。

第二步：处理第一个骰子(2面)

• 新建一个数组newDp为$$[0,0,0,0,0,0,0,0,0,0]$$长度依然为10。
• 此时我们要遍历所有可能的点数,也就是$从0到9$
• 每次呢检查概率数组dp中对应点数和的概率,当某个点数的概率不是0时,进行概率更新
  • $sum=0,dp[0]=1.0$
    • $newDp[0+1]=newDp[1]+dp[0]/2=0+\frac{1}{2}$
    • $newDp[0+2]=newDp[2]+dp[0]/2=0+\frac{1}{2}$
  • $sum=1,dp[1]=0$
  • $\dots \dots$
  • $sum=9,dp[9]=0$
• newDp复制给dp,此时dp为：$$[0.0,\frac{1}{2},\frac{1}{2},0,0,0,0,0,0,0]$$

第三步：处理第二个骰子(3面)

• 新建一个数组newDp为$$[0,0,0,0,0,0,0,0,0,0]$$
• 此时仍然是遍历所有可能的点数,$从0到9$
• 概率数组dp中对应的概率和不是0时,对所在位置概率进行更新
  • $sum=0,dp[0]=0$
  • $sum=1,dp[1]=\frac{1}{2}$
    • $newDp[1+1]=newDp[2]+dp[1]/3=0+\frac{1}{2}/3=\frac{1}{6}$
    • $newDp[1+2]=newDp[3]+dp[1]/3=0+\frac{1}{2}/3=\frac{1}{6}$
    • $newDp[1+3]=newDp[4]+dp[1]/3=0+\frac{1}{2}/3=\frac{1}{6}$
  • $sum=2,dp[2]=\frac{1}{2}$
    • $newDp[2+1]=newDp[3]+dp[2]/3=\frac{1}{6}+\frac{1}{2}/3=\frac{1}{3}$
    • $newDp[2+2]=newDp[4]+dp[2]/3=\frac{1}{6}+\frac{1}{2}/3=\frac{1}{3}$
    • $newDp[2+3]=newDp[5]+dp[2]/3=0+\frac{1}{2}/3=\frac{1}{6}$
  • $sum=3,dp[3]=0$
  • $\dots \dots$
  • $sum=9,dp[9]=0$
• newDp复制给dp,此时dp为：$$[0,0,\frac{1}{6},\frac{1}{3},\frac{1}{3},\frac{1}{6},0,0,0,0]$$

第四步：处理第三个骰子(4面)

• 新建一个数组newDp为$$[0,0,0,0,0,0,0,0,0,0]$$
• 遍历所有可能的点数,$从0到9$
• 概率数组dp中对应的概率和不是0时,对所在位置概率进行更新
  • $sum=0,dp[0]=0$
  • $sum=1,dp[1]=0$
  • $sum=2,dp[2]=\frac{1}{6}$
    • $newDp[2+1]=newDp[3]+dp[2]/4=0+\frac{1}{6}/4=\frac{1}{24}$
    • $newDp[2+2]=newDp[4]+dp[2]/4=0+\frac{1}{6}/4=\frac{1}{24}$
    • $newDp[2+3]=newDp[5]+dp[2]/4=0+\frac{1}{6}/4=\frac{1}{24}$
    • $newDp[2+4]=newDp[6]+dp[2]/4=0+\frac{1}{6}/4=\frac{1}{24}$
  • $sum=3,dp[3]=\frac{1}{3}$
    • $newDp[3+1]=newDp[4]+dp[3]/4=\frac{1}{24}+\frac{1}{3}/4=\frac{1}{8}$
    • $newDp[3+2]=newDp[5]+dp[3]/4=\frac{1}{24}+\frac{1}{3}/4=\frac{1}{8}$
    • $newDp[3+3]=newDp[6]+dp[3]/4=\frac{1}{24}+\frac{1}{3}/4=\frac{1}{8}$
    • $newDp[3+4]=newDp[7]+dp[3]/4=0+\frac{1}{3}/4=\frac{1}{12}$
  • $sum=4,dp[4]=\frac{1}{3}$
    • $newDp[4+1]=newDp[5]+dp[4]/4=\frac{1}{8}+\frac{1}{3}/4=\frac{5}{24}$
    • $newDp[4+2]=newDp[6]+dp[4]/4=\frac{1}{8}+\frac{1}{3}/4=\frac{5}{24}$
    • $newDp[4+3]=newDp[7]+dp[4]/4=\frac{1}{12}+\frac{1}{3}/4=\frac{1}{6}$
    • $newDp[4+4]=newDp[8]+dp[4]/4=0+\frac{1}{3}/4=\frac{1}{12}$
  • $sum=5,dp[5]=\frac{1}{6}$
    • $newDp[5+1]=newDp[6]+dp[5]/4=\frac{5}{24}+\frac{1}{6}/4=\frac{1}{4}$
    • $newDp[5+2]=newDp[7]+dp[5]/4=\frac{1}{6}+\frac{1}{6}/4=\frac{5}{24}$
    • $newDp[5+3]=newDp[8]+dp[5]/4=\frac{1}{12}+\frac{1}{6}/4=\frac{1}{8}$
    • $newDp[5+4]=newDp[9]+dp[5]/4=0+\frac{1}{6}/4=\frac{1}{24}$
  • $sum=6,dp[6]=0$
  • $\dots \dots$
  • $sum=9,dp[9]=0$
• newDp复制给dp,此时dp为：$$[0,0,0,\frac{1}{24},\frac{1}{8},\frac{5}{24},\frac{1}{4},\frac{5}{24},\frac{1}{8},\frac{1}{24}]$$

第五步：传出最终结果

• 骰子为2、3、4 的最终结果是：$$[0,0,0,\frac{1}{24},\frac{1}{8},\frac{5}{24},\frac{1}{4},\frac{5}{24},\frac{1}{8},\frac{1}{24}]$$

现在呢，我们再回头观察这个算法：我们要用两个数组，一个概率数组，一个每一轮的数组。什么意思呢？我们可以把三次骰子看做是逐次抛出：

• 第一轮,每轮数组会存入两面骰子可能出现的点数及其对应的概率,也就是下标为1、2的位置更新概率;(但我们犹记刚才这两个数组的长度都是2+3+4+1,所以其余位置就都保留为0)，然后概率数组复制结果;
• 第二轮,每轮数组首先都归零,然后遍历概率数组,对概率不是0的点呢进行本轮的概率更新,把结果都存入新的每轮数组中,保证了此时每次存入每轮数组中的概率都是两个骰子相乘的结果,然后概率数组复制结果;
• 第三轮呢,同第二轮,也保证了每次存入新的每轮数组中的结果都是三个骰子相乘的结果,然后概率数组复制结果,得到最终结果。

import java.util.Arrays;

public class Main {
    public static double solution(int n, int m, int[] arrayN, int[] arrayM) {
        double[] probA = calculateProbabilities(arrayN);
        double[] probB = calculateProbabilities(arrayM);

        double winProbability = 0.0;

        for (int i = 0; i < probA.length; i++) {
            for (int j = 0; j < probB.length; j++) {
                if (i > j) {
                    winProbability += probA[i] * probB[j];
                }
            }
        }
        // 保留三位小数
        return Math.round(winProbability * 1000.0) / 1000.0;
    }

    private static double[] calculateProbabilities(int[] dice) {
        int maxSum = Arrays.stream(dice).sum();
        double[] dp = new double[maxSum + 1];
        dp[0] = 1.0;
        for (int die : dice) {
            double[] newDp = new double[maxSum + 1];
            for (int sum = 0; sum <= maxSum; sum++) {
                if (dp[sum] > 0) {
                    for (int face = 1; face <= die; face++) {
                        newDp[sum + face] += dp[sum] / die;
                    }
                }
            }
            dp = newDp;
        }
        return dp;
    }

    public static void main(String[] args) {
        System.out.println(solution(1, 3, new int[]{8}, new int[]{2, 3, 4}));
    }
}

---

（中）和的逆运算问题(半成品)

问题描述
n 个整数两两相加可以得到 n(n - 1) / 2 个和。我们的目标是：根据这些和找出原来的 n 个整数。
按非降序排序返回这 n 个数，如果无解，输出 “Impossible”。
测试样例

样例1：
输入：n = 3, sums = [1269, 1160, 1663]
输出：“383 777 886”

样例2：
输入：n = 3, sums = [1, 1, 1]
输出：“Impossible”

样例3：
输入：n = 5, sums = [226, 223, 225, 224, 227, 229, 228, 226, 225, 227]
输出：“111 112 113 114 115”

样例4：
输入：n = 5, sums = [-1, 0, -1, -2, 1, 0, -1, 1, 0, -1]
输出："-1 -1 0 0 1"

样例5：
输入：n = 5, sums = [79950, 79936, 79942, 79962, 79954, 79972, 79960, 79968, 79924, 79932]
输出：“39953 39971 39979 39983 39989”

解题思路
这个是个半成品，也就是只能解决所有样例均大于等于零的情况。
具体思路呢，我们知道对于$n$个解，一共有$\frac{n(n-1)}{2}$个随机两个数的和。
那么我们按一般情况来考虑，这些和一定是有大小的，那么我们对这些和进行升序排列：$$a_{1+2}<a_{1+3}<\dots <a_{(n-1)+n}$$然后呢设$n$个解分别为：$$x_1,x_2,...,x_n$$同时满足：$$x_1<x_2<\dots <x_n$$那么最小的两个解一定等于最小的那一个和：$$x_1+x_2=a_{1+2}$$而第二小的和也一定满足：$$x_1+x_3=a_{1+3}$$然后呢拐点就来了，第三小的和我们不能证明是$x_1+x_4$还是$x_2+x_3$。一个思路如下：我们根据最小和的式子，可以得知：$$x_1<=\frac{a_{1+2}}{2}$$那么我们是不是可以通过暴力枚举获得$x_1$的值，如何确定呢？假定我们有一个可能的$x_1$的值，那么根据最小和的式子可得$x_2$,然后根据第二小的和的式子可得$x_3$,我们就可以知道这种情况下$x_2+x_3$的值,而第三小和第四小中一定有一个是和他相等的，如何存在，我们就可以知道假定成立。
然后呢我们可以创建一个哈希表，用来存储和以及出现的次数。此时我们已经确定$x_1+x_2,x_1+x_3,x_2+x_3$,就可以把这三组和从哈希表中出现的次数各减一，如果只出现一次就直接删除。然后此时哈希表中最小的和一定是$x_1+x_4
$,那我们就可以获得$x_4$,然后将$x_1+x_4,x_2+x_4,x_3+x_4$从哈希表中出现次数各减一或者直接删除；然后此时最小的和一定是$x_1+x_5$,重复上述操作。最终可以解决。

import java.util.*;

public class Main {
    public static String findOriginalNumbers(int n, int[] sums) {
        // 数组元素排序
        Arrays.sort(sums);
        // 求n-1组所有解的和
        int sumMultiplier = 0;
        for (int num : sums) {
            sumMultiplier += num;
        }
        // 如果不能被整除，则代表无解
        if (sumMultiplier % (n - 1) != 0) {
            return "Impossible";
        } else {
            // 借助哈希表创建键值字典
            Map<Integer, Integer> sumsDictionary = new HashMap<>();
            for (int num : sums) {
                // 判断键是否已存在，如果不存在则计数为 1，否则计数加 1
                sumsDictionary.merge(num, 1, Integer::sum);
            }

            // 定义一个最终接受int类型结果的链表
            List<Integer> result = new ArrayList<>();

            // 暴力枚举解x_1
            for (int x_1 = 0; x_1 <= sums[0]; x_1++) {
                int x_2 = sums[0] - x_1;
                int x_3 = sums[1] - x_1;
                if ( (x_2 + x_3 == sums[2] || (sums.length > 3 && x_2 + x_3 == sums[3])) && sumsDictionary.containsKey(x_2 + x_3)) {
                    result.add(x_1);
                    result.add(x_2);
                    result.add(x_3);

                    // 更新 sumsDictionary
                    if (sumsDictionary.get(x_2 + x_3) == 1) {
                        sumsDictionary.remove(x_2 + x_3);
                    } else {
                        sumsDictionary.put(x_2 + x_3, sumsDictionary.get(x_2 + x_3) - 1);
                    }
                    if (sumsDictionary.get(x_1 + x_3) == 1) {
                        sumsDictionary.remove(x_1 + x_3);
                    } else {
                        sumsDictionary.put(x_1 + x_3, sumsDictionary.get(x_1 + x_3) - 1);
                    }
                    if (sumsDictionary.get(x_1 + x_2) == 1) {
                        sumsDictionary.remove(x_1 + x_2);
                    } else {
                        sumsDictionary.put(x_1 + x_2, sumsDictionary.get(x_1 + x_2) - 1);
                    }
                    // 正式开始寻找新的元素，知道哈希图为空
                    while (!sumsDictionary.isEmpty()) {
                        // 找到此时哈希图中最小的一组键值
                        int minKey = Integer.MAX_VALUE;
                        for (int key : sumsDictionary.keySet()) {
                            minKey = Math.min(minKey, key);
                        }
                        // 获得新的元素
                        int newElement = minKey - x_1;
                        result.add(newElement);
                        // 删除由新元素组成的键值对，更新哈希表
                        for (int i = 0; i < result.size() - 1; i++) {
                            if (sumsDictionary.containsKey(result.get(i) + newElement)) {
                                if (sumsDictionary.get(result.get(i) + newElement) == 1) {
                                    sumsDictionary.remove(result.get(i) + newElement);
                                } else {
                                    sumsDictionary.put(result.get(i) + newElement, sumsDictionary.get(result.get(i) + newElement) - 1);
                                }
                            }
                        }
                    }
                    Collections.sort(result);
                    return result.toString().replaceAll("[\\[\\],]", "");
                }
            }
        }
        return "Impossible";
    }

    public static void main(String[] args) {

        int[] sums1 = {1269, 1160, 1663};
        System.out.println(findOriginalNumbers(3, sums1));
        System.out.println(findOriginalNumbers(3, sums1).equals("383 777 886"));
        System.out.println("-------------------------------------------------");

        int[] sums2 = {1, 1, 1};
        System.out.println(findOriginalNumbers(3, sums2));
        System.out.println(findOriginalNumbers(3, sums2).equals("Impossible"));
        System.out.println("-------------------------------------------------");

        int[] sums3 = {226, 223, 225, 224, 227, 229, 228, 226, 225, 227};
        System.out.println(findOriginalNumbers(5, sums3));
        System.out.println(findOriginalNumbers(5, sums3).equals("111 112 113 114 115"));
        System.out.println("-------------------------------------------------");

        int[] sums4 = {-1, 0, -1, -2, 1, 0, -1, 1, 0, -1};
        System.out.println(findOriginalNumbers(5, sums4));
        System.out.println(findOriginalNumbers(5, sums4).equals("-1 -1 0 0 1"));
        System.out.println("-------------------------------------------------");

        int[] sums5 = {79950, 79936, 79942, 79962, 79954, 79972, 79960, 79968, 79924, 79932};
        System.out.println(findOriginalNumbers(5, sums5));
        System.out.println(findOriginalNumbers(5, sums5).equals("39953 39971 39979 39983 39989"));
        System.out.println("-------------------------------------------------");

        int[] sums6 = {3, 4, 5, 5, 6, 7};
        System.out.println(findOriginalNumbers(4, sums6));
        System.out.println(findOriginalNumbers(4, sums6).equals("1 2 3 4"));
        System.out.println("-------------------------------------------------");

        int[] sums7 = {3, 4, 5};
        System.out.println(findOriginalNumbers(3, sums7));
        System.out.println(findOriginalNumbers(3, sums7).equals("1 2 3"));
        System.out.println("-------------------------------------------------");

        int[] sums8 = {3, 4, 5, 6, 7, 8, 7, 8, 9, 11};
        System.out.println(findOriginalNumbers(5, sums8));
        System.out.println(findOriginalNumbers(5, sums8).equals("1 2 3 5 6"));
    }
}

---

（难）二进制之和

问题描述
小U和小R喜欢探索二进制数字的奥秘。他们想找到一个方法，将两个二进制字符串相加并以十进制的形式呈现。这个过程需要注意的是，他们的二进制串可能非常长，所以常规的方法可能无法处理大数。小U和小R希望你帮助他们设计一个算法，该算法能在保证时间复杂度不超过$O(n^2)$的前提下，返回两个二进制字符串的十进制求和结果。

测试样例

样例1：
输入：$binary1="101",binary2="110"$
输出：‘11’

样例2：
输入：$binary1="111111",binary2="10100"$
输出：‘83’

样例3：
输入：$binary1="111010101001001011",binary2="100010101001"$
输出：‘242420’

样例4：
输入：$binary1="111010101001011",binary2="10010101001"$
输出：‘31220’

样例5：
输入：$binary1="11",binary2="1"$
输出：‘4’

解题思路
因为我们用的是Java语言，那这里补充一个知识点：

• BigInteger类：该类提供了对大整数的运算支持;
• BigDecima类：提供了对大浮点数的运算支持。

Java中的这两个类位于java.math包中，支持对任意精度数值的支持。

• BigInteger类：用于表示任意精度的整数。
  • 主要特点：
    • 任意精度：唯一限制它可以存储数值大小的限制是计算机可用内存。
    • 不可变性：这类对象一旦创建，其值不能改变，所以每次操作都要返回一个新的对象。
    • 线程安全

import java.math.BigInteger;

public class BigIntegerExample {
    public static void main(String[] args) {
        // 从字符串创建 BigInteger 对象
        BigInteger bigInt1 = new BigInteger("123456789012345678901234567890");
        
         // 从二进制字符串创建 BigInteger 对象
        BigInteger bigInt1 = new BigInteger("10101010101010101010101010101010", 2);
        
        // 从八进制字符串创建 BigInteger 对象
        BigInteger bigInt2 = new BigInteger("12345670123456701234567012345670", 8);
        
        // 从字节数组创建 BigInteger 对象
        byte[] bytes = {0, 1, -1, 2, -2};
        BigInteger bigInt2 = new BigInteger(bytes);
        
        // 从 long 值创建 BigInteger 对象
        BigInteger bigInt3 = BigInteger.valueOf(123456789L);

        // 加法
        BigInteger sum = bigInt1.add(bigInt2);
        System.out.println("Sum: " + sum);

        // 减法
        BigInteger difference = bigInt1.subtract(bigInt2);
        System.out.println("Difference: " + difference);

        // 乘法
        BigInteger product = bigInt1.multiply(bigInt2);
        System.out.println("Product: " + product);

        // 除法
        BigInteger quotient = bigInt1.divide(bigInt2);
        System.out.println("Quotient: " + quotient);

        // 取模
        BigInteger remainder = bigInt1.remainder(bigInt2);
        System.out.println("Remainder: " + remainder);

        // 同时返回商和余数
        BigInteger[] result = bigInt1.divideAndRemainder(bigInt2);
        System.out.println("Quotient: " + result[0]);
        System.out.println("Remainder: " + result[1]);

        // 幂运算
        BigInteger power = bigInt1.pow(2);
        System.out.println("Power: " + power);

        // 取反
        BigInteger negated = bigInt1.negate();
        System.out.println("Negated: " + negated);

        // 绝对值
        BigInteger absoluteValue = bigInt1.abs();
        System.out.println("Absolute Value: " + absoluteValue);

        // 比较
        int comparison = bigInt1.compareTo(bigInt2);
        if (comparison > 0) {
            System.out.println(bigInt1 + " is greater than " + bigInt2);
        } else if (comparison < 0) {
            System.out.println(bigInt1 + " is less than " + bigInt2);
        } else {
            System.out.println(bigInt1 + " is equal to " + bigInt2);
        }

        // 相等性检查
        boolean isEqual = bigInt1.equals(bigInt2);
        System.out.println("Are they equal? " + isEqual);

        // 转换为字符串
        String decimalString = bigInt1.toString();
        System.out.println("Decimal String: " + decimalString);

        // 转换为指定基数的字符串
        String binaryString = bigInt1.toString(2);
        System.out.println("Binary String: " + binaryString);
    }
}

• BigDecima类：用于表示任意精度的浮点数。
  • 主要特点：
    • 任意精度：只受限于可用内存。
    • 不可变性
    • 线程安全

import java.math.BigDecimal;
import java.math.RoundingMode;

public class BigDecimalExample {
    public static void main(String[] args) {
        // 从字符串创建 BigDecimal 对象
        BigDecimal bigDecimal1 = new BigDecimal("1234567890.1234567890");
        
        // 从 double 值创建 BigDecimal 对象
        BigDecimal bigDecimal2 = new BigDecimal(1234567890.1234567890);
        
        // 从 long 值创建 BigDecimal 对象
        BigDecimal bigDecimal3 = BigDecimal.valueOf(123456789L);

        // 加法
        BigDecimal sum = bigDecimal1.add(bigDecimal2);
        System.out.println("Sum: " + sum);

        // 减法
        BigDecimal difference = bigDecimal1.subtract(bigDecimal2);
        System.out.println("Difference: " + difference);

        // 乘法
        BigDecimal product = bigDecimal1.multiply(bigDecimal2);
        System.out.println("Product: " + product);

        // 除法，指定小数点后的位数和舍入模式
        BigDecimal quotient = bigDecimal1.divide(bigDecimal2, 10, RoundingMode.HALF_UP);
        System.out.println("Quotient: " + quotient);

        // 取模
        BigDecimal remainder = bigDecimal1.remainder(bigDecimal2);
        System.out.println("Remainder: " + remainder);

        // 设置小数点后的位数，指定舍入模式
        BigDecimal scaled = bigDecimal1.setScale(5, RoundingMode.HALF_UP);
        System.out.println("Scaled: " + scaled);

        // 取反
        BigDecimal negated = bigDecimal1.negate();
        System.out.println("Negated: " + negated);

        // 绝对值
        BigDecimal absoluteValue = bigDecimal1.abs();
        System.out.println("Absolute Value: " + absoluteValue);

        // 比较
        int comparison = bigDecimal1.compareTo(bigDecimal2);
        if (comparison > 0) {
            System.out.println(bigDecimal1 + " is greater than " + bigDecimal2);
        } else if (comparison < 0) {
            System.out.println(bigDecimal1 + " is less than " + bigDecimal2);
        } else {
            System.out.println(bigDecimal1 + " is equal to " + bigDecimal2);
        }

        // 相等性检查
        boolean isEqual = bigDecimal1.equals(bigDecimal2);
        System.out.println("Are they equal? " + isEqual);

        // 转换为字符串
        String decimalString = bigDecimal1.toString();
        System.out.println("Decimal String: " + decimalString);

        // 转换为未规范化字符串
        String unscaledString = bigDecimal1.toPlainString();
        System.out.println("Unscaled String: " + unscaledString);
    }
}

那么我们再回过头来看这道题，那似乎就简单多了：首先定义两个BigInteger对象，来接受二进制字符串，然后再调用相加函数，最后输出十进制的字符串。

import java.math.BigInteger;

public class Main {
    public static String solution(String binary1, String binary2) {
        // Please write your code here
        BigInteger num1 = new BigInteger(binary1,2);
        BigInteger num2 = new BigInteger(binary2,2);
        BigInteger sum =num1.add(num2);
        String sumStr = sum.toString(10);
        return sumStr;
    }

    public static void main(String[] args) {
        // You can add more test cases here
        System.out.println(solution("101", "110").equals("11"));
        System.out.println(solution("111111", "10100").equals("83"));
        System.out.println(solution("111010101001001011", "100010101001").equals("242420"));
        System.out.println(solution("111010101001011", "10010101001").equals("31220"));
    }
}

---

未完待续……