题目一：绳子覆盖点问题题目二：装袋子问题题目三：吃草问题 题目一：绳子覆盖点问题
题目；
思路一：枚举 + 贪心
将绳子右端放在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 "先手赢"; }