一、 给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1) 输入描述: 无序整数数组A[n] 输出描述: 满足条件的最大乘积 示例1 输入 3 4 1 2 输出 24
public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n = sc.nextInt(); /* 两种情况：1、三个数都是正数，取三个最大整数 * 2、两个最小负数和一个最大正数 */ int max[] = new int[3]; int min[] = new int[2]; Arrays.fill(max, Integer.MIN_VALUE); Arrays.fill(min, Integer.MAX_VALUE); for (int i = 0; i < n; i++) { int cur = sc.nextInt(); if(cur > max[0]) { max[2] = max[1]; max[1] = max[0]; max[0] = cur; } else if(cur > max[1]) { max[2] = max[1]; max[1] = cur; } else if(cur > max[2]) { max[2] = cur; } if(cur < min[0]) { min[1] = min[0]; min[0] = cur; } else if(cur < min[1]) { min[1] = cur; } } System.out.println(Math.max((long)min[0]*min[1]*max[0], (long)max[0]*max[1]*max[2])); sc.close(); } }二、 有两个用字符串表示的非常大的大整数,算出他们的乘积，也是用字符串表示。不能用系统自带的大整数类型。 输入描述: 空格分隔的两个字符串，代表输入的两个大整数 输出描述: 输入的乘积，用字符串表示 示例1 输入 72106547548473106236 982161082972751393 输出 70820244829634538040848656466105986748
public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String a = sc.next(); String b = sc.next(); sc.close(); int result[] = new int[a.length() + b.length()];//两个数相乘，结果的位数必小于两个数位数之和 int n = a.length(); int m = b.length(); a = new StringBuilder(a).reverse().toString(); b = new StringBuilder(b).reverse().toString(); for(int i = 0; i < n; i++) {//先算没有进位的两个数相乘 for(int j = 0; j < m; j++) { result[i + j] += (a.charAt(i) - '0') * (b.charAt(j) - '0'); } } StringBuffer sb = new StringBuffer(); for(int i = 0; i < result.length; i++) {//处理进位问题 int remain = result[i] % 10; int carry = result[i] / 10; sb.append(remain); if(i < result.length - 1) {//防止数组越界 result[i + 1] += carry; } } sb.reverse();//处理顺序是尾部在头，所以应该反转 while(sb.length() > 0 && sb.charAt(0) == '0') {//result数组长度可能稍大，最后几个数为0 sb.deleteCharAt(0); } System.out.println(sb.toString()); } }三、 六一儿童节，老师带了很多好吃的巧克力到幼儿园。 每块巧克力j的重量为w[j]，对于每个小朋友i，当他分到的巧克力大小达到h[i] (即w[j]>=h[i])，他才会上去表演节目。 老师的目标是将巧克力分发给孩子们，使得最多的小孩上台表演。可以保证每个w[i]> 0且不能将多块巧克力分给一个孩子或将一块分给多个孩子。 输入描述: 第一行：n，表示h数组元素个数 第二行：n个h数组元素 第三行：m，表示w数组元素个数 第四行：m个w数组元素 输出描述: 上台表演学生人数 示例1 输入 3 2 2 3 2 3 1 输出 1
public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n = sc.nextInt(); int h[] = new int[n]; for(int i = 0; i < n; i++) { h[i] = sc.nextInt(); } int m = sc.nextInt(); int w[] = new int[m]; for(int i = 0; i < m;i++) { w[i] = sc.nextInt(); } sc.close(); //给需求最少的人最小的巧克力 Arrays.sort(h); Arrays.sort(w); int res = 0; for(int i = m - 1, j = n - 1; i >= 0 && j >= 0; j--) { if(w[i] >= h[j]) { res++; i--; } }System.out.println(res); } }四、 假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。 迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。 迷宫之中有的路上还有门，每扇门都在迷宫的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。 请设计一个算法，帮助探险家找到脱困的最短路径。 如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0-墙，1-路，2-探险家的起始位置，3-迷宫的出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙 输入描述: 迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N 后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。 输出描述: 路径的长度，是一个整数 输入 5 5 02111 01a0A 01003 01001 01111 输出 7
class Point { int x; int y; int key; public Point(int x, int y, int key) { this.x = x; this.y = y; this.key = key; } } public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); char map[][] = new char[m][n]; sc.nextLine(); for (int i = 0;i<m;i++){ map[i] = sc.nextLine().toCharArray(); } sc.close(); //迷宫问题一般都是用dfs。本题和一般的迷宫问题差别在找钥匙 int startx = 0, starty = 0, endx = 0, endy = 0; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(map[i][j] == '2') {//找起点 startx = i; starty = j; } if(map[i][j] == '3') {//找终点 endx = i; endy = j; } } } System.out.println(bfs(map, m, n, startx, starty, endx, endy)); } private static int bfs(char[][] map, int m, int n, int startx, int starty, int endx, int endy) { Queue<Point> q = new LinkedList<>(); int dir[][] = {{0,1}, {0,-1}, {1,0}, {-1,0}};//每行一个方向 int[][][] keys = new int[m][n][1024];//keys存路径长度。最多10把钥匙，用十个01串存获取钥匙情况 for (int i = 0;i < m; i++){ for (int j = 0;j < n; j++){ for (int s = 0;s < 1024; s++){ keys[i][j][s] = -1;//初始化为-1表示未走过 } } } q.add(new Point(startx, starty, 0)); keys[startx][starty][0] = 0; while (!q.isEmpty()){ Point next = q.poll(); int x = next.x; int y = next.y; int key = next.key; if (x == endx && y == endy) {//走到终点 //每遍历一层路径都加1，所以最先到达终点的可认为路径最短 return keys[x][y][key]; } for (int i = 0; i < 4; i++){ x = next.x + dir[i][0]; y = next.y + dir[i][1]; key = next.key; if(x < 0 || x >= m || y < 0 || y >= n || map[x][y] == '0') {//走出界或走到墙 continue; } if(keys[x][y][key] != -1) {//当前路径走过 continue; } if(map[x][y] >= 'a' && map[x][y] <= 'z'){//走到钥匙 key = key | (0x1 << (map[x][y] - 'a')); } if (map[x][y] >= 'A' && map[x][y] <= 'Z'){//走到门 if((key & (0x1 << (map[x][y] - 'A'))) <= 0){//没有钥匙 continue; } } keys[x][y][key] = keys[next.x][next.y][next.key]+1;//标记是否走过，MAX表示未走过 q.add(new Point(x,y,key)); } } return -1; } }