目录
买饮料投币次数司机调度数组越界题目没记清，以下是大致描述
买饮料投币次数 现有一套贩卖机可以买可乐，该贩卖机只接受10，50，100的硬币。 现在要买m瓶可乐，手里有a枚10元硬币、b枚50元硬币、c枚100元硬币，可乐的价格为 x （x为10的倍数）。 每次投币优先选择面值较大的硬币，如可乐240，则我们优先投三枚100元硬币。贩卖机找零优先找面值较大的硬币，如刚才要找零60，则会选择一枚50元硬币和1枚10元硬币。 每次只能买一瓶可乐（即每次都要经历投币，买可乐，找零）。输入描述： 输入5个数字依次表示m, a, b, c, x。
输出描述： 输出一个整数表示需要投币的次数。
示例： 输入 2 1 4 3 250 输出 8 说明：第一瓶可乐需要投3枚100，第二瓶需要投5枚50。
//思路： //每次投一个手上最大的硬币，累加这个硬币面值，当这个面值超过x时，就停止投币并进行找零。 //比如以示例来看，先投三个100，然后找零50。 //创建一个保存硬币个数的数组，当投币时，对应数组元素-1；当找零时，对应数组元素+1。 //每次投币时，也就是当硬币个数-1的操作时，就记录一次。 //循环m次后返回记录的投币次数。 import java.util.Scanner; public class Main { //硬币面值数组（从大到小排序） private static int[] coin = {100, 50, 10}; /** * @param m 可乐数 * @param a 10元硬币数 * @param b 50元硬币数 * @param c 100元硬币数 * @param x 可乐价格 * @return 返回投币次数 */ private static int buyCoke(int m, int a, int b, int c, int x) { int count = 0; //投币次数 int[] num = {c, b, a}; //硬币个数，按coin数组排序 //一次买一瓶可乐 while (m > 0) { int money = 0; //每次买可乐投入贩卖机的钱 int index = 0; //使用哪种硬币 while (true) { //当前硬币个数为0时取下一个硬币 if (num[index] == 0) { index++; continue; } money += coin[index]; //投币次数+1 count++; //硬币个数-1 num[index]--; //若投入的钱大于可乐价格，则需要找零 if (money >= x) { if (money > x) backZero(money - x, num); //找零 break; } } m--; } return count; } /** * @param money 待找零总金额 * @param num 硬币个数数组 */ private static void backZero(int money, int[] num) { int index = 0; //使用哪种硬币 while (money != 0) { if (money - coin[index] >= 0) { money -= coin[index]; num[index]++; //硬币数+1 } else index++; //硬币面值大于待找金额时，取下一种硬币 } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); int a = in.nextInt(); int b = in.nextInt(); int c = in.nextInt(); int x = in.nextInt(); System.out.println(buyCoke(m, a, b, c, x)); } } 司机调度 现有司机 2N 人。第 i 个司机去 A 市可收入为income[i][0]，去 B 市可收入为income[i][1]。返回将每个司机都去到某个城市的最高收入，要求每个城市都有 N 个司机抵达。输入描述： 循环输入，每行输入两个数，第一个表示去A市的收入，第二个表示去B市的收入。
输出描述： 输出一个整数表示N个去A市的司机收入和N个去B市的司机收入之和的最大值。 注意：当参输入异常时输出error。
示例1： 输入 10 20 20 30 输出 50 说明：第一个司机去A市，第二个司机去B市，总和为10 + 40 = 50。
示例2： 输入 10 30 100 200 150 50 60 20 输出 440 说明：前两个司机去B市，后两个司机去A市：30 + 200 + 150 + 60。
//思路： //先让所有司机去B市，然后再从其中找出N名司机去A市。 //去A市的司机，收入必定要比在B市更赚。其赚得最多的N名就是我们要找的N名司机。 //可以通过用“A市的收入 - B市的收入”去最大的N名即可实现收入最大化。 //其中“A市的收入 - B市的收入”这个值可正可负，负数表示该司机去A市亏了。 //所以这道题，仅仅需要通过排序“A市的收入 - B市的收入”即可正确解答。 import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); /* --输入-- */ ArrayList<int[]> list = new ArrayList<int[]>(); while (in.hasNextInt()) { //IDEA按Ctrl+D手动结束该循环 int incomeOfA = in.nextInt(); int incomeOfB = in.nextInt(); int[] element = {incomeOfA, incomeOfB}; list.add(element); } /* --输入结束-- */ int length = list.size(); //没有输入或司机数不是2的倍数 if (length == 0 || length % 2 != 0) { System.out.println("error"); return; } //将输入转为数组，方便排序 int[][] income = new int[length][2]; for (int i = 0; i < length; i++) income[i] = list.get(i); //降序排序，A市收入与B市收入的差值作为排序依据 Arrays.sort(income, (o1, o2) -> (o2[0] - o2[1]) - (o1[0] - o2[0])); int total = 0; int n = length >> 1; for (int i = 0; i < n; i++) total += income[i][0] + income[i + n][1]; System.out.println(total); } } 数组越界 作为一个新手程序员，数组越界是一个非常容易犯的错误。游游为了提醒自己，决定写一个小程序来分析自己的代码中是否存在这样的错误。但它很快发现，这项工作对于它来说太过困难了。所以它希望你来帮忙实现一个简化后的版本。 在这个简化后的版本中，它所需要处理的语句只有以下两种类型：整形数组定义语句：格式为name[size]。例如：a[5]或者array[10]。数组可用的下标为[0, size)。定义后的数组所有的元素均为0； 赋值语句：格式为name[index]=value。例如：a[0]=1或者a[a[0]]=a[a[3]]。 在被分析的代码中，数组越界错误只会出现在赋值语句中，且代码中只会有这一类错误。游游希望你帮它找出代码中第一次出现错误的语句，并输出对应的行号。
输入描述： 第一行为一个整数n，表示总的代码行数。 从第二行至第n+1行每行均为代码字符串，且只会为上述两种语句之一。
输出描述： 仅输出一个整数，表示第一次出现错误的语句所对应的行号。若程序中无任何错误，则输出"0"（不包含双引号）。
示例1：
输入 3 a[50] a[a[1]]=1 a[a[55]]=a[15] 输出 3 说明：第三行a[55]越界。示例2：
输入 6 a[50] a[1]=10 a[a[1]]=20 a[a[10]]=a[1] a[a[b[10]]]=0 a[a[55]]=1 输出 5 说明：第5行因为没有b数组，所以是错误的。示例3：
输入 2 a[50] b[10] 输出 0 说明：没有错误。分步解释： 1. 如何获取数组名称？ 定义一个方法，传入参数为一个类似a[1], a[a[1]]之类的字符串，然后获取第一个[，截取该字符前的字符串即为数组名称。
private static String getArrName(String line) { char[] c = line.toCharArray(); for (int i = 0; i < c.length; i++) { if (c[i] == '[') return line.substring(0, i); } return null; }2. 如何获取数组索引（长度）？ 输入参数与上面一样，然后遍历字符串，记录第一个[字符的下标和最后一个]字符的下标，截取两个下标中间的字符串。
private static String getArrIndex(String line) { char[] c = line.toCharArray(); int left = -1, right = -1; for (int i = 0; i < c.length; i++) { if (left == -1 && c[i] == '[') left = i; else if (c[i] == ']') right = i; } return line.substring(left + 1, right); }3. 核心思路第一步：保存数组 定义两个map，一个保存数组名称与数组长度的映射，方便通过数组名称来判断当前索引是否越界；另一个用来保存数组名称与数组本身的映射，方便给实现赋值语句。
//数组名称和长度映射 private static HashMap<String, Integer> lengthMap = new HashMap<String, Integer>(); //数组名称和数组映射 private static HashMap<String, int[]> arrMap = new HashMap<String, int[]>(); //数字正则判断 private static final String REGEX = "^[-|+]?[0-9]+$"; //后面的步骤会用到4. 核心思路第二步：声明语句与赋值语句 若是声明语句，则代码行不会出现=，所以可以直接获取数组名称和长度保存到lengthMap，然后创建一个空数组，长度为获取到的长度，并保存到arrMap。 若是赋值语句，则代码行会出现=，先根据=切割数组两边。首先是左边，然后获取数组名称（该名称必定存在于map中，该题只判断越界），通过该名称从lengthMap中获取数组长度，用于后面越界判断；再通过该名称从arrMap中获取数组本身，用于后面执行赋值操作。然后获取索引，该索引可能为数组的某个元素（如a[a[1]]索引为a[1]），所以需要执行操作获取到最终索引值（后面再讲）。 判断最终索引值是否越界，越界则结束方法，返回越界行号。 若不越界，则获取要赋予数组元素的值，即=右边。若为数字则直接转换；若不为数字则执行与上述获取最终索引值相同的操作获取最终值。 获取最终值时，要解决一个问题。在获取最终索引值时，所越界则通过返回-1的形式。当在获取最终值时，我们可以允许到最后的值是-1。这里留意一下。 上述若未越界，则执行最后的赋值操作。
/** * 核心方法 * @param lines 代码行 * @return 返回报错的行号 */ private static int validateArrayUsages(String[] lines) { String name; //数组名称 String index; //索引 int length; //长度 for (int i = 0; i < lines.length; i++) { String line = lines[i]; //声明语句 if (line.indexOf("=") == -1) { name = getArrName(line); length = Integer.parseInt(getArrIndex(line)); lengthMap.put(name, length); int[] element = new int[length]; //创建该数组 arrMap.put(name, element); } //赋值语句（重点） else { String[] s = line.split("="); //等式左边 String leftStr = s[0]; name = getArrName(leftStr); index = getArrIndex(leftStr); length = lengthMap.get(name); int[] elementLeft = arrMap.get(name); //该数组为最终需要进行赋值操作的数组 int j = getIndex(index, length); //获取索引最终值，下面的步骤讲 if (j == -1) //表示越界 return i + 1; //等式右边 String rightStr = s[1]; int value; if (rightStr.matches(REGEX)) //右边为纯数字 value = Integer.parseInt(rightStr); else { //这里就是刚才要留意的地方，我们之所以麻烦的在获取一次数字名称和索引什么的 //原因是若直接调用getIndex()方法，返回的-1可能是报错或者元素值就是-1 //如rightStr=“a[1]”，然后a[1]=-1 //若直接getIndex()就是报错，所以这里才麻烦的再获取一次 name = getArrName(rightStr); index = getArrIndex(rightStr); length = lengthMap.get(name); int[] elementRight = arrMap.get(name); //右边数组，用于获取要赋的值 value = getIndex(index, length); if (value == -1) return i + 1; value = elementRight[value]; } //赋值 elementLeft[j] = value; } } return 0; }5. 核心思路第三部：获取最终索引（值） 其实就是递归下去，直到获取的索引值是数字即可停止递归。如a[a[a[1]]]，获取到a[a[1]]，进入递归，然后获取a[1]，再进入递归，然后获取1，递归结束，返回1。之后获取1对应的元素值再返回，以此类推。最终就会获取到a[a[a[1]]]的值。
/** * 获取索引 * @param index 传入索引 * @param length 传入数组长度 * @return 返回最终索引所表示的值 */ private static int getIndex(String index, int length) { int i; if (index.matches(REGEX)) i = Integer.parseInt(index); //若是数字直接转换 else i = judgeIndex(index); //非数字则需要进行判断 if (i < 0 || i >= length) return -1; //越界 return i; } /** * 判断索引是否合法 * @param str 传入像a[1]或a[a[1]]这样的索引 * @return 返回最终值或-1 */ private static int judgeIndex(String str) { String name = getArrName(str); String index = getArrIndex(str); int length = lengthMap.get(name); int[] element = arrMap.get(name); //若不存在数组直接返回-1 if (lengthMap.containsKey(name)) { //获取下标对应的值，若index = "a[1]"，a[1] = 2，则i = 2 int i = getIndex(index, length); if (i != -1) return element[i]; } return -1; }完整代码：
import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int linesSize = Integer.parseInt(in.nextLine().trim()); String[] lines = new String[linesSize]; for (int i = 0; i < linesSize; i++) lines[i] = in.nextLine(); System.out.println(String.valueOf(validateArrayUsages(lines))); } private static HashMap<String, Integer> lengthMap = new HashMap<String, Integer>(); private static HashMap<String, int[]> arrMap = new HashMap<String, int[]>(); private static final String REGEX = "^[-|+]?[0-9]+$"; private static int validateArrayUsages(String[] lines) { String name; String index; int length; for (int i = 0; i < lines.length; i++) { String line = lines[i]; if (line.indexOf("=") == -1) { name = getArrName(line); length = Integer.parseInt(getArrIndex(line)); lengthMap.put(name, length); int[] element = new int[length]; arrMap.put(name, element); } else { String[] s = line.split("="); String leftStr = s[0]; name = getArrName(leftStr); index = getArrIndex(leftStr); length = lengthMap.get(name); int[] elementLeft = arrMap.get(name); int j = getIndex(index, length); if (j == -1) return i + 1; String rightStr = s[1]; int value; if (rightStr.matches(REGEX)) value = Integer.parseInt(rightStr); else { name = getArrName(rightStr); index = getArrIndex(rightStr); length = lengthMap.get(name); int[] elementRight = arrMap.get(name); value = getIndex(index, length); if (value == -1) return i + 1; value = elementRight[value]; } elementLeft[j] = value; } } return 0; } private static int getIndex(String index, int length) { int i; if (index.matches(REGEX)) i = Integer.parseInt(index); else i = judgeIndex(index); if (i < 0 || i >= length) return -1; return i; } private static int judgeIndex(String str) { String name = getArrName(str); String index = getArrIndex(str); int length = lengthMap.get(name); int[] element = arrMap.get(name); if (lengthMap.containsKey(name)) { int i = getIndex(index, length); if (i != -1) return element[i]; } return -1; } private static String getArrName(String line) { char[] c = line.toCharArray(); for (int i = 0; i < c.length; i++) { if (c[i] == '[') return line.substring(0, i); } return null; } private static String getArrIndex(String line) { char[] c = line.toCharArray(); int left = -1, right = -1; for (int i = 0; i < c.length; i++) { if (left == -1 && c[i] == '[') left = i; else if (c[i] == ']') right = i; } return line.substring(left + 1, right); } }