01-玩家选数-括号配对-数组累加和
2019-07-30 本文已影响0人
囧么肥事
年轻即出发...
简书：https://www.jianshu.com/u/7110a2ba6f9e
知乎：https://www.zhihu.com/people/zqtao23/posts
GitHub源码：https://github.com/zqtao2332
个人网站：http://www.zqtaotao.cn/ （停止维护更新内容）
QQ交流群：606939954
咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。
最后：喜欢编程，对生活充满激情
本节内容预告
实例1：玩家选数问题
实例2：有效括号配对问题
实例3：数组累加和问题1
实例4：数组累加和问题2
实例5：数组累加和问题3
实例1：玩家选数问题
有一排正数，玩家A和玩家B都可以看到。
每位玩家在拿走数字的时候，都只能从最左和最右的数中选择一个。
玩家A先拿，玩家B再拿，两人交替拿走所有的数字，
两人都力争自己拿到的数的总和比对方多。请返回最后获胜者的分数。
例如：
5,2,3,4
玩家A先拿，当前他只能拿走5或者4。
如果玩家A拿走5，那么剩下2，3，4。轮到玩家B，此时玩家B可以选择2或4中的一个，…
如果玩家A拿走4，那么剩下5，2，3。轮到玩家B，此时玩家B可以选择5或3中的一个，…
思路1、递归: 暴力尝试
自己分别作为先选人，后选人，查看收益最大
无论是作为先选人，还是作为后选人，都是绝对理智的，每一次做出的选择都是最优的
具体过程见代码详解
1_1_递归过程依赖图.png
/**
* @description: 两人选数游戏
* 思路1、递归: 暴力尝试
* @version: 1.0
*/
public class Code_01_CardsInLine_1 {
// 方式1、递归: 暴力尝试
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) return 0;
// 自己分别作为先选人，后选人，查看收益最大
// 无论是作为先选人，还是作为后选人，都是绝对理智的，每一次做出的选择都是最优的
return Math.max(first(arr, 0, arr.length - 1), second(arr, 0, arr.length - 1));
}
/*
作为先选人，从 i 到 j 位置上获得的最大分数
核心：我作为先选人每一次决策都是选择的最优的
如：
5 2 3 4
那么我作为先选者一定最终做出的选择的是 （5 + 作为后选人最大分数）（4 + 作为后选人最大分数）中最大分数的
*/
public static int first(int[] arr, int i, int j) {
if (i == j) { // 只有一个数，同时作为先选人，当然返回这个唯一的数
return arr[i];
}
// 选择左边数，然后自己变成了后选人
// 从 i 到 j 位置上获得的最大分数 = 左边数 + 自己变为后选人从 i+1 到 j 位置上获得的最大分数
int L = arr[i] + second(arr, i + 1, j);
// 选择右边数，然后自己变成了后选人
// 从 i 到 j 位置上获得的最大分数 = 右边数 + 自己变为后选人从 i 到 j-1 位置上获得的最大分数
int R = arr[j] + second(arr, i, j - 1);
// 返回自己选择左边数和选择右边数两种情况下，最大的分数
return Math.max(L, R);
}
/*
作为后选人，从i 到 j 位置上获得的最大分数
核心：每一次都认为先选人做出的选择是最优的，留给自己的一定是最小的
5 2 3 4
先选人，选了 5 给自己留下 2 3 4 = 9
先选人，选了 4 给自己留下 5 2 3 = 10
先选人怎么可能那么好心让自己赢，我们都是绝对理智的人
所以
我作为后选人，悲催的只能在先选人选择后的区域选择我的数
但是我现在也不知道那边的数大，需要计算才能知道先选人选择的到底是哪边的数？
5 2 3 4
先选人，选了 5 给自己留下 2 3 4 = 9
先选人，选了 4 给自己留下 5 2 3 = 10
通过计算发现，9 < 10 ，先选人既然是绝对理智的，那么他给我留下的就是最小的
而我，只能从最小的那几个数中找最大的分数。
由于先选人已经选择了，现在他退位到后选人，我上了先选人位置，即，我现在是先选人。
总结: 我作为后选人做出什么样的决定，完全取决于先选人做出了什么决定，先选人扔给我的一定是最小的
*/
public static int second(int[] arr, int i, int j) {
if (i == j) { //只有一个数，自己作为后选人，自己前面有一个先选人，先选人选择后，剩下0个数可选
return 0;
}
// 现在我是先选人，选择左边数
int L = first(arr, i + 1, j);
// 现在我是先选人，选择右边数
int R = second(arr, i, j - 1);
// 我只能从最小的区域中进行选择
return Math.min(L, R);
}
}
思路2：从暴力递归到动态规划
暴力递归其实就是一个暴力尝试过程，尝试每一种选择
缺点：重复的大量计算，而且这种重复计算随着样本量的增加而指数式增加，做了很多无用功
暴力递归到动态规划的一般步骤
动态规划：
1、写出暴力尝试
2、确定最终解，是什么点
3、查看暴力尝试过程中的计算解，是否是完全无后效性的
4、找到可以代替解的变量
5、base case 给表赋值
6、一般情况的依赖关系
根据题具体分析
1、暴力尝试：win1()
2、确定最终解：(0, N-1) 点
3、win1() 中 f(arr, i, j) arr 是固定值，f(i , j) 是无效性的
4、可以用 i , j 表示解
5、根据递归中的base case 来给表赋值（不变值，基本情况下的值，如本题 i==j 时）
6、一般情况下的依赖关系
first() (i,j) 依赖于second() 中的 (i+1, j) 和 (i, j-1)
second() (i,j) 依赖于 first() 中的 (i+1,j) 和 (i, j-1)
1_2_fs依赖关系.png
import static cn.zqtao.learn.nowcode_other.day1.Code_01_CardsInLine_1.win1;
/**
* @description: 两人选数游戏
* 思路2：从暴力递归到动态规划
* <p>
* 暴力递归其实就是一个暴力尝试过程，尝试每一种选择
* 缺点：重复的大量计算，而且这种重复计算随着样本量的增加而指数式增加，做了很多无用功
* <p>
* 动态规划：
* 1、写出暴力尝试
* 2、确定最终解，是什么点
* 3、查看暴力尝试过程中的计算解，是否是完全无后效性的
* 4、找到可以代替解的变量
* 5、base case 给表赋值
* 6、一般情况的依赖关系
* <p>
* 1、暴力尝试：win1()
* 2、确定最终解：(0, N-1) 点
* 3、win1() 中 f(arr, i, j) arr 是固定值，f(i , j) 是无效性的
* 4、可以用 i , j 表示解
* 5、根据递归中的base case 来给表赋值（不变值，基本情况下的值，如本题 i==j 时）
* 6、一般情况下的依赖关系
* first() (i,j) 依赖于second() 中的 (i+1, j) 和 (i, j-1)
* second() (i,j) 依赖于 first() 中的 (i+1,j) 和 (i, j-1)
* <p>
* <p>
* 暴力尝试可以使用表进行表示
* dpf 可以保存所有 first() 的所有情况
* dps 可以保存所有 second() 的所有情况
* <p>
* first() 中
* @version: 1.0
*/
public class Code_02_CardsInLine_2 {
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) return 0;
// 保存各种状态
int[][] dpf = new int[arr.length][arr.length];
int[][] dps = new int[arr.length][arr.length];
for (int j = 0; j < arr.length; j++) {
dpf[j][j] = arr[j]; // first() 中 base case 中 i==j 情况赋值
// dps[j][j] = 0; // second() 中 base case 中 i==j 情况，由于Java是自动给数组初始化为0 的所以可以忽略
for (int i = j - 1; i >= 0; i--) {
// 一般情况依赖关系
// first() (i,j) 依赖于second() 中的 (i+1, j) 和 (i, j-1)
dpf[i][j] = Math.max(arr[i] + dps[i + 1][j], arr[j] + dps[i][j - 1]);
// second() (i,j) 依赖于 first() 中的 (i+1,j) 和 (i, j-1)
dps[i][j] = Math.min(dpf[i + 1][j], dpf[i][j - 1]);
}
}
return Math.max(dpf[0][arr.length - 1], dps[0][arr.length - 1]);
}
public static int[] generateRandomArr(int maxSize, int maxValue) {
int[] arr = new int[(int) (Math.random() * (maxSize + 1))];
return arr;
}
public static void main(String[] args) {
int maxSize = 5;
int testTime = 50000;
for (int i = 0; i < testTime; i++) {
int[] arr = generateRandomArr(maxSize, 20);
int r1 = win1(arr);
int r2 = win2(arr);
if (r1 != r2) {
System.out.println("error");
}
}
}
}
实例2：有效括号配对问题
1、已知一个字符串都是由左括号(和右括号)组成，判断该字符串是否是有效的括号组合。
例子：
有效的括号组合:()(),(()),(()())
无效的括号组合:(,()),((),()(()
2、题目进阶：
已知一个字符串都是由左括号(和右括号)组成，返回最长有效括号子串的长度。
1思路：
1、临时变量count
2、"(" count+1
")" count-1 每次判断count < 0 返回false
3、最终遍历完成，count != 0 false
// 是否是有效括号
public static boolean isValidParentheses(String str) {
if (str == null || "".equals(str)){
return false;
}
char[] chars = str.toCharArray();
int count = 0;
for (int i = 0; i < chars.length; i++) {
if (")".equals(chars[i]) && --count < 0){
return false;
}
if ("(".equals(chars[i])) {
count++;
}
}
return count == 0;
}
进阶思路
动态规划
）（）（）（（）（））
2_1_最长有效括号子串.png
// 有效最大长度
public static int maxLength(String str) {
if (str == null || "".equals(str)) {
return 0;
}
char[] chars = str.toCharArray();
int res = 0;
int[] dp = new int[chars.length];
int pre = 0; // 和当前 ')' 对应的 '('的位置下标
for (int i = 1; i < chars.length; i++) { // 无论是什么括号，dp[0] 一定是0
if (')' == chars[i]) {
pre = i - dp[i - 1] - 1; // 根据第 i-1 位，进行前推 dp[i-1] - 1 个
if (pre >= 0 && chars[pre] == '(') {
int preLenth = pre > 0 ? dp[pre - 1] : 0; // 之前有效的长度, 注意：pre <= 0 的存在
dp[i] = (dp[i - 1] + 2) + preLenth;
}
}
res = Math.max(dp[i], res);
}
return res;
}
实例3：数组累加和问题1
1、给定一个数组，值全是正数，请返回累加和为给定值k的最长子数组长度。
思路：滑动窗口
双指针 L R 分别控制窗口进元素和出元素
public static int maxSubArrLen(int[] arr, int k) {
if (arr == null || arr.length == 0) return 0;
int L = 0;
int R = 0;
int sum = arr[R];
int len = 0;
while (R < arr.length) {
if (sum == k) {
len = Math.max(len, R - L + 1);
sum -= arr[L++];
} else if (sum < k) {
R++;
if (R == arr.length) break; // 防止越界
sum += arr[R];
} else {
sum -= arr[L++];
}
}
return len;
}
实例4：数组累加和问题2
2、给定一个数组，值可以为正、负和0，请返回累加和为给定值k的最长子数组长度。
注意：子数组，子串等问题，常规套路：
选择以某个位置开始怎么怎么样, 或者选择以某个位置结束怎么怎么样！！
即选择子串开始位置考虑，或者选择子串结束位置考虑。
通过其他位置来推此位置时的状态
此题，以某个位置为结尾的子数组，累加和为定值 k
public static int maxSubArrLen(int[] arr, int k) {
if (arr == null || arr.length == 0) return 0;
int len = 0;
int sum = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // 处理第一位等于 k 的情况
/*
6 1 2 3 k = 6
上来 sum = 6
sum - k = 0;
len = i - map.get(0) 但是现在不存在map.get(0) 这样len返回的结果是0，而不是 1
*/
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (map.containsKey(sum - k)) {
len = Math.max(len, i - map.get(sum - k));
}
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return len;
}
实例5：数组累加和问题3
3、给定一个数组，值可以为正、负和0，请返回累加和小于等于k的最长子数组长度。
import java.util.Arrays;
import java.util.HashMap;
/**
* @description: 数组累加和问题3
*
* 3、给定一个数组，值可以为正、负和0，请返回累加和小于等于k的最长子数组长度。
* @version: 1.0
*/
public class Code_04_3_LongestSumSubArrayLengthInPositiveArray {
/**
* 第一步：求得 以arr[i] 开头的情况下，往后累加，能得到的最小和是多少？存进 sums
* 以arr[i] 开头累加出最小和，边界时多少？存进ends
*
* 第二步：遍历数组，求以a[i] 为开头，累加和 <=k 的子数组
*
* 无注释版
*/
public static int maxLengthAwesome(int[] arr, int k) {
if (arr == null || arr.length == 0) {
return 0;
}
int[] sums = new int[arr.length];
HashMap<Integer, Integer> ends = new HashMap<>();
// 第一步
sums[arr.length - 1] = arr[arr.length - 1];
ends.put(arr.length - 1, arr.length - 1);
for (int i = arr.length - 2; i >= 0; i--) {
if (sums[i + 1] < 0) {
sums[i] = arr[i] + sums[i + 1];
ends.put(i, ends.get(i+1));
} else {
sums[i] = arr[i];
ends.put(i, i);
}
}
// 第二步: 采用滑动窗口
int end = 0;
int sum = 0;
int resLen = 0;
for (int i = 0; i < arr.length; i++) {
while (end < arr.length && sum + sums[end] <= k) {
sum += sums[end];
end = ends.get(end) + 1;
}
sum -= end > i ? arr[i] : 0;
resLen = Math.max(resLen, end - i);
end = Math.max(end, i + 1);
}
return resLen;
}
// 注释版
public static int maxLengthAwesome2(int[] arr, int k) {
if (arr == null || arr.length == 0) {
return 0;
}
int[] sums = new int[arr.length];
// key: 第i位数下标 value: 第i位数开头的情况下累加最小和的右边界
HashMap<Integer, Integer> ends = new HashMap<>();
// 以arr[i] 开头的情况下，往后累加，能得到的最小和是多少？存进 sums
// 以arr[i] 开头累加出最小和，边界时多少？存进ends
// 最后一个数的最小累加和，就是本身
sums[arr.length - 1] = arr[arr.length - 1];
// 右边界时最后一个数的下标
ends.put(arr.length - 1, arr.length - 1);
// 遍历数组，求以arr[i] 开头情况下，往后累加，能得到的最小和是多少？存进sums
// 右边界存进 ends
for (int i = arr.length - 2; i >= 0; i--) {
if (sums[i + 1] < 0) { // 对于arr[i] 如果以 arr[i+1] 开头求得的最小和 < 0
sums[i] = arr[i] + sums[i + 1]; // arr[i] 开头的最小和=当前数+以arr[i+1]开头累加的最小和
ends.put(i, ends.get(i + 1));// 右边界就等于 i+1 的右边界
} else { // >= 0 情况下
sums[i] = arr[i]; // 最小和就是本身
ends.put(i, i); // 右边界也是本身
}
}
// 以a[i] 为开头，累加和<=k 的子数组
int end = 0; // 记录右边界
int sum = 0; // 记录滑动窗口内累加和
int res = 0; // 记录最长子数组长度
for (int i = 0; i < arr.length; i++) {
// 以arr[i]开头的最小累加和是小于 k 的才能继续累加。
// 如果连最小的累加和都大于k,那么无论怎么样累加都不可能累加出小于等于k的累加和
while (end < arr.length && sum + sums[end] <= k) { // 持续累加直到找到累加和大于 K的
sum += sums[end];
end = ends.get(end) + 1; // end指向下一个最小累加和的起始位置
// 如以arr[0]开始的最小累加和到 i=7结束，即ends[0]=7。
// 那么下一个最小累加和就是i=8位置开始的，end=8
}
sum -= end > i ? arr[i] : 0;
res = Math.max(res, end - i);
end = Math.max(end, i + 1); // 如果没有走while循环end 需要更新为下一个数
}
return res;
}
// ---------------------- test -----------------------------
// 下面提供一种 O(N*logN) 的方法进行对比测试
public static int maxLength(int[] arr, int k) {
int[] h = new int[arr.length + 1];
int sum = 0;
h[0] = sum;
for (int i = 0; i != arr.length; i++) {
sum += arr[i];
h[i + 1] = Math.max(sum, h[i]);
}
sum = 0;
int res = 0;
int pre = 0;
int len = 0;
for (int i = 0; i != arr.length; i++) {
sum += arr[i];
pre = getLessIndex(h, sum - k);
len = pre == -1 ? 0 : i - pre + 1;
res = Math.max(res, len);
}
return res;
}
public static int getLessIndex(int[] arr, int num) {
int low = 0;
int high = arr.length - 1;
int mid = 0;
int res = -1;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] >= num) {
res = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return res;
}
// for test
public static int[] generateRandomArray(int len, int maxValue) {
int[] res = new int[len];
for (int i = 0; i != res.length; i++) {
res[i] = (int) (Math.random() * maxValue) - (maxValue / 3);
}
return res;
}
public static void main(String[] args) {
for (int i = 0; i < 100; i++) {
int[] arr = generateRandomArray(10, 20);
int k = (int) (Math.random() * 20) - 5;
System.out.println("arr: " + Arrays.toString(arr) + " k=" + k);
System.out.println("maxLengthAwesome(arr, k): " + maxLengthAwesome(arr, k));
System.out.println("maxLength(arr, k): " + maxLength(arr, k));
if (maxLengthAwesome(arr, k) != maxLength(arr, k)) {
System.out.println("oops!");
}
}
}
}
