美团8.13笔试
第一题、int数组，时间t代表送货的平均时间，nums[i]代表订单的最晚截止时间， 问有几个订单不能按时送到。
例：t=5,【5，6，7，8，9，10】，5满足，10满足，答案：4，因为，第二次送货时间是10，所以6，7，8，9不满足。
解答情况：27%，我怀疑我理解错题意了。
思路：模拟
解法：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), t = sc.nextInt();
int[] nums = new int[n];
int res = 0, cnt = 1;
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
if (nums[i] < cnt * t) {
res++;
} else {
cnt++;
}
}
System.out.println(res);
} 第二题、机器人打扫房间。一个int型矩阵，给出一系列指令，可以向上下左右打扫。打扫完成输出Yes和用了几条指令，没完成输出No和还有几个单元没完成。
例：2*2矩阵，初始站在00位置，指令是WSWS，答案：No，2
解答情况：过了81%，解答错误。
思路：暴力
时空复杂度：n，1
解法：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
String instructions = sc.next();
HashSet<String> set = new HashSet<>();
int[][] matrix = new int[n][m];
int curX = 0, curY = 0;
matrix[curX][curY] = 1;
int num = 0;
for (int i = 0; i < instructions.length(); i++) {
if (instructions.charAt(i) == 'W') {
curX = curX - 1;
} else if (instructions.charAt(i) == 'S') {
curX = curX + 1;
} else if (instructions.charAt(i) == 'A') {
curY = curY - 1;
} else if (instructions.charAt(i) == 'D') {
curY = curY + 1;
}
matrix[curX][curY] = 1;
StringBuilder sb = new StringBuilder();
sb.append(curX);
sb.append(curY);
set.add(new String(sb));
if (set.size() == n * m) {
num = i;
break;
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
res++;
}
}
}
if (res == 0) {
System.out.println("Yes\n" + num);
} else {
System.out.println("No\n" + res);
}
} 第三题、模拟，将数组中首部的数放到尾部，重复两次，然后删除第一个元素，直到没有元素。给你结果，还原这个数组。 例：【1，2，3，4】，答案：【4，2，1，3】
解答情况：过了81%，解答错误。
思路：逆向思维。倒序。添加元素，将数组中尾部的元素放到首部，重复两次。
第一次：放入【4】，
第二次：放入3，【3，4】，removeLast（），addFirst（），removeLast（），addFirst（），还是【3，4】
第三次：放入2，【2，3，4】，。。。，【3，4，2】
第四次：放入1，【1，3，4，2】，。。。，【4，2，1，3】
时空复杂度：n，n
解法：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
LinkedList<Integer> list = new LinkedList<>();
for (int i = nums.length - 1; i >= 0; i--) {
list.addFirst(nums[i]);
Integer last = list.removeLast();
list.addFirst(last);
Integer secondeLast = list.removeLast();
list.addFirst(secondeLast);
}
for (Integer integer : list) {
System.out.println(integer);
}
} 第四题、求三元组，满足i<j<k&&nums【i】-2nums【j】=2*nums【j】-nums【k】
思路：暴力
解答情况：81%，超时
时空复杂度：n3，1
解法：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int res = 0;
for (int i = 0; i < n - 2; i++) {
int a = nums[i];
for (int j = i + 1; j < n - 1; j++) {
int b = nums[j];
for (int k = j + 1; k < n; k++) {
int c = nums[k];
if (a - b == 2 * b - c) {
res++;
}
}
}
}
System.out.println(res);
} 第五题、节点之和最大的路径
例：【1，2，3】，root=1，left=2，right=3，最大和是4.
解答情况：ac。
思路：力扣原题
时空复杂度：n，n
解法：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n+1];
for (int i = 1; i <= n; i++) {
nums[i] = sc.nextInt();
}
int res = traverse(1, nums);
System.out.println(res);
}
private static int traverse(int index, int[] nums) {
if (index < 0 || index >= nums.length) {
return 0;
}
int left = traverse(index * 2, nums);
int right = traverse(index * 2 + 1, nums);
return Math.max(left, right) + nums[index];
} 
