【打表法】买苹果问题

60 阅读 0 评论 40 点赞

我是靠谱客的博主纯情豆芽，最近开发中收集的这篇文章主要介绍【打表法】买苹果问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【题目】小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装包装不可拆分。可是小虎现在只想购买恰好n个苹果，小虎想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小虎将不会购买。输入一个整数n，表示小虎想购买的个苹果，返回最小使用多少袋子。如果无论如何都不能正好装下，返回-1。

打表法

打表就是将所有输入情况的答案保存在代码中，输入数据后直接输出就可以了
这个技巧对于一些题目而言能够降低程序的运行时间，降低算法的时间复杂度。
满足的特点是一般为输入是一个参数输出也是一个数

打表法的几个优点：

（1）在程序中一次性计算出需要的结果，之后直接查询，一般情况下，Q次查询的时间复杂度只需要O(n+Q)；

（2）对于一些题目，数据范围非常大，可以暴力计算小范围数据结果，然后找规律。

打表法具有快速，易行（可以写暴力枚举程序）的特点，缺点是代码可能太大，或者有些情况没有覆盖完。

思路

1.先使用一般的解法遍历出一定范围内输入与输入的联系，观察规律。

2.使用打表法将输入情况的结果用代码表示得到对应的输出，降低时间复杂度。

代码实现

public class Code02_BuyApples {
    public static void main(String[] args) {
        boolean flag = true;
        for (int i = 0; i < 1000; i++) {
            if (buyApples(i) != minBagAwesome(i)) {
                flag = false;
            }
        }
        System.out.println(flag);
    }

    /*小虎去附近的商店买苹果， 奸诈的商贩使用了捆绑交易， 只提供6个每袋和8个
每袋的包装包装不可拆分。 可是小虎现在只想购买恰好n个苹果， 小虎想购买尽
量少的袋数方便携带。 如果不能购买恰好n个苹果， 小虎将不会购买。 输入一个
整数n， 表示小虎想购买的个苹果， 返回最小使用多少袋子。 如果无论如何都不
能正好装下， 返回-1。*/
    public static int buyApples(int n) {
        if (n <= 0) {
            return -1;
        }
        //超过24个的话就不用再算
        int bag8 = n / 8;
        int bag6 = 0;
        int wait = n % 8;   //表示被8的袋子装完之后剩余的苹果
        while (wait < 24 && bag8 >= 0) {
            wait = (n - bag8 * 8);
            if (wait % 6 == 0) {
                bag6 = wait / 6;
                return bag6 + bag8;
            } else {
                bag8--;
            }
        }
        return -1;
    }

可以通过打表法时间复杂度优化为O(1)

    public static int minBagAwesome(int n) {
        if (n <= 0) {
            return -1;
        }
        if ((n & 1) != 0) { //如果是奇数直接返回-1
            return -1;
        }
        if (n < 18) {
            if (n == 12 || n == 14 || n == 16) {
                return 2;
            } else if (n == 2 || n == 4 || n == 10) {
                return -1;
            } else {
                return 1;
            }
        }

        return (n - 18) / 8 + 3;
    }

}