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;
    }