中级提升四
题目一：最小路径和
- 题目：
- 暴力递归：
（1）尝试方法：往下或者右的位置一次尝试
（2）basecase的确定：右下角
（3）特殊情况：在最右边，只能往下走；在最下边，只能往右走
public static int minPath(int[][] matrix){ if (matrix == null){ return 0; } return process(matrix, 0, 0); } public static int process(int[][] martix, int x, int y){ if (x == martix.length - 1 && y == martix[0].length - 1){ //basecase return martix[x][y]; } if (x == martix.length - 1){ //最右端，只能往下走 return martix[x][y] + process(martix, x, y + 1); } if (y == martix[0].length - 1){ //最底端 return martix[x][y] + process(martix, x + 1, y); } int right = process(martix, x + 1, y); int down = process(martix, x, y + 1); return martix[x][y] + Math.min(right, down); }
- 动态规划：
（1）两个可变参数，建立二维的dp表
（2）dp表的右下角，以及最右边，和最下边，可以直接确定结果
（3）dp表中的普遍位置依赖关系：由其右边与下边的较小值决定
（4）确定填表顺序，从dp的右下角到左上角
（5）最终位置：dp[0][0]
public static int minPath(int[][] matrix){ if (matrix == null){ return 0; } int[][] dp = new int[matrix.length][matrix[0].length]; dp[matrix.length - 1][matrix[0].length - 1] = matrix[matrix.length - 1][matrix[0].length - 1]; for (int x = matrix.length - 2; x >= 0 ; x--){ //只能往右走 dp[x][matrix[0].length - 1] = dp[x + 1][matrix[0].length - 1] + matrix[x][matrix[0].length - 1]; } for (int y = matrix[0].length - 2; y >= 0 ; y--){ //只能往下走 dp[matrix.length - 1][y] = dp[matrix.length - 1][y + 1] + matrix[matrix.length - 1][y]; } for (int x = matrix.length - 2; x >= 0; x--){ for (int y = matrix[0].length - 2; y >= 0; y--){ dp[x][y] = Math.min(dp[x + 1][y], dp[x][y + 1]) + matrix[x][y]; } } return dp[0][0]; }
题目二：容器装水问题
- 题目：
- 思路：
（1）先找到每一个位置可以容纳水的值，其由左侧的最大值与右侧的最大值决定
（2）单个位置存水量的表达式：max（min（leftMax，rightMax）- 当前位置高度，0）与0比较防止负数的出现
（3）最终将每一个位置加起来，就是其整体的容纳水量
（4）实现过程：leftMax与rightMax数组，存储每个位置左右的最大值，再求每一个位置的存水量
public static int maxWater(int[] arr) { int[] leftMax = new int[arr.length]; int[] rightMax = new int[arr.length]; int sum = 0; int max = Integer.MIN_VALUE; for (int i = 1; i < arr.length; i++) { max = Math.max(max, arr[i - 1]); leftMax[i] = max; } max = Integer.MIN_VALUE; for (int i = arr.length - 2; i >= 0; i--) { max = Math.max(max, arr[i + 1]); rightMax[i] = max; } for (int i = 0; i < arr.length; i++) { sum += Math.max((Math.min(leftMax[i], rightMax[i]) - arr[i]), 0); } return sum; }
- 优化：
（1）不使用leftMax与rightMax数组，只使用两个变量记录最值
（2）使用双下标left，right遍历数组，两边可以通过leftMax与rightMax中，较小的值确定一边的存水量，同时不断更新leftMax与rightMax
public static int maxWater(int[] arr){ int left = 0; int right = arr.length - 1; int leftMax = arr[left]; int rightMax = arr[right]; int sum = 0; while (left < right){ if (leftMax > rightMax){ right--; if (arr[right] < rightMax){ sum += (rightMax - arr[right]); }else { rightMax = arr[right]; } }else { left++; if (arr[left] < leftMax){ sum += (leftMax - arr[left]); }else { leftMax = arr[left]; } } } return sum; }
题目三：分割数组最大值
- 题目：
- 思路：
（1）预处理，得到每个位置左侧与右侧的最大值
（2）按照要求找到最大差值即可
public static int maxDevide(int[] arr) { int[] leftMax = new int[arr.length]; int[] rightMax = new int[arr.length]; int res = 0; int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr[i]); leftMax[i] = max; } max = Integer.MIN_VALUE; for (int i = arr.length - 1; i >= 0; i--) { max = Math.max(max, arr[i]); rightMax[i] = max; } for (int i = 0; i < arr.length; i++) { res = Math.max(res, Math.abs(leftMax[i] - rightMax[i])); } return res; }
- 优化
（1）先找到整个数组的最大值，因为是整体划分成两部分，结果一定是max - 某个数
（2）若max划分到左部分，那么为了使得差值最大，右部分就是最右侧的数
（3）同理，若max划分到右部分，那么为了使得差值最大，左部分就是最左侧的数
（4）找到这两种情况产生的最大值即可
public static int maxDevide(int[] arr) { int leftMax = arr[0]; int rightMax = arr[arr.length - 1]; int max = 0; for (int i : arr){ max = Math.max(max, i); } return Math.max(max - leftMax, max - rightMax); }
题目四：旋转字符串
- 题目：
- 思路：
（1）先判断a，b字符串的长度是否相同，若不相同直接放回false
（2）a = a + a
（3）判断b是否是a的字串，可以使用kmp算法
public static boolean circleString(String a, String b){ if (a.length() != b.length()){ return false; } a = a + a; return kmp(a, b); } public static boolean kmp(String str1, String str2){ if (str1 == null || str2 == null || str1.length() < 1 || str2.length() < 1){ return false; } char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); int index1 = 0; int index2 = 0; int[] next = getNextArray(chs2);//str2的nextArr数组 while (index1 < chs1.length && index2 < chs2.length){ if (chs1[index1] == chs2[index2]){ index1++; index2++; } else if (index2 == 0){ //等同与：else if (next[index2] == -1) //index2回到0位置，且str1仍不匹配，直接使index1移动 index1++; } else { //index2的跳跃，就是对应下标next数组中的值 index2 = next[index2]; } } //判断是否匹配成功 return index2 == chs2.length; } public static int[] getNextArray(char[] str) { if (str.length == 1){ return new int[] {-1}; } //默认，0位置是-1，1位置是1 int[] nextArr = new int[str.length]; nextArr[0] = -1; nextArr[1] = 1; int index = 2; //next数组的位置 int pre = 0; //要比较字符的位置（前缀的下一个）也有前缀长度的含义 while (index < str.length){ if (str[index - 1] == str[pre]){ //index - 1 与 pre 位置相同 //nextArr[index] 就是上一个位置加一 //pre：前缀长度增加 nextArr[index] = nextArr[index - 1] + 1; index++; pre++; } else if (pre > 0){ //不相同，跳到上一个前缀进行比较 pre = nextArr[pre]; }else { //跳到了最前面，也不相同 nextArr[index] = 0; index++; } } return nextArr; }
题目五：咖啡杯问题
- 题目
首先，给你几个数据：
数组arr：表示几个咖啡机，这几个咖啡机生产一杯咖啡所需要的时间就是数组中的值，例如arr=[2,3,7]就表示第一台咖啡机生产一杯咖啡需要2单位时间，第二台需要3单位时间，第三台需要7单位时间。
int N：表示有N个人需要用咖啡机制作咖啡，每人一杯，同时，假设制作完咖啡后，喝咖啡时间为0，一口闷。
int a：表示用洗碗机洗一个咖啡杯需要的时间，串行运行。
int b：表示咖啡杯也可以不洗，自然晾干的时间，咖啡杯要么洗，要么晾干。
现在，请你求出这N个人从开始用咖啡杯制作咖啡到杯子洗好或者晾干的最少时间？
- 思路：
（1）先生成每一个人对应最短时间喝完咖啡的时间drinkTimes
（2）drinkTimes可以通过小根堆的结果获得，小根堆元素由两个元素组成：机器空闲的时间，机器生成一次咖啡的时间。根据二者的和来确定小根堆的比较方式
（3）便可以根据dirnkTimes尝试a，b两个洗杯子的时间，暴力递归得到最小时间
public static class Machine{ //堆中放入的数据类型 public int timePoint; //一个机器可以开始使用的时间 public int workTime; //生成一杯咖啡的时间 public Machine(int t, int w){ timePoint = t; workTime = w; } } public static class MachineComparator implements Comparator<Machine>{ //小根堆的比较器 public int compare(Machine o1, Machine o2){ return (o1.workTime + o1.timePoint) - (o2.workTime + o2.timePoint); } } public static int minTime(int[] arr, int n, int a, int b){ PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator()); for (int i : arr){ //初始的开始时间均为0，机器运行时间在arr中 heap.add(new Machine(0, i)); } int[] drinkTimes = new int[n]; for (int i = 0; i < n; i++){ //使用堆排序填drinkTimes Machine cur = heap.poll(); cur.timePoint += cur.workTime; drinkTimes[i] = cur.timePoint; heap.add(cur); } return process(drinkTimes, a, b, 0, 0); } public static int process(int[] drinkTimes, int a, int b, int index, int washLine){ //washTime：洗咖啡的机器有空的时间 //index：目前遍历到drinkTimes的位置 if (index == drinkTimes.length - 1){ //basecase //使用机器要受机器是否有空的时间控制 return Math.min(Math.max(washLine, drinkTimes[index]) + a, drinkTimes[index] + b); } //选择机器洗，计算时间 int wash = Math.max(washLine, drinkTimes[index]) + a; //洗完剩余咖啡杯最早的结束时间 int next1 = process(drinkTimes, a, b, index + 1, wash); //需要完成所有事情的时间，是由前二者的较大值决定的 int p1 = Math.max(wash, next1); //选择风干 int dry = drinkTimes[index] + b; //风干剩余咖啡杯最早的结束时间 int next2 = process(drinkTimes, a, b, index + 1, washLine); //需要完成所有事情的时间，是由前二者的较大值决定的 int p2 = Math.max(wash, next1); return Math.min(p1, p2); }
题目六：arr数组的特殊要求
- 题目：
- 思路：
（1）将arr中的数分为3类，奇数，因子含4的偶数，因子不含4的偶数，假设个数为a，b，c
（2）因为：奇数 * 奇数为奇数，奇数 * 因子不含4的偶数不满足题意，故奇数一定要与含4的偶数相邻；因子不含4的偶数要与偶数相邻
（3）故我们可以通过三种数字的个数判断arr的要求能否成功 - 情况分析
（1）c == 0：奇 _ 含4因子 _ 奇 _ 含四因子 _ 奇 ； b >= a - 1
（2）c != 0：将不含二因子的偶数放到一起 _ 含4因子 _ 奇 _ 含四因子 _ 奇 ；b >= a - 代码：
public static boolean adjustArr(int[] arr){ int a = 0; int b = 0; int c = 0; for (int i : arr){ if (i % 4 == 0){ b++; }else if (i % 2 == 0){ c++; }else { a++; } } return c == 0 && b >= a - 1 || c != 0 && b >= a; }
题目七：仅用栈实现队列
- 题目：在只有栈的数据结构的情况下，如何实现队列
- 应用：在一些必须使用队列的题目中，只允许使用栈的情况下，可以使用提供的栈，实现队列的功能。例如：使用栈的结构实现图的广度优先遍历
- 思路：
（1）构造两个栈push，pop
（2）每次加入数据时先加入push栈
（3）若要弹出数据先检查pop栈是否为空，若pop栈为空，一次性将push栈中的数据全部加入pop栈，再弹出pop栈的栈顶元素；若pop栈不为空则直接弹出pop的栈顶 - 代码：
public static class TwoStacksQueue{ private Stack<Integer> pushStack; private Stack<Integer> popStack; public TwoStacksQueue(){ pushStack = new Stack<Integer>(); popStack = new Stack<Integer>(); } public void push(int value){ pushStack.push(value); } public int pop(){ if (pushStack.empty() &&popStack.empty()){ throw new RuntimeException("Queue is empty"); } if (popStack.isEmpty()){ while (!pushStack.isEmpty()){ popStack.push(pushStack.pop()); } } return popStack.pop(); } public int peek(){ if (pushStack.empty() &&popStack.empty()){ throw new RuntimeException("Queue is empty"); } if (popStack.isEmpty()){ while (!pushStack.isEmpty()){ popStack.push(pushStack.pop()); } } return popStack.peek(); } }
题目八：仅用队列实现栈
- 题目：在只有队列的数据结构的情况下，如何栈
- 思路：
（1）构造两个队列one，two
（2）每次所有的数据都只在一个队列中
（3）若要加入数据只能加入到目前有数据的一个队列中，若目前两个队列均为空，默认加入队列one
（4）若要弹出数据，先将有数据的队列将除了最后一个全部加入另一个空队列，最后将最后一个元素返回即可 - 代码：
public static class TwoQueueStack{ private Queue<Integer> one; private Queue<Integer> two; public TwoQueueStack(){ one = new LinkedList<Integer>(); two = new LinkedList<Integer>(); } public void push(int value){ if (two.isEmpty()){ one.add(value); }else { two.add(value); } } public int pop(){ int res = 0; if (one.isEmpty() && two.isEmpty()){ throw new RuntimeException("Stack is empty"); }else { if (one.isEmpty()){ while (!two.isEmpty()){ res = two.poll(); if (!two.isEmpty()){ one.add(res); } } }else { while (!one.isEmpty()){ res = one.poll(); if (!one.isEmpty()){ two.add(res); } } } } return res; } }
