华为2019-09-29笔试题
之前报了华为的通用软件工程师，过了两个月才接到笔试通知。一共三道题，分别是100分，200分，300分，按照官方给的标准，只要拿到100分以上就可以参加面试。当时第一题AC了，第二道题写到最后感觉虽然不会AC，但是至少能通过一部分测试用例，结果上传了三次都是0%，当时比较急躁就索性交了。结束之后自己又检查了一下，结果发现是因为最后输出的时候index弄错了…改了一行代码就好了，唉，要是当时静下心仔细看一下也就好了。
第一题：合并url
合并两个url，/a, /b, 两个url需要用/隔开，如果没有就加上，如果两个都有就去重。输入：url1,url2， 输出：url1/url2。
示例：
/a,/b => /a/b
/a/,b => /a/b
/a/,/b => /a/b
, => /
这一题是很简单的字符串处理题，主要是需要注意多种情况，以及单个url为空的情况，比如：/a,和,/b。考虑到所有情况就可以AC了。一轮技术面的时候面试官让我再次提交了这一题，没让我写输入的处理，直接字符串传入就好，下面是代码。
public class Main {
public static void main(String[] args) {
String input = ",/b";
String[] in = input.split(",");
System.out.println(result(in));
}
public static String result(String[] in) {
if (in.length == 0) return "/";
if (in.length == 1) {
if (in[0].charAt(in[0].length() - 1) == '/') return in[0];
return in[0] + "/";
}
if (in.length == 2 && in[0].length() == 0) {
if (in[1].charAt(0) == '/') return in[1];
return "/" + in[1];
}
if (in[0].charAt(in[0].length() - 1) == '/' && in[1].charAt(0) == '/') {
return in[0] + in[1].substring(1);
} else if (in[0].charAt(in[0].length() - 1) != '/' && in[1].charAt(0) != '/') {
return in[0] + "/" + in[1];
} else {
return in[0] + in[1];
}
}
}
第二题：薅羊毛
商场准备了很多活动，每参加一场就可以获得一个红包，给出商场的活动时间表，帮李奶奶找到如何规划行程可以获得最多的红包，输出最多的红包数量以及场次规划。每一场活动的时间格式为(开始时间,结束时间)，比如：(1,3)代表1点开始3点结束，每个时间表中间用空格隔开，只有开始时间大于上一场结束时间才可以参加，比如参加(1,3)就不能参加(2,4)。如果两个时间规划得到红包一样多，输出开始最晚或者结束最早的。
示例：
输入： (1,5) (3,6) (6,7)
输出： count:2
(3,6) (6,7)
看到这一题我的第一反应就是用贪心算法，找局部最优解，每次寻找剩下场次里面结束最早的，这样就可以尽可能多的参加活动，拿更多红包。我写了一个方法，是用来寻找结束时间最早的场次，每次找完判断是不是还有，有的话继续调用自身，相当于是一个迭代。结果我在结束判断语句那里卡住了，也因为比较紧张，试了好几种方案都是在原地打转，最后也是发现只需要两行代码，唉，还是不够熟练。
我的第一稿代码如下：
import java.util.*;
public class Main {
static ArrayList<Integer> results = new ArrayList<Integer>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String input = in.nextLine().trim();
String[] time = input.split(" ");
Schedule[] schedules = new Schedule[time.length];
for (int i = 0; i < time.length; i++) {
String tem = time[i].substring(1, time[i].length() - 1);
String[] tems = tem.split(",");
schedules[i] = new Schedule(i, Integer.parseInt(tems[0]),Integer.parseInt(tems[1]));
}
scheduleTime(0, schedules);
StringBuilder sb = new StringBuilder();
System.out.println("count:" + (results.size()));
for (Integer i : results) {
sb.append(time[i] + " ");
}
System.out.print(sb.toString().trim());
}
public static void scheduleTime(int endTime, Schedule[] schedules){
ArrayList<Schedule> list = new ArrayList<Schedule>();
for(Schedule s: schedules){
if(s.start > endTime){
list.add(s);
}
}
if(list.size() > 0){
endTime = findMin(list);
scheduleTime(endTime, schedules);
}
}
public static int findMin(ArrayList<Schedule> list){
int min = list.get(0).end;
int start = list.get(0).start;
int index = list.get(0).index;
for(Schedule s: list){
if(s.end == min){
if(s.start > start){
min = s.end;
start = s.start;
index = s.index;
}
}
if(s.end < min) {
min = s.end;
start = s.start;
index = s.index;
}
}
results.add(index);
return min;
}
}
class Schedule{
public int index;
public int start;
public int end;
Schedule(int index, int start, int end){
this.index = index;
this.start = start;
this.end = end;
}
}
其实写的很不好，没有考虑题目中的最后一种情况，就是如果红包数量一样，要输出开始最晚或者结束最早的。上面的代码我试验了一下，对于一般的情况还是可以的，但是有些就不行了，比如题目中的输入：(1,5) (3,6) (6,7)，按照要求应该是(3,6) (6,7)，可是这个跑出来是(1,5) (6,7)，贪心算法应该不是这个题目的解，先挖个坑，有空改进一下代码，争取AC。
========
Update:2019-10-17
最近又深入理解了一下动态规划，然后跟光哥讨论了一下，觉得这一题应该是用动态规划做，可以求出来最大红包的数量，但是对于红包个数相同的不同情况我还没有什么思路。
========
Update:2019-11-01
最近忙着笔试面试啥的，也没有仔细回过头来看看这道题，之前有了思路，确实是用动态规划，只不过对于每一步存的是当前参加场次的下标。从第一个时间表开始，对于每一个时间表，可以选择参加或者不参加，参加的话红包数就是，能参加的最近的上一场的红包个数加一，不参加就是上一个场次的红包数，对比哪一个更大，哪一个更大选择哪一种方案。但是写出来感觉代码太冗长，应该还有优化的空间。
import java.util.*;
public class Main {
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
Scanner in = new Scanner(System.in);
String input = in.nextLine().trim();
String[] time = input.split(" ");
Schedule[] schedules = new Schedule[time.length];
for (int i = 0; i < time.length; i++) {
String tem = time[i].substring(1, time[i].length() - 1);
String[] tems = tem.split(",");
schedules[i] = new Schedule(i, Integer.parseInt(tems[0]),Integer.parseInt(tems[1]));
}
for(int i = 0 ; i < schedules.length; i++) {
ArrayList<Integer> tem = new ArrayList<>();
if(i == 0) {
tem.add(schedules[i].index);
result.add(tem);
}else {
int j = i - 1;
for(; j >= 0; j--) {
if(schedules[j].end <= schedules[i].start) break;
}
if(j >= 0 && result.get(j).size() + 1 >= result.get(i-1).size()) {
tem.addAll(result.get(j));
tem.add(schedules[i].index);
result.add(tem);
}else if(j < 0){
tem.add(schedules[i].index);
result.add(tem);
}else{
tem = result.get(i-1);
result.add(tem);
}
}
}
StringBuilder sb = new StringBuilder();
int max = result.get(0).size();
int num = 0;
for(int i = 0 ; i < result.size(); i++) {
if(result.get(i).size() > max) {
max = result.get(i).size();
num = i;
}
}else if(result.get(i).size() == max) {
int a = schedules[result.get(i).get(result.get(i).size() - 1)].end;
int b = schedules[result.get(num).get(result.get(num).size() - 1)].end;
if(a < b) {
max = result.get(i).size();
num = i;
}
}
System.out.println("count:" + max);
for (Integer index : result.get(num)) {
sb.append(time[index] + " ");
}
System.out.print(sb.toString().trim());
}
}
class Schedule{
public int index;
public int start;
public int end;
Schedule(int index, int start, int end){
this.index = index;
this.start = start;
this.end = end;
}
}
第三题
由于时间问题大概看了一眼题目，现在已经记不得了，也没做。