尚硅谷图解Java数据结构和算法.pdf

二分查找法 非递归

image.png

  1. package com.atguigu.binarysearchnorecursion;
  3. public class BinarySearchNoRecur {
  5.     public static void main(String[] args) {
  6.         //测试
  7.         int[] arr = {1,3, 8, 10, 11, 67, 100};
  8.         int index = binarySearch(arr, 100);
  9.         System.out.println("index=" + index);//
  10.     }
  12.     //二分查找的非递归实现
  13.     /**
  14.      * 
  15.      * @param arr 待查找的数组, arr是升序排序
  16.      * @param target 需要查找的数
  17.      * @return 返回对应下标，-1表示没有找到
  18.      */
  19.     public static int binarySearch(int[] arr, int target) {
  21.         int left = 0;
  22.         int right = arr.length - 1;
  23.         while(left <= right) { //说明继续查找
  24.             int mid = (left + right) / 2;
  25.             if(arr[mid] == target) {
  26.                 return mid;
  27.             } else if ( arr[mid] > target) {
  28.                 right = mid - 1;//需要向左边查找
  29.             } else {
  30.                 left = mid + 1; //需要向右边查找
  31.             }
  32.         }
  33.         return -1;
  34.     }
  35. }

1、分治算法

算法介绍

分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

基本步骤

分治法在每一层递归上都有三个步骤：

  • 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
  • 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

  • 合并：将各个子问题的解合并为原问题的解

    应用——汉诺塔

    思路

    A、B、C三个塔

  • 如果只有一个盘，直接A->C

  • 如果大于等于两个盘，就分成两部分。最下面的一个盘为一部分，上面的所有盘为一部分

    • 将上面部分的盘A->B
    • 最下面的盘A->C

    • 再将B中的盘B->C

      实现代码

      ```java public class Demo1 { public static void main(String[] args) { hanoiTower(3, ‘A’, ‘B’, ‘C’); }

      /**

      • 汉诺塔 *
      • @param num 盘的总数
      • @param a 第一个塔
      • @param b 第二个塔
      • @param c 第三个塔 */ public static void hanoiTower(int num, char a, char b, char c) { //如果只有一个盘，把这个盘从A移动到C if(num == 1) { System.out.println(“把第” + num + “个盘从” + a + “->” + c); return; } //如果大于等于两个盘，将上面部分的盘从A借助C移动到B hanoiTower(num-1, a, c, b); //把最下面的盘从A移动到C System.out.println(“把第” + num + “个盘从” + a + “->” + c); //把上面部分的盘从B借助A移动到C hanoiTower(num-1, b, a, c); } }

运行结果

把第1个盘从A->C 把第2个盘从A->B 把第1个盘从C->B 把第3个盘从A->C 把第1个盘从B->A 把第2个盘从B->C 把第1个盘从A->C

  1. <a name="evi6s"></a>
  2. ### 博客推荐
  3. 在刷leetcode时有幸看到了一位大佬写的关于递归的博客，在此转载贴出。<br />[点此跳转](https://lyl0724.github.io/2020/01/25/1/)
  4. <a name="Gs4py"></a>
  5. ## 2、动态规划
  6. <a name="K32ud"></a>
  7. ### 算法介绍
  9. - 动态规划(Dynamic Programming)算法的核心思想是：将**大问题划分为小问题**进行解决，从而一步步获取最优解的处理算法
  10. - 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
  11. - 与分治法不同的是，适合于用动态规划求解的问题，经分解得到**子问题往往不是互相独立的**。( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
  12. - 动态规划可以通过**填表**的方式来逐步推进，得到最优解
  13. <a name="JUbDp"></a>
  14. ### 算法应用——01背包问题
  15. | **物品** | **重量** | **价值** |
  16. | --- | --- | --- |
  17. | 吉他 | 1 | 1500 |
  18. | 音响 | 4 | 3000 |
  19. | 电脑 | 3 | 2000 |
  21. 一个背包最多装4kg的东西，求
  23. - 装入物品使得背包的总价值最大，且不超出背包的容量
  24. - 要求装入的物品**不能重复**（01背包）
  25. <a name="bg6f0"></a>
  26. #### 解题思路
  27. 算法的主要思想，利用动态规划来解决。每次遍历到的第 i个物品，根据 w[i]和 v[i]来确定是否需要将该物品放入背包中。即对于给定的 n个物品，**设 v[i]、w[i]分别为第 i个物品的价值和重量**，C为背包的容量。再令二维数组<br />v[ i ][ j ]<br />表示在前 i个物品中能够装入容量为 j的背包中的**最大价值**。则我们有下面的结果
  28. ```java
  29. //表示填入表的第一行和第一列是 0，主要是为了方便表示物品和容量
  30. (1) v[i][0]=v[0][j]=0; 
  32. // 当准备加入新增的商品的重量大于当前背包的容量时，就直接使用上一个单元格的装入策略（装入物品的价值）
  33. (2) 当 w[i]>j 时：v[i][j]=v[i-1][j] 
  35. // 当准备加入的新增的商品的容量小于等于当前背包的容量,
  36. // 装入的方式:
  37. (3) 当 j>=w[i]时：v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
  39. v[i-1][j]：上一个装法的总价值
  41. v[i] : 表示当前商品的价值
  43. v[i-1][j-w[i]] ： 装入i-1商品，到剩余空间j-w[i]的总价值

简单来说：

  • 装入物品的容量大于背包容量时，直接使用之前装入背包物品的最大价值
  • 装入物品容量小于等于背包容量时，比较选取较大者
    • 装入该物品之前，背包物品的最大价值
    • 装入该后，该物品的价值+剩余容量能放入物品的最大价值image.png

      实现代码

      ```java package dynamic;

/**

  • @author Voyager1

  • @create 2021-10-22 15:58 */ public class KnapsackProblem { public static void main(String[] args) {

    1.  int[] w = {1,4,3};//物品重量
    2.  int[] val = {1500,3000,2000};//物品价值
    3.  int m = 4;//背包容量
    4.  int n = val.length;//物品个数
    6.  //创建二维数组，
    7.  //v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
    8.  int[][] v = new int[n+1 ][m+1];
    9.  //为了记录放入商品的情况，我们定一个二维数组
    10.  int[][] path = new int[n+1][m+1];
    12.  //初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0
    13.  for(int i = 0; i < v.length; i++) {
    14.      v[i][0] = 0; //将第一列设置为0
    15.  }
    16.  for(int i=0; i < v[0].length; i++) {
    17.      v[0][i] = 0; //将第一行设置0
    18.  }
    20.  //根据前面得到公式来动态规划处理
    21.  for (int i = 1; i < v.length; i++) {
    22.      for (int j = 1; j < v[0].length; j++) {
    23.          //如果物品的重量大于背包剩余的容量，就不放入
    24.          //i-1是因为下标是从1开始的，减一后才为0
    25.          if (w[i-1] > j){
    26.              v[i][j] = v[i-1][j];
    27.          }else {
    28.              //说明:
    29.              //因为我们的i 从1开始的， 因此公式需要调整成
    30.              //v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
    31.              //为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
    32.              if (v[i-1][j] < val[i-1] + v[i-1][j-w[i-1]]){
    33.                  v[i][j] = val[i-1] + v[i-1][j-w[i-1]];
    34.                  //把当前的情况记录到path
    35.                  path[i][j] = 1;
    36.              }else {
    37.                 v[i][j] = v[i-1][j];
    38.              }
    39.          }
    40.      }
    42.  }
    44.  //输出一下v 看看目前的情况
    45.  for(int i =0; i < v.length;i++) {
    46.      for(int j = 0; j < v[i].length;j++) {
    47.          System.out.print(v[i][j] + " ");
    48.      }
    49.      System.out.println();
    50.  }
    52.  System.out.println("============================");
    54.  //动脑筋
    55.  int i = path.length - 1; //行的最大下标
    56.  int j = path[0].length - 1;  //列的最大下标
    57.  while(i > 0 && j > 0 ) { //从path的最后开始找
    58.      if(path[i][j] == 1) {
    59.          System.out.printf("第%d个商品放入到背包\n", i);
    60.          j -= w[i-1]; //w[i-1]
    61.      }
    62.      i--;
    63.  }

    } }

运行结果

[0, 0, 0, 0, 0] [0, 1500, 1500, 1500, 1500] [0, 1500, 1500, 1500, 3000] [0, 1500, 1500, 2000, 3500]

将第3个物品放入背包 将第1个物品放入背包

  1. <a name="BYni0"></a>
  2. ## 3、KMP算法
  3. <a name="KbOAp"></a>
  4. ### 暴力匹配法
  5. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/12831985/1634901518412-4a087f96-09e1-4a09-8ef2-4073789503f7.png#clientId=ueb32eae9-5e1f-4&from=paste&id=u11fbd644&margin=%5Bobject%20Object%5D&name=image.png&originHeight=288&originWidth=828&originalType=url&ratio=1&size=53537&status=done&style=none&taskId=uaba541d4-7785-4b31-8925-efb3bdf98ed)
  6. <a name="J1ogR"></a>
  7. ### 暴力匹配算法 代码实现
  8. ```java
  9. public class ViolenceMatch {
  10.     public static void main(String[] args) {
  11.         //测试暴力匹配算法
  12.         String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
  13.         String str2 = "尚硅谷你尚硅你";
  14.         int index = violenceMatch(str1, str2);
  15.         System.out.println("index=" + index);
  16.     }
  17.     // 暴力匹配算法实现
  18.     public static int violenceMatch(String str1,String str2){
  19.         char[] s1 = str1.toCharArray();
  20.         char[] s2 = str2.toCharArray();
  22.         int s1Len = s1.length;
  23.         int s2Len = s2.length;
  25.         int i = 0; // i索引指向s1
  26.         int j = 0; // j索引指向s2
  27.         while (i < s1Len && j < s2Len){
  28.             if (s1[i] == s2[j]){
  29.                 i++;
  30.                 j++;
  31.             }else {
  32.                 i = i - (j - 1);
  33.                 j = 0;
  34.             }
  35.         }
  36.         //判断是否匹配成功
  37.         if(j == s2Len) {
  38.             return i - j;
  39.         } else {
  40.             return -1;
  41.         }
  42.     }
  43. }

KMP是一个解决模式串在文本串是否出现过，如果出现过，找出最早出现的位置的经典算法
参考资料：https://www.cnblogs.com/zzuuoo666/p/9028287.html

算法应用——字符串匹配

思路及图解

问题：有一个字符串 str1= BBC ABCDAB ABCDABCDABDE，和一个子串 str2=ABCDABD。现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1

算法步骤

  • 首先，用 str1的第一个字符和 str2的第一个字符去比较，不符合，关键词向后移动一位

十、算法 - 图3

  • 重复第一步，还是不符合，再后移

十、算法 - 图4

  • 一直重复，直到 Str1有一个字符与 Str2的第一个字符符合为止

十、算法 - 图5

  • 接着比较字符串和搜索词的下一个字符，还是符合

十、算法 - 图6

  • 遇到 Str1有一个字符与 Str2对应的字符不符合

十、算法 - 图7
重要步骤

  • 这时候，想到的是继续遍历 str1的下一个字符，重复第 1步。(其实是很不明智的，因为此时 BCD已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”
    • KMP 算法的想法是：设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率

  • 怎么做到把刚刚重复的步骤省略掉？可以对 str2计算出一张部分匹配表，这张表的产生在后面介绍

    • str2的部分匹配表如下 | 搜索词 | A | B | C | D | A | B | D | | —- | —- | —- | —- | —- | —- | —- | —- | | 部分匹配值 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |

  • 已知空格与 D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的部分匹配值为 2，因此按照下面的公式算出向后移动的位数：

    • 移动位数 = 已匹配的字符数 - 对应的部分匹配值
    • 因为 6 - 2 等于 4，所以将搜索词向后移动 4 位

十、算法 - 图8
十、算法 - 图9

  • 因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为 2（”AB”），对应的部分匹配值为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移 2 位

十、算法 - 图10

  • 因为空格与 A不匹配，继续后移一位

十、算法 - 图11
十、算法 - 图12

  • 逐位比较，直到发现 C与 D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动 4 位

十、算法 - 图13

  • 逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动 7 位，这里就不再重复了

十、算法 - 图14

部分匹配表的生成

前缀与后缀

  • 前缀：ABCD的前缀为[A, AB, ABC]
  • 后缀：ABCD的后缀为[BCD, CD, D]

部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

  • ”A”的前缀和后缀都为空集，共有元素的长度为 0；
  • ”AB”的前缀为[A]，后缀为[B]，共有元素的长度为 0；
  • ”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度 0；
  • ”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为 0；
  • ”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为 1；
  • ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为 2；
  • ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD,D]，共有元素的长度为 0。

十、算法 - 图15

实现代码

  1. public class Demo3 {
  2.    public static void main(String[] args) {
  3.       String str1 = "BBC ABCDAB ABCDABCDABDE";
  4.       String str2 = "ABCDABD";
  5.         int result = getPosition(str1, str2);
  6.         if(result != -1) {
  7.             System.out.print("匹配位置是：str1[");
  8.             System.out.println(result + "]");
  9.         } else {
  10.             System.out.println("匹配失败");
  11.         }
  12.    }
  14.    /**
  15.     *得到匹配字符串的部分匹配表
  16.     *
  17.     * @param matchStr 用于匹配的字符串
  18.     * @return 部分匹配表
  19.     */
  20.    public static int[] getNext(String dest) {
  21.       //部分匹配值的数组
  22.       int[] next = new int[dest.length()];
  23.       //匹配字符串的第一个元素没有前缀与后缀，部分匹配值为0
  24.       next[0] = 0;
  25.       //i用来指向部分匹配字符串末尾的字符，j用来指向开始的字符
  26.       for (int i = 1,j = 0 ; i < dest.length(); i++) {
  27.          //当j>0且前缀后缀不匹配时，使用部分匹配表中前一个表项的值
  28.           while (j > 0 && dest.charAt(i) != dest.charAt(j)){
  29.                 j = next[j - 1];
  30.            }
  31.          //如果前缀后缀匹配，j向后移，继续比较
  32.          if (dest.charAt(i) == dest.charAt(j)){
  33.                 j++;
  34.           }
  35.          //存入匹配值
  36.          next[i] = j;
  37.       }
  38.       return next;
  39.    }
  41.    /**
  42.     * 通过KMP算法匹配字符串，若匹配成功，返回第一个字符出现的位置
  43.     *
  44.     * @param str1 用于匹配的字符串
  45.     * @param str2 要匹配的字符串
  46.     * @return 第一个字符出现的位置，没有则返回-1
  47.     */
  48.    public static int kmpSearch(String str1, String str2) {
  49.       //获得str2的部分匹配表
  50.       int[] next = getNext(str2);
  51.       for(int i = 0, j = 0; i < str1.length(); i++) {
  52.          //需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
  53.             //KMP算法核心点, 可以验证...
  54.             while (j > 0 && str1.charAt(i) != str2.charAt(j)){
  55.                 j = next[j-1];
  56.             }
  57.             if (str1.charAt(i) == str2.charAt(j)){
  58.                 j++;
  59.             }
  60.             if (j == str2.length()) {
  61.                 return i - j + 1;
  62.             }
  63.         }
  64.         return -1;
  65.    }
  66. }
  67. 运行结果
  69. 匹配位置是：str1[15]

4、贪心算法

算法简介

  • 贪心算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利)的选择，从而

希望能够导致结果是最好或者最优的算法

  • 贪心算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

    算法应用——集合覆盖

    假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有的地区都可以接收到信号
电台 覆盖地区个数 覆盖地区
K1 0 北京 上海 天津
K2 0 广州 北京 深圳
K3 0 成都 上海 杭州
K4 0 上海 天津
K5 0 杭州 大连

思路及图解

思路

  • 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系
  • 将这个电台加入到一个集合中(比如 ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
  • 重复第 1步直到覆盖了全部的地区

图解
十、算法 - 图16

  • 遍历电台的覆盖地区，发现K1覆盖的地区最多，将K1覆盖的地区从地区集合中移除。然后将K1放入电台集合中，并更新覆盖地区个数

十、算法 - 图17

  • 遍历，发现K2覆盖的地区最多，将K2覆盖的地区从地区集合中移除。然后将K2放入电台集合中，并更新覆盖地区个数

十、算法 - 图18

  • 遍历，发现K3覆盖的地区最多，将K3覆盖的地区从地区集合中移除。然后将K3放入电台集合中，并更新覆盖地区个数

十、算法 - 图19

  • 遍历，发现K5覆盖的地区最多，将K5覆盖的地区从地区集合中移除。然后将K5放入电台集合中，并更新覆盖地区个数。所有区域都被覆盖，算法结束

十、算法 - 图20

  1. package com.luyi.algorithm;
  3. import java.security.AllPermission;
  4. import java.util.ArrayList;
  5. import java.util.HashMap;
  6. import java.util.HashSet;
  7. import java.util.Map;
  9. /**
  10.  * 贪心算法解决算法 广播覆盖问题
  11.  */
  12. public class GreedyAlgorithm {
  13.     public static void main(String[] args) {
  14.         // 创建广播电台 放入Map
  15.         Map<String, HashSet<String>> broadcast = new HashMap<>();
  16.         // 将各个电台放入HashSet
  17.         HashSet<String> hashSet1 = new HashSet<>();
  18.         hashSet1.add("北京");
  19.         hashSet1.add("上海");
  20.         hashSet1.add("天津");
  22.         HashSet<String> hashSet2 = new HashSet<>();
  23.         hashSet2.add("广州");
  24.         hashSet2.add("上海");
  25.         hashSet2.add("深圳");
  27.         HashSet<String> hashSet3 = new HashSet<>();
  28.         hashSet3.add("成都");
  29.         hashSet3.add("上海");
  30.         hashSet3.add("杭州");
  32.         HashSet<String> hashSet4 = new HashSet<>();
  33.         hashSet4.add("上海");
  34.         hashSet4.add("天津");
  36.         HashSet<String> hashSet5 = new HashSet<>();
  37.         hashSet5.add("杭州");
  38.         hashSet5.add("大连");
  40.         broadcast.put("k1", hashSet1);
  41.         broadcast.put("k2", hashSet2);
  42.         broadcast.put("k3", hashSet3);
  43.         broadcast.put("k4", hashSet4);
  44.         broadcast.put("k5", hashSet5);
  46.         // 存放所有地区
  47.         HashSet<String> allArea = new HashSet<>();
  48.         for (Map.Entry<String, HashSet<String>> entity : broadcast.entrySet()) {
  49.             allArea.addAll(entity.getValue());
  50.         }
  51.         // 可以输出验证一波
  52. //        for (String s : allArea) {
  53. //            System.out.println(s);
  54. //        }
  55.         // 创建 ArrayList存放选择的电台集合
  56.         ArrayList<String> selects = new ArrayList<>();
  58.         // 定义一个临时集合 在遍历过程中 存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
  59.         HashSet<String> tempSet = new HashSet<>();
  61.         // 定义一个maxKey 保存在一次遍历过程中 能够覆盖最大覆盖的地区对应的电台key
  62.         // 如果maxKey 不为null 则会加入selects里
  63.         String maxKey = "";
  64.         while (allArea.size() != 0) { // 如果allArea > 0 则还没有覆盖所有的地区
  65.             maxKey = ""; // 每个循环需要对maxKey清空
  66.             // 遍历broadcast. 取出对应的ekey
  67.             for (String key : broadcast.keySet()) {
  68.                 tempSet.clear(); // tempSet 每个循环要清空
  69.                 // areas 当前的key(电台) 能够覆盖的地区
  70.                 HashSet<String> areas = broadcast.get(key);
  71.                 tempSet.addAll(areas);
  72.                 // 取出tempSet 与 allAreas 集合的交集  retainAll 方法 将交集的部分赋值给tempSet
  73.                 tempSet.retainAll(allArea);
  74.                 // 如果当前这个集合包含的未覆盖的地区的数量 比maxSize 指向集合为覆盖的地区的多 将 maxSize重新赋值
  75.                 if (tempSet.size() > 0 && ("".equals(maxKey) || tempSet.size() > broadcast.get(maxKey).size())) {
  76.                     maxKey = key;
  77.                 }
  78.             }
  79.             // 如果maxKey的长度不为0 将 maxKey加入到selects
  80.             if (!"".equals(maxKey)) {
  81.                 selects.add(maxKey);
  82.                 // 将maxKey指向的广播电台覆盖的地区, 从allAreas 去掉
  83.                 allArea.removeAll(broadcast.get(maxKey));
  84.             }
  85.         }
  86.         System.out.println("得到的集合为:"+ selects); //得到的集合为:[k1, k2, k3, k5]
  87.     }
  88. }

注意事项

image.png

算法应用——钱币找零

假设纸币金额为1元、5元、10元、20元、50元、100元
要凑成123元应该尽可能兑换少的纸币

算法思路

  • 尽可能从大面值一直往下减即可

    实现代码

    ```java public class Demo1 { public static void main(String[] args) {

    1. splitChange(123);

    }

    /**

    • 拆分零钱 *
    • @param money 钱币总金额 */ public static void splitChange(int money) { //零钱金额，纸币的种类 int[] prices = {100, 50, 20, 10, 5, 1}; //用于记录每种纸币的数量，下标与prices数组的下标对应 int[] counts = new int[prices.length]; //剩下的金额 int surplus = money; if(money > 0) { //如果剩下的金额大于0 while(surplus > 0) {
      1.   //从大金额向小金额进行凑数
      2.   for(int i = 0; i<prices.length; i++) {
      3.      //每张钱币的数量
      4.      int count = 0;
      5.      //如果该金额的钱币小于总金额，该钱币数量+1
      6.      while (surplus - prices[i] >= 0) {
      7.         count++;
      8.         surplus -= prices[i];
      9.      }
      10.      counts[i] = count;
      11.   }
      } }
  1.   //打印结果
  2.   System.out.println("凑成" + money +"元");
  3.   for(int i = 0; i<prices.length; i++) {
  4.      if(counts[i] != 0) {
  5.         System.out.println("需要" + prices[i] + "元的纸币" + counts[i] + "张");
  6.      }
  7.   }

} }

运行结果

凑成123元 需要100元的纸币1张 需要20元的纸币1张 需要1元的纸币3张 ```