20201013携程研发笔试算法题
程序员文章站
2024-03-20 12:55:58
...
目录
- 买饮料投币次数
- 司机调度
- 数组越界
题目没记清，以下是大致描述
- 买饮料投币次数
现有一套贩卖机可以买可乐，该贩卖机只接受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);
}
}
上一篇： 02_二分法求函数的零点
下一篇： jsp页面中获取session中的值