27、算法与数据结构 - 实战：打表找规律技巧、根据数据量猜解法
打表找规律
1、 某个面试题，输入参数简单，并且只有一个实际参数；
2、 要求的返回值类型也简单，并且只有一个；
3、 用暴力方法，把输入参数对应的返回值，打印出来看看，进而优化code；
题目一
小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量。
能装下6 个苹果的袋子，
能装下8 个苹果的袋子。
小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满。
给定一个正整数 N，返回至少使用多少袋子。如果 N 无法让使用的每个袋子必须装满，返回 - 1
一般做法就是一上来就根据题意，推背后的数学公式，但是这种做法效率太低。
首先使用暴力方法，打印所有的解，寻找规律：
/**
* 第一步：打印所有的解，寻找规律
*/
public static void printAllResult() {
for (int i = 0; i <= 100; i++) {
int a = i / 8; // 8号代个数
int b = i % 8; // 剩余苹果数
if (b == 0) {
// 苹果剩余0个（正好用8号袋全部装下）？
//System.out.println(i + " " + a + " " + 0 + " " + a);
System.out.println(i + " " + a);
continue;
}
if (b == 6) {
// 正好剩下6个？
System.out.println(i + " " + (a + 1));
continue;
}
boolean flag = true;
// 1个8号袋分出去，2个8号袋分出去，......直到刚好能被6号袋分摊
for (int j = 1; j <= a; j++) {
if (((j * 8) + i % 8) % 6 == 0) {
System.out.println(i + " " + ((a - j) + ((j * 8) + i % 8) / 6));
flag = false;
break;
}
}
if (flag) System.out.println(i + " " + (-1));
}
}
打印的结果：
00 1-1
2-1
3-1
4-1
5-1
61 7-1
81 9-1
10-1
11-1
122
13-1
142
15-1
162
17-1
183
19-1
203
21-1
223
23-1
243
25-1
264
27-1
284
29-1
304
31-1
324
33-1
345
35-1
365
37-1
385
39-1
405
41-1
426
43-1
446
45-1
466
47-1
486
49-1
507
51-1
527
53-1
547
55-1
567
57-1
588
59-1
608
61-1
628
63-1
648
65-1
发现规律：
0打印0
奇数都是打印-1
从18开始，每8个数一组，偶数打印组号+3，奇数也是打印-1
前17个数的偶数，单独枚举就行
优化后的code：
/**
0 0
1 -1
2 -1
3 -1
4 -1
5 -1
6 1
7 -1
8 1
9 -1
10 -1
11 -1
12 2
13 -1
14 2
15 -1
16 2
17 -1
18 3
19 -1
20 3
21 -1
22 3
23 -1
24 3
25 -1
26 4
27 -1
28 4
29 -1
30 4
31 -1
32 4
33 -1
34 5
35 -1
36 5
37 -1
38 5
39 -1
40 5
41 -1
42 6
43 -1
44 6
45 -1
46 6
47 -1
48 6
49 -1
50 7
51 -1
52 7
53 -1
54 7
55 -1
56 7
57 -1
58 8
59 -1
60 8
61 -1
62 8
63 -1
64 8
65 -1
* @param apple
* @return
*/
public static int minBages(int apple) {
/*
根据打表返回的数列，找出规律，按规律分情况返回结果
*/
if (apple < 0) return -1;
if ((apple & 1) != 0) return -1; // 奇数返回-1
// 单独枚举的数
if (apple < 18) {
switch (apple) {
case 0: return 0;
case 6: return 1;
case 8: return 1;
case 12: return 2;
case 14: return 2;
case 16: return 2;
default: return -1;
}
}
return (apple - 18) / 8 + 3; // 从18开始, 偶数返回组号+3
}
题目二
给定一个正整数N，表示有N份青草统一堆放在仓库里。
有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草。
不管是牛还是羊，每一轮能吃的草量必须是：1，4，16，64…(4的某次方)。
谁最先把草吃完，谁获胜。
假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定。
根据唯一的参数N，返回谁会赢。
先用暴力解，打表找规律：
public static String winner1(int n) {
/*
base case
后 先 后 先 先
0 1 2 3 4
*/
if (n < 5) {
return n ==0 || n == 2 ? "后手" : "先手";
}
int base = 1;
while (base <= n) {
// n减去base，再递归调winner函数，
// 如果返回后手赢，则当前函数返回先手赢，
// 因为吃掉base份草后，当前玩家变后手
if (winner1(n - base).equals("后手")) return "先手";
if (base > n / 4) break;
// 每一轮能吃的草量是4的某次方，乘一个4
// 但是要做防溢出处理
if (base <= n/4)base *= 4;
else break;
}
return "后手";
}
发现规律：
后手
先手
后手
先手
先手
后手
先手
后手
先手
先手
......
每5个一组，都是“后先后先先”
优化后的code：
/**
后手
先手
后手
先手
先手
后手
先手
后手
先手
先手
* @param n
* @return
*/
public static String winner2(int n) {
return (n % 5 == 0 || n % 5 == 2) ? "后手" : "先手";
}
题目三
定义一种数：可以表示成若干（数量>1）连续正数和的数 。
比如:5 = 2+3，5就是这样的数 ；12 = 3+4+5，12就是这样的数 。
1不是这样的数，因为要求数量大于1个、连续正数和 。
2=1 + 1，2也不是，因为等号右边不是连续正数 。
给定一个参数N，返回是不是可以表示成若干连续正数和的数 。
先用暴力解找规律：
/**
* 暴力解找规律
* @param n
* @return
*/
public static boolean isMSum1(int n) {
// 1 + 2 + 3 + 4 + ...
// 2 + 3 + 4 + ...
// 3 + 4 + ....
// 遍历开头的那个数
for (int start = 1; start < n; start++) {
// sum一开始为开头数
int sum = start;
// 一直加一个往后的连续数
for (int num = start + 1; num < n; num++) {
// 能加到n
if (sum + num == n) return true;
// 加超了
if (sum + num > n) break;
// 加
sum += num;
}
}
return false;
}
打表结果：
1false
2false
3true
4false
… 8false
… 16false
… 32false
… 64false
发现规律：
2的某次方，就是false，否则是true
优化后的code：
/**
1 false
2 false
3 true
4 false
...
8 false
...
16 false
...
32 false
...
64 false
* @param n
* @return
*/
public static boolean isMSum2(int n) {
if (n < 3) return false;
/*
如果一个数的二进制形式只有一个1，就是2的某次方
那么与上自己减一后的值，会变成0
如果与上自己减一后的值，不是0，那么就不是2的某次方
获取可以提取二进制最右侧的1，看是否和自己相等
相等的话就是2的某次方
*/
// if ((n & (-n)) == n) return true;
if ((n & (n - 1)) != 0) return true;
return false;
}
根据数据量猜解法
1、 C/C++，1秒处理的指令条数为10的8次方；
2、 Java等语言，1~4秒处理的指令条数为10的8次方；
3、 这里就有大量的空间了！；
如果给定的参数是一个数组，长度10^6，Java语言要求2~3秒内完成，
那么写一个O(N^2)的算法，就是不通过的，至少是一个O(N * logN)的算法，最好是O(N)。
如果给定的参数是一个数组，长度10^3，
那么写一个O(N^2)的算法，就足够了。
如果给定的参数是一个数组，长度10^12，O(logN)的算法也没戏，要么是O(logN)通过二分规避掉长度，要么压根跟长度N无关。
一个例子
int[] d，d[i]：i号怪兽的能力
int[] p，p[i]：i号怪兽要求的钱
开始时你的能力是0，你的目标是从0号怪兽开始，通过所有的怪兽。
如果你当前的能力，小于i号怪兽的能力，你必须付出p[i]的钱，贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上；如果你当前的能力，大于等于i号怪兽的能力，你可以选择直接通过，你的能力并不会下降，你也可以选择贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上。
返回通过所有的怪兽，需要花的最小钱数。
暴力解：
public static int minMoney(int[] d,int[] p) {
if (d == null || p == null || d.length == 0 || p.length == 0 || d.length != p.length) return 0;
return process(d, p, 0, 0);
}
/**
* 第一种解法 递归
* 当前能力是ability，来到了index号怪兽，通关后续所有怪兽，至少需要多少钱
* @param d 怪兽能力数组
* @param p 怪兽要求的钱数组
* @param ability 当前能力值
* @param index 当前怪兽的下标
* @return
*/
public static int process(int[] d, int[] p, int ability, int index) {
// base case，彻底通关了，需要0块钱
if (index == d.length) return 0;
// 能力不够，只能花钱贿赂
if (ability < d[index]) {
return p[index] + process(d, p, ability + d[index], index + 1);
}
// 能力够，花钱、不花钱，递归尝试，取最小值
else {
return Math.min(p[index] + process(d, p, ability + d[index], index + 1),
process(d, p, ability, index + 1));
}
}
如果题目给出的怪兽能力值，都比较小，那么通过上面这个暴力解，改成动态规划
申请一个二维dp表，行表示怪兽下标，列表示能力值的累加和，
每个格子dp[i][j]表示从i号怪兽开始，当前能力值是j，通关后续所有怪兽，至少花掉的钱数
但是如果题目给出的怪兽能力值，都比较大，例如10^8以上，就不能这么改动态规划了。
应该把列换成严格花掉的钱数
dp[i][j]表示表示通过从0~i号怪兽，是否能严格花掉j块钱，能的话填上获得的最大能力值，不能则填-1
public static int dp(int[] d,int[] p) {
if (d == null || p == null || d.length == 0 || p.length == 0 || d.length != p.length) return 0;
// 累加所有的钱，最大钱数
int money = 0;
for (int i = 0; i < p.length; i++) {
money += p[i];
}
/*
dp表
dp[i][j] 表示通过从0~i号怪兽，是否能严格花掉j块钱，
能的话填上获得的最大能力值
不能则填-1
*/
int[][] dp = new int[d.length][money + 1];
for (int i = 0; i < d.length; i++) {
dp[i][0] = -1;
}
for (int i = 0; i < money; i++) {
dp[0][i] = -1;
}
dp[0][p[0]] = d[0];
for (int i = 1; i < d.length; i++) {
for (int j = 1; j <= money; j++) {
/*
1、如果能严格花掉j块钱通关0~i-1号怪兽，并且获得的能力值大于i号怪兽的能力值，则直接通过，能力值为dp[i - 1][j]
2、如果能严格花掉j-p[i]块钱，通过0~i-1号怪兽，选择贿赂i号怪兽，能力值dp[i - 1][j - p[i]] + d[i]
上面两种情况的值，选最大的填到当前格子
*/
int ability1 = dp[i - 1][j] >= d[j] ? dp[i - 1][j] : -1;
int ability2 = j - p[i] >= 0 && dp[i - 1][j - p[i]] != -1 ? dp[i - 1][j - p[i]] + d[i] : -1;
dp[i][j] = Math.max(ability1, ability2);
}
}
//遍历dp表的最后一行，最早不为-1的，这个列代表的钱数，就是通关所有怪兽花掉最少的钱
for (int i = 0; i <= money; i++) {
if (dp[d.length - 1][i] != -1) return i;
}
return money;
}
如果题目给出的贿赂怪兽的钱数都较大，那么就不能用第二种方法，要用第一种。
分治法
面试中的分治应用场景：
1、 数据量整体做尝试可能性太多了，跑不完；
2、 数据分成多个块（通常是两块），各自可能性并不算多；
3、 合并多个块各自信息的整体过程不复杂；
例子一
给定一个非负数组arr，和一个正数m。 返回arr的所有子序列中累加和%m之后的最大值。
第一种数据量情况：
如果arr中的每个值都不大，arr的长度也不大
如果arr的长度 * 数组累加和，在10^8以内
1、 那么可以以arr下标为行，累加和为列，弄一个boolean类型的dp表，dp[i][j]表示从数组0~i范围自由选择，能否搞出累加和j；
2、 填dp[i][j]有两种情况：不要arr[i]，那么dp[i][j]=dp[i-1][j]；要arr[j]，那么dp[i][j]=dp[i-1][j-arr[i]]两个或一下；
3、 填完这个表后，遍历最后一行，为true的，那它模m抓出一个余数，每一个余数都PK一下抓出最大值；
第二种数据量情况：
arr的长度不大，m不大，但是arr里的value很大
那么列就不可以用累加和，改为用余数做列
1、 也是一个boolean类型的dp表，dp[i][j]表示从arr的0~i范围内，自由选择数，能不能高出余数j，那么dp表的列数就是m；
2、 填dp[i][j]有两种情况：不要arr[i]，那么dp[i][j]=dp[i-1][j]；要arr[i]，如果arr[i]%m<=j，dp[i][j]==dp[i-1][j-cur]，如果arr[i]%m>j，dp[i][j]==dp[i-1][m+j-cur]三个或一下；
3、 填完这个表后，遍历最后一行，为true的余数抓出来PK；
第三种数据量情况：
数组中每个值都大于10^8
m为10^12，数组长度最多20个数
那么此时就不适合用动态规划解法了：
1、 因为value都很大，所以不能用背包解（row为arr的数，col为sum，dp为boolean类型）；
2、 因为m很大，所以不能用以m为col的db（row为arr的数，col为m，dp为boolean类型）；
此时时候用分治：
数组砍成两边
分别求两边的所有子序列累计和
然后在计算左边累计和最接近m的、右边的累加和最接近m的、两边组合最接近m的，返回最接近m的结果
/**
* 给定一个非负数组arr，和一个正数m。 返回arr的所有子序列中累加和%m之后的最大值。
* 数组中每个值都大于10^8，m为10^12，数组长度最多20个数
* Created by huangjunyi on 2022/10/9.
*/
public class _02SubsquenceMaxModM {
public static int getMax(int[] arr, int m) {
if (arr.length == 1) return arr[0] % m;
int mid = (arr.length - 1) / 2;
/*
因为value都很大，所以不能用背包解（row为arr的数，col为sum，dp为boolean类型）
因为m很大，所以不能用以m为col的db（row为arr的数，col为m，dp为boolean类型）
数组砍成两边
分别求两边的所有子序列累计和
然后在计算左边累计和最接近m的、右边的累加和最接近m的、两边组合最接近m的，返回最接近m的结果
*/
TreeSet<Integer> treeSet1 = new TreeSet<>();
process(arr, 0, 0, mid, m, treeSet1);
TreeSet<Integer> treeSet2 = new TreeSet<>();
process(arr, mid + 1, 0, arr.length - 1, m, treeSet2);
int res = 0;
for (Integer leftMode : treeSet1) {
res = Math.max(res, leftMode + treeSet2.floor(m - 1 - leftMode));
}
return res;
}
private static void process(int[] arr, int index, int sum, int end, int m, TreeSet<Integer> treeSet) {
if (index == end + 1) {
treeSet.add(sum % m);
}
process(arr, index + 1, sum, end, m, treeSet);;
process(arr, index + 1, sum + arr[index], end, m, treeSet);
}
}
例子二
背包容量为w
一共有n袋零食，零食体积为v[i]，v[i] > 0
问总体积不超过背包容量的情况下，一共有多少种零食放法？（总体积为0也算一种方法）
这是经典的背包问题，如果没有其他限制条件，使用动态规划解即可：
public static int process(int[] v, int w) {
int n = v.length;
/*
弄一个dp数组（二维）
dp[i][j]表示零食从0~i自由选择，刚好凑齐j体积的放法数量
*/
int[][] dp = new int[n][w + 1];
for (int i = 0; i < n; i++) {
dp[i][0] = 1;
}
if (v[0] <= w) {
dp[0][v[0]] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= w; j++) {
/*
动态转移方程
dp[i][j]等于i号零食不要时的放法数（dp[i - 1][j])加上i号零食要时的放法数（dp[i - 1][j - v[i]]）
*/
dp[i][j] = dp[i - 1][j] + (j - v[i] >= 0 ? dp[i - 1][j - v[i]] : 0);
}
}
//把最后一行累加，得到结果
int res = 0;
for (int i = 0; i <= w; i++) {
res += dp[n - 1][i];
}
return res;
}
但是如果题目加了限制条件，
假设v[i]的范围是0~10^9，
w的范围是1~2*10^9，
n的范围是1~30呢？
这时如果使用动态规划的话，dp表光是宽度就超10^8了，在规定时间内肯定是拿不下的，
但是n却很小，如果使用分治的话，两边各负责15，使用暴力递归，也就是2^15
两边分别求一个方法数，同时各自用一个map收集每种体积对应的方法数，然后两个map匹配一下，再求一个方法数即可。
注意，有一个map要转换成前缀和map，因为题目求的时体积不超的情况下的方法数。
public static int process2(int[] v, int w) {
if (v == null || v.length == 0) return 0;
if (v.length == 1) return v[0] <= w ? 2 : 1;
int mid = (v.length - 1) >> 1;
TreeMap<Integer, Integer> leftMap = new TreeMap<>();
int ways = getWays(v, 0, 0, w, mid, leftMap);
TreeMap<Integer, Integer> rightMap = new TreeMap<>();
ways += getWays(v, 0, 0, w, v.length - 1, leftMap);
int pre = 0;
// 右map的前缀和map
TreeMap<Integer, Integer> rightPreSumMap = new TreeMap<>();
for (Map.Entry<Integer, Integer> entry : rightMap.entrySet()) {
pre += entry.getValue();
rightPreSumMap.put(entry.getKey(), pre);
}
// 左map和右map前缀和map进行匹配
for (Map.Entry<Integer, Integer> entry : leftMap.entrySet()) {
// 包大小 - 左map当前遍历到的体积 = 剩余的体积
Integer key = rightPreSumMap.floorKey(w - entry.getKey());
if (key != null) {
// 匹配成功，两边方法数相乘
ways += entry.getValue() * rightPreSumMap.get(key);
}
}
// +1是还有一种是任何都不选
return ways + 1;
}
/**
* 从index位置开始，往后自由选择，能凑出的体积不超w的方法数
* @param v 零食数组
* @param index 零食数组当前下标
* @param weight 当前体积
* @param w 背包容量
* @param end 结束位置
* @param map 结果map
* @return
*/
private static int getWays(int[] v, int index, int weight, int w, int end, TreeMap<Integer, Integer> map) {
// 体积超了，无效
if (weight > w) return 0;
// 遍历完了
if (index > end) {
// 这是什么都不选的，也无效
if (weight == 0) return 0;
// 记录到map中，后面用于两边map匹配
if (map.containsKey(weight)) {
map.put(weight, map.get(weight) + 1);
} else {
map.put(weight, 1);
}
// 1中有效方法数
return 1;
}
// 当前位置零食要
int ways = getWays(v, index + 1, weight, w, end, map);
// 当前位置零食不要
ways += getWays(v, index + 1, weight + v[index], w, end, map);
return ways;
}