中级提升一
题目一：绳子覆盖点问题（滑动窗口）
- 题目；
- 思路一：枚举 + 贪心
将绳子右端放在arr[]数组的每一个端点上，依次尝试得到最大值
- 例：
arr数组如下，L为5
当绳子的右端点来到0位置，2 - 5 = - 3，前面没有覆盖，只覆盖了0位置的一个点
当绳子的右端点来到1位置，4 - 5 = - 1，找最左侧端点，0位置的2，故覆盖2个端点
当绳子端点来到3位置，9 - 5 = 4，最左侧为1位置，故从1 ~ 3，覆盖3个点
- 思路二：滑动窗口
（1）左右指针（l，r）
（2）l每次从最左端点开始，r到达下一个端点，
（3）r - l 是否 < L，若小于，点数加一，移动r，继续判断；若大于，则直接移动l - 例：
l 在0位置时，r可以移动一次到达1位置，覆盖2个点
l 移动到1位置与 r相遇， 此时r可以连续移动2次到达3位置，覆盖3个点
- 时间复杂度分析：数组大小为N
（1）思路一：若采用二分发查找每次可以覆盖的位置，O（N * logN）
（2）思路二：只用将 l 指针在数组遍历一遍，O（N） - 代码实现
思路一： public static int maxPoint(int[] arr, int L){ int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++){ //每个点均作为绳子的最右端 max = Math.max(max, process(arr, L, i)); } return max; } public static int process(int[] arr, int L, int index){ //index最右端 int point = 1; //点数的记录 int pre = arr[index] - L; while (index - 1 >= 0 && arr[--index] >= pre){ //index - 1 >= 0 防止越界 point++; } return point; }
思路二： public static int maxPoint(int[] arr, int L){ int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++){ //每个点均作为绳子的最左端，l指针移动 max = Math.max(max, process(arr, L, i)); } return max; } public static int process(int[] arr, int L, int l){ int point = 1; //点数的记录 int r = l + 1; while (r < arr.length && arr[r] - arr[l] <= L){ //r指针移动 point++; r++; } return point; }
题目二：装袋子问题（打表法）
打表法：只有一个输入和输出，通过观察结果总结规律，得到技巧
- 题目：
- 思路：
（1）若n为奇数一定不行，直接返回 -1
（2）贪心策略：使用最多的8类型的袋子
（3）n / 8，得到袋子数后，检查剩余的苹果能否被6的袋子装下，若能，则成功；若不能，减少8类型的袋子，分给6类型的袋子进行测试 - 例：
若 n = 100，100 / 8 = 12，剩余4个，6类型无法装下，12 - 1 = 11，4 + 8 = 12，6类型可以装下，尝试成功 - 优化：
在对剩余苹果能否被6类型袋子装下进行优化判断，若剩余的个数已经超过24（6与8的最小公倍数）则剩余个数再次增加，也不肯能装下，便可提前结束判断。
解析：若剩余为x > 24，x = 24 + y = 3 * 8 + y；那么可以判断，24能由8类型解决，而剩余的y一定在前面就判断过不能被6类型的袋子装下
public static int minBags(int apple){ if (apple < 0 || apple % 2 != 0){ //一定不成功的情况 return -1; } int bag8 = apple / 8; int bag6 = 0; int rest = apple - bag8 * 8; //剩余个数 while (bag8 >= 0 && rest <= 24){ //将8的给了6 if (rest % 6 == 0){ bag6 = rest / 6; return bag8 + bag6; } bag8--; rest += 8; } return -1; }
- 打表法：只有一个输入，一个输出，直接观察结果
通过结果可以看出，前16个每有规律可以一一列举出来，从第17个开始每八个数为一组，偶数为3，4，5……，奇数全部是负一
那么我们无需计算，通过输入数子，便可以直接得出答案
public static int minBags(int apple){ if (apple < 0 || apple % 2 != 0){ //一定不成功的情况 return -1; } if (apple <= 16){ //小于16的一一对应输出 if (apple == 0){ return 0; } if (apple == 6 || apple == 8){ return 1; } if (apple == 12 || apple == 14 || apple == 16){ return 2; } return -1; } return (apple - 17) / 8 + 3; }
题目三：吃草问题（打表法）
- 题目：
假设现在有两只动物吃草，每次只能吃4的次幂的草，也就是1、4、16等等，现在，给你一个整数N，代表总共有多少草，两只动物，只能交替吃草，有先手和后手区别，假设动物都绝顶聪明，哪只动物先吃完草，哪只就赢，请你求出N份草时，是先手赢还是后手赢？
- 思路：
（1）先手占据主动权，所以只要对于N份草，只要先手有机会赢，一定可以成功
（2）那么，可以让先手尝试所有的可能，若尝试均不成功，则后手成功
（3）使用递归函数表示，不断进行缩小规模，进行先后手的尝试
（4）basecase，若N <= 0，无意义，若N = 1先手赢，N = 2 后手赢，N = 3 先手赢，N = 4 先手赢 - 代码实现：
public static String win(int N){ if (N <= 0){ return "输入错误"; } if (N <= 4){ //basecase return N == 2 ? "后手赢" : "先手赢"; } int num = 1; //目前尝试的数值 while (num <= N){ if (win(N - num).equals("后手赢")){ //若递归的后手赢，则代表目前的先手赢 return "先手赢"; } if (num > N / 4){ //越界 break; } num *= 4; } //最后情况，先手无法获胜，只可能后手赢 return "后手赢"; }
- 打表法：规律总结
处了0以外，其余能除以5余数为：2或是0的，结果均是后手
public static String win(int N){ if (N <= 0){ return "输入错误"; } if (N % 5 == 2 || N % 5 == 0){ return "后手赢"; } return "先手赢"; }
题目四：涂染问题（预处理）
预处理：空间换时间，总结待处理数据的规律，减少时间复杂度
- 题目：
- 思路：(枚举）分为左右侧，左侧全部是R，右侧全部是G，从左侧0个到左侧全部
例：s = RGRGR
（1）左侧0个：GGGGG，3个
（2）左侧1个：RGGGG，2个
（3）左侧2个：RRGGG，3个
（4）左侧3个：RRRGG，2个
（5）左侧4个：RRRRG，3个
（6）左侧5个：RRRRR，2个
时间复杂度：O(N ^ 2)
public static int minPaint(String s){ if (s == null || s.length() < 2){ return 0; } char[] chs = s.toCharArray(); int min = chs.length; for (int index = 0; index <= chs.length; index++){ //目前左侧区域的大小，类似于分界线 int test = 0; for (int i = 0; i < chs.length; i++){ //遍历字符串 if (i < index){ //左侧 if (chs[i] == 'G'){ test++; } } else if (chs[i] == 'R'){ //右侧 test++; } } min = Math.min(min, test); } return min; }
- 优化：预处理，时间复杂度O（N）
（1）通过左侧分界线得到对应的左，右侧分别有几个需要染色，得到两个数组
（2）例如s = RGRGR，left[]：左边几个G，right[]：右侧几个R
left = [0，0，1，1，2，2]
right = [3，2，2，1，1，0]
（3）将left与right对应位置相加，取最小值
public static int minPaint(String s){ if (s == null || s.length() < 2){ return 0; } char[] chs = s.toCharArray(); int min = chs.length; int[] left = new int[chs.length + 1]; int[] right = new int[chs.length + 1]; int num = 0; for (int index = 0; index < chs.length; index++){ //目前左侧区域的大小 if (chs[index] == 'G'){ num++; } //left要错位设置 left[index + 1] = num; } num = 0; for (int index = chs.length - 1; index >= 0; index--){ //目前左侧区域的大小 if (chs[index] == 'R'){ num++; } //right的最后一个不用设置，一定为0 right[index] = num; } for (int index = 0; index < left.length; index++){ min = Math.min(min, left[index] + right[index]); } return min; }
题目五：最大正方形（预处理）
- 题目：
- 思路：
（1）N * N的矩阵能产生多少种子矩阵，矩阵产生任意一个点为O(N ^ 2)，任意两个点，分别作为子矩阵的左上角与右下角，便可确定一个矩阵，虽然会有重复，但是时间复杂度的数量级为O(N ^ 4)
（2）N * N的矩阵能产生多少种子正方形矩阵，矩阵产生任意一个点为O(N ^ 2)，使得该点为左上角，边长的取值可以从1 ~ N（边长根据矩阵的大小限制），故时间复杂度的数量级为O(N ^ 3)
（3）那么通过（2）的思路，便可以遍历通过每一个点形成的正方形的边长大小，判断正方形的四条边是否全部为1
public static int maxSquare(int[][] matrix){ int max = Integer.MIN_VALUE; for (int row = 0; row < matrix.length; row++){ for (int col = 0; col < matrix[0].length; col++){ //确定左上角点 int num = 0; for (int border = 1; border < Math.min(matrix.length - row, matrix[0].length - col); border++){ //边长的确定，行和列最小的限制边长的最大值 boolean flag = true; if (matrix[row][col] == 0){ break; } //四条边的检测 for (int i = row; i < row + border; i++){ if (matrix[i][col] == 0) { flag = false; break; } } for (int i = col; i < col + border; i++){ if (matrix[row][i] == 0) { flag = false; break; } } for (int i = row; i <= row + border; i ++){ if (matrix[i][col + border] == 0) { flag = false; break; } } for (int i = col; i <= col + border; i++){ if (matrix[row + border][i] == 0) { flag = false; break; } } if (flag){ num = border; } } max = Math.max(max, num); } } //包括开始位置，边长加一 return max + 1; }
时间复杂度：O(N ^ 4)，因为要判断四条边，时间复杂度上升
- 优化：预处理
（1）准备right数组，与down数组规模与原数组相同
（2）right数组：表示该数字位置的右方有几个连续的1，数组从右下角开始，从右往左，再从下往上依次填写
（3）down数组：表示该数字位置的下方有几个连续的1，数组从右下角开始，从下往上，再从右往左
（4）四条边的判断可以通过数组种的right[右上角点]，right[右下角]，down[右上角]，down[左上角]进行判断
（5）这样便可以减少一层for循环，将时间复杂度优化为O(N ^ 3)
public static int maxSquare(int[][] matrix){ int max = Integer.MIN_VALUE; int[][] right = new int[matrix.length][matrix[0].length]; int[][] down = new int[matrix.length][matrix[0].length]; for (int row = matrix.length - 1; row >= 0; row--){ int num = 0; for (int col = matrix[0].length - 1; col >= 0; col--){ if (matrix[row][col] == 1){ num++; right[row][col] = num; } } } for (int col = matrix[0].length - 1; col >= 0; col--){ int num = 0; for (int row = matrix.length - 1; row >= 0; row--){ if (matrix[row][col] == 1){ num++; down[row][col] = num; } } } for (int row = 0; row < matrix.length; row++){ for (int col = 0; col < matrix[0].length; col++){ //确定左上角点 int num = 0; for (int border = 1; border < Math.min(matrix.length - row, matrix[0].length - col); border++){ //边长的确定，行和列最小的限制边长的最大值 boolean flag = true; if (matrix[row][col] == 0){ break; } if (right[row][col] < border || down[row][col] < border || right[row + border][col] < border || down[row][col + border] < border){ //四条边的检测 flag = false; } if (flag){ num = border; } } max = Math.max(max, num); } } //包括开始位置，边长加一 return max + 1; }
题目六：随机数
- 题目：
- 思路：
（1）要扩大原随机数的范围，可通过二进制的转化实现
（2）创建中间函数将 f 产生的1，2作为0；4，5作为1；3重新尝试，即将 f 函数的结果转化为0或1
（3）1 ~ 7可以通过3位二进制表示，g调用3次 f 分别产生3个位置对应的数字，若产生0，重新调用
public static int f(){ return (int)(Math.random() * 5) + 1; } public static int temp(){ //中间函数，将f函数的结果转化为0 / 1 int res; do { res = f(); }while (res == 3); return res < 3 ? 0 : 1; } public static int g(){ int res; do { res = temp() * 4 + temp() * 2 + temp(); }while (res == 0); return res; }
- 题目
- 思路：
（1）使用 f 连续产生二个数字组合
（2）若为00或是11，重新产生
（3）若是01，产生1；若是10，产生0；使得两者概率相同
