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