华为机考
031 【靠谱的车】
程序员小明打了一辆出租车去上班。出于职业敏感，他注意到这辆出租车的计费表有点问题，总是偏大。
出租车司机解释说他不喜欢数字4，所以改装了计费表，任何数字位置遇到数字4就直接跳过，其余功能都正常。
比如：
23再多一块钱就变为25；
39再多一块钱变为50；
399再多一块钱变为500；
小明识破了司机的伎俩，准备利用自己的学识打败司机的阴谋。
给出计费表的表面读数，返回实际产生的费用。
输入描述:
只有一行，数字N，表示里程表的读数。
(1<=N<=888888888)。
输出描述:
一个数字，表示实际产生的费用。以回车结束。
示例1：
输入
5
输出
4
说明
5表示计费表的表面读数。
4表示实际产生的费用其实只有4块钱。
示例2：
输入
17
输出
15
说明
17表示计费表的表面读数。
15表示实际产生的费用其实只有15块钱。
示例3：
输入
100
输出
81
说明
100表示计费表的表面读数。
81表示实际产生的费用其实只有81块钱。
public class ZT31 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int input = sc.nextInt();
int reduce = 0;
int idx = 0;
while (idx < input){
int next = idx +1 ;
String temp = String.valueOf(next);
String newTemp = "";
if (temp.contains("4")) {
int fourIdx = temp.indexOf("4");
if (fourIdx == temp.length()-1){
newTemp = temp.substring(0,fourIdx) + 5;
}else {
newTemp = temp.substring(0,fourIdx) + 5 + temp.substring(fourIdx+1);
}
reduce += Integer.parseInt(newTemp) - idx -1;
idx = Integer.parseInt(newTemp);
}else {
idx++;
}
}
System.out.println(input - reduce);
}
上述算法遇到大位数据会超时，优化如下
public class ZT3102 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int input = in.nextInt();
//求司机多算了多少[0,10][10,100][100,1000]
int temp = 0;
int total = input;
int k = 0;//记录当前位
int j = 1;//记录个位？
//13
while (total > 0){
if (total % 10 >4) {//当前位大于4
temp += (total % 10 - 1) * k + j ;
}else {//当前位小于4
temp += (total % 10) * k;
}
k = k * 9 + j;
j *= 10;
total = total/10;
}
System.out.println(input - temp);
}
}
032 【快递运输】
一辆运送快递的货车，运送的快递均放在大小不等的长方体快递盒中，为了能够装载更多的快递，同时不能让货车超载，需要计算最多能装多少个快递。
注：快递的体积不受限制，快递数最多1000个，货车载重最大50000。
输入描述:
第一行输入每个快递的重量，用英文逗号分隔，如：5,10,2,11
第二行输入货车的载重量，如：20
不需要考虑异常输入。
输出描述:
输出最多能装多少个快递，如：3
示例1：
输入
5,10,2,11
20
输出
3
说明
货车的载重量为20，最多只能放三个快递5、10、2，因此输出3
public class ZT32 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] input = sc.nextLine().split(",");//2 5 10 11 2510
int max = Integer.parseInt(sc.nextLine());//20
int[] arr = new int[input.length];
for (int i = 0; i < input.length; i++) {
arr[i] = Integer.parseInt(input[i]);
}
Arrays.sort(arr);
System.out.println(calc(arr,0,0,0,max));
}
private static int calc(int[] arr,int idx,int count,int total,int max){
if (total > max || idx>= arr.length){
return count-1;
}
int cl1 = calc(arr, idx+1, count+1,total + arr[idx],max);
int cl2 = calc(arr, idx+1, count, total,max);
return Math.max(cl1,cl2);
}
}
033 【连续字母长度】
给定一个字符串，只包含大写字母，求在包含同一字母的子串中，长度第 k 长的子串的长度，相同字母只取最长的那个子串。
输入描述:
第一行有一个子串(1<长度<=100)，只包含大写字母。
第二行为 k的值
输出描述:
输出连续出现次数第k多的字母的次数。
示例1
输入
AAAAHHHBBCDHHHH
3
输出
2
说明
同一字母连续出现的最多的是A和H，四次；第二多的是H，3次，但是H已经存在4个连续的，故不考虑；下个最长子串是BB，所以最终答案应该输出2。
示例2
输入
AABAAA
2
输出
1
说明
同一字母连续出现的最多的是A，三次；第二多的还是A，两次，但A已经存在最大连续次数三次，故不考虑；下个最长子串是B，所以输出1
示例3
输入
ABC
4
输出
-1
说明
只含有3个包含同一字母的子串，小于k，输出-1
示例4
输入
ABC
2
输出
1
说明
三个子串长度均为1，所以此时k = 1，k=2，k=3这三种情况均输出1。特此说明，避免歧义。
备注:
若子串中只包含同一字母的子串数小于k，则输出-1
public class ZT33 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
int k1 = Integer.parseInt(sc.nextLine());
int[] arr = new int[26];
int temp = 0;
char pre = ' ';
for (int i = 0; i < input.length(); i++) {
if (i == 0){
temp++;
pre = input.charAt(i);
}else if (input.charAt(i) == pre){
temp++;
int count = arr[pre - 'A'];
arr[pre - 'A'] = Math.max(temp, count);
}else {//换代
temp = 1;
pre = input.charAt(i);
arr[input.charAt(i) - 'A'] = Math.max(temp, arr[input.charAt(i) - 'A'] );;
}
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0){
list.add(arr[i]);
}
}
list.sort((a1,b1) -> b1 - a1);
if (list.size()<k1){
System.out.println(-1);
}else {
System.out.println(list.get(k1-1));
}
}
}
034 【两数之和绝对值最小】
给定一个从小到大的有序整数序列（存在正整数和负整数）数组 nums ，请你在该数组中找出两个数，其和的绝对值(|nums[x]+nums[y]|)为最小值，并返回这个绝对值。
每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
输入描述:
一个通过空格分割的有序整数序列字符串，最多1000个整数，且整数数值范围是 -65535~65535。
输出描述:
两数之和绝对值最小值
示例1
输入
-3 -1 5 7 11 15
输出
2
说明
因为 |nums[0] + nums[2]| = |-3 + 5| = 2 最小，所以返回 2
public class ZT34 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] input = sc.nextLine().split(" ");
int[] arr = new int[input.length];
for (int i = 0; i < input.length; i++) {
arr[i] = Integer.parseInt(input[i]);
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
min = Math.min(min,Math.abs(arr[i]+arr[j]));
}
}
System.out.println(min);
}
}
035 【流水线】
一个工厂有m条流水线，来并行完成n个独立的作业，该工厂设置了一个调度系统，在安排作业时，总是优先执行处理时间最短的作业。
现给定流水线个数m，需要完成的作业数n, 每个作业的处理时间分别为t1,t2…tn。请你编程计算处理完所有作业的耗时为多少？
当n>m时，首先处理时间短的m个作业进入流水线，其他的等待，当某个作业完成时，依次从剩余作业中取处理时间最短的进入处理。
输入描述:
第一行为2个整数（采用空格分隔），分别表示流水线个数m和作业数n；
第二行输入n个整数（采用空格分隔），表示每个作业的处理时长t1,t2…tn。
0< m,n<100，0<t1,t2…tn<100。
注：保证输入都是合法的。
输出描述:
输出处理完所有作业的总时长
示例1
输入
3 5
8 4 3 2 10
输出
13
说明
1、先安排时间为2、3、4的3个作业。
2、第一条流水线先完成作业，然后调度剩余时间最短的作业8。
3、第二条流水线完成作业，然后调度剩余时间最短的作业10。
4、总工耗时就是第二条流水线完成作业的时间13（3+10）。
public class ZT35 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] input = sc.nextLine().split(" ");
String[] job = sc.nextLine().split(" ");
int med = Integer.parseInt(input[0]);
int[] arr = new int[job.length];
for (int i = 0; i < job.length; i++) {
arr[i] = Integer.parseInt(job[i]);
}
Arrays.sort(arr);
List<Medic> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (list.size() <med){
list.add(new Medic(arr[i],arr[i]));
}else {
//找到数组中 total最小的medic 加进去
Collections.sort(list);
Medic medic = list.get(0);
medic.total += arr[i];
}
}
Collections.sort(list);
System.out.println(list.get(list.size()-1).total);
}
static class Medic implements Comparable{
private int end;
private int total;
public Medic(int end, int total) {
this.end = end;
this.total = total;
}
@Override
public int compareTo(Object obj) {
Medic medic= (Medic)obj;
return this.total - medic.total;
}
}
}
036 【内存资源分配】
有一个简易内存池，内存按照大小粒度分类，每个粒度有若干个可用内存资源，用户会进行一系列内存申请，需要按需分配内存池中的资源，返回申请结果成功失败列表。分配规则如下：
1、分配的内存要大于等于内存申请量，存在满足需求的内存就必须分配，优先分配粒度小的，但内存不能拆分使用。
2、需要按申请顺序分配，先申请的先分配。
3、有可用内存分配则申请结果为true，没有可用内存分配则返回false。
注：不考虑内存释放。
输入描述:
输入为两行字符串：
第一行为内存池资源列表，包含内存粒度数据信息，粒度数据间用逗号分割，一个粒度信息内部用冒号分割，冒号前为内存粒度大小，冒号后为数量。资源列表不大于1024，每个粒度的数量不大于4096
第二行为申请列表，申请的内存大小间用逗号分隔。申请列表不大于100000
如：
64:2,128:1,32:4,1:128
50,36,64,128,127
输出描述:
输出为内存池分配结果。
如：
true,true,true,false,false
示例1
输入
64:2,128:1,32:4,1:128
50,36,64,128,127
输出
true,true,true,false,false
说明
内存池资源包含：64K共2个、128K共1个、32K共4个、1K共128个的内存资源；
针对50,36,64,128,127的内存申请序列，分配的内存依次是：64,64,128,NULL,NULL,第三次申请内存时已经将128分配出去，
因此输出结果是：true,true,true,false,false
public class ZT36 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] input = sc.nextLine().split(",");
String[] apply = sc.nextLine().split(",");
List<Integer> exist = new ArrayList<>();
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < input.length; i++) {
String[] typeCount = input[i].split(":");
int type = Integer.parseInt(typeCount[0]);
exist.add(type);
map.put(type,Integer.parseInt(typeCount[1]));
}
Collections.sort(exist);
for (int i = 0; i < apply.length; i++) {
boolean flag = false;
int need = Integer.parseInt(apply[i]);
for (int j = 0; j < exist.size(); j++) {
if (need<= exist.get(j)){
//拿出来一个
int pool = map.get(exist.get(j));
flag = true;
if (--pool == 0){
map.remove(exist.get(j));
exist.remove(j);
}else {
map.put(exist.get(j),pool);
}
break;
}
}
System.out.print(flag + " ");
}
System.out.println();
}
}
037 【判断一组不等式是否满足约束并输出最大差】
给定一组不等式，判断是否成立并输出不等式的最大差(输出浮点数的整数部分)，要求：1）不等式系数为double类型，是一个二维数组；2）不等式的变量为int类型，是一维数组；3）不等式的目标值为double类型，是一维数组；4）不等式约束为字符串数组，只能是：“>”,“>=”,“<”,“<=”,“=”，例如,不等式组：
a11x1+a12x2+a13x3+a14x4+a15x5<=b1;
a21x1+a22x2+a23x3+a24x4+a25x5<=b2;
a31x1+a32x2+a33x3+a34x4+a35
x5<=b3;
最大差=max{ (a11x1+a12x2+a13x3+a14x4+a15x5-b1), (a21x1+a22x2+a23x3+a24x4+a25x5-b2), (a31x1+a32x2+a33x3+a34x4+a35
x5-b3) }，类型为整数(输出浮点数的整数部分)
输入描述:
1）不等式组系数(double类型)：
a11,a12,a13,a14,a15
a21,a22,a23,a24,a25
a31,a32,a33,a34,a35
2）不等式变量(int类型)：
x1,x2,x3,x4,x5
3）不等式目标值(double类型)：b1,b2,b3
4)不等式约束(字符串类型):<=,<=,<=
输入：a11,a12,a13,a14,a15;a21,a22,a23,a24,a25;a31,a32,a33,a34,a35;x1,x2,x3,x4,x5;b1,b2,b3;<=,<=,<=
输出描述:
true 或者 false, 最大差
示例1
输入
2.3,3,5.6,7,6;11,3,8.6,25,1;0.3,9,5.3,66,7.8;1,3,2,7,5;340,670,80.6;<=,<=,<=
输出
false 458
示例2
输入
2.36,3,6,7.1,6;1,30,8.6,2.5,21;0.3,69,5.3,6.6,7.8;1,13,2,17,5;340,67,300.6;<=,>=,<=
输出
false 758
038 【判断字符串子序列】
给定字符串 target和 source, 判断 target 是否为 source 的子序列。
你可以认为 target 和 source 中仅包含英文小写字母。字符串 source可能会很长（长度 ~= 500,000），而 target 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”abc”是”aebycd”的一个子序列，而”ayb”不是）。
请找出最后一个子序列的起始位置。
输入描述:
第一行为target，短字符串（长度 <=100）
第二行为source，长字符串（长度 ~= 500,000）
输出描述:
最后一个子序列的起始位置， 即最后一个子序列首字母的下标
示例1
输入
abc
abcaybec
输出
3
说明
这里有两个abc的子序列满足，取下标较大的，故返回3
备注:
若在source中找不到target，则输出-1
public class ZT38 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String target = sc.nextLine();//[0,100]
String source = sc.nextLine();//[0,50w]
int idx = source.length();
for (int i = target.length()-1; i >= 0; i--) {
char ta = target.charAt(i);
if (source.contains(String.valueOf(ta))) {
int idxLast = source.lastIndexOf(String.valueOf(ta));
if (idxLast < idx){
idx = idxLast;
}else {
System.out.println(-1);
return;
}
}else {
System.out.println(-1);
return;
}
}
System.out.println(idx);
}
}
039 【拼接URL】
给定一个URL前缀和URL后缀，通过”,”分割，需要将其连接为一个完整的URL，如果前缀结尾和后缀开头都没有“/”，需自动补上“/”连接符，如果前缀结尾和后缀开头都为“/”，需自动去重。
约束：不用考虑前后缀URL不合法情况。
输入描述:
URL前缀（一个长度小于100的字符串),URL后缀（一个长度小于100的字符串）。
输出描述:
拼接后的URL。
示例1
输入
/acm,/bb
输出
/acm/bb
示例2
输入
/abc/,/bcd
输出
/abc/bcd
示例3
输入
/acd,bef
输出
/acd/bef
示例4
输入
,
输出
/
040 【求符合要求的结对方式】
用一个数组A代表程序员的工作能力，公司想通过结对编程的方式提高员工的能力，假设结对后的能力为两个员工的能力之和，求一共有多少种结对方式使结对后能力为N。
输入描述:
5
1 2 2 2 3
4
第一行为员工的总人数，取值范围[1,1000]
第二行为数组A的元素，每个元素的取值范围[1,1000]
第三行为N的值，取值范围[1,1000]
输出描述:
4
满足结对后能力为N的结对方式总数
示例1
输入
5
1 2 2 2 3
4
输出
4
说明
满足要求的结对方式为：A[0]和A[4]，A[1]和A[2]，A[1]和A[3]，A[2]和A[3]
public class ZT40 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int people = Integer.parseInt(sc.nextLine());
String[] input = sc.nextLine().split(" ");
int target = Integer.parseInt(sc.nextLine());
int[] arr = new int[people];
for (int i = 0; i < people; i++) {
arr[i] = Integer.parseInt(input[i]);
}
int count = 0;
for (int i = 0; i < people; i++) {
for (int j = i + 1; j < people; j++) {
if (target == arr[i] + arr[j]){
count++;
}
}
}
System.out.println(count);
}
}