打表法

1）问题如果返回值不太多，可以用hardcode的方式列出，作为程序的一部分。
2）一个大问题解决时底层频繁使用规模不大的小问题的解，如果小问题的返回值满足条件1），可以把小问题的解列成一张表，作为程序的一部分。
3）打表找规律（本节课重点），有关1）和2）内容欢迎关注后序课程。

打表找规律

1）某个面试题，输入参数类型简单，并且只有一个实际参数。
2）要求的返回值类型也简单，并且只有一个。
3）用暴力方法，把输入参数对应的返回值，打印出来看看，进而优化code。

• 小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量。
  1）能装下6个苹果的袋子
  2）能装下8个苹果的袋子
  小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满。
  给定一个正整数N，返回至少使用多少袋子。如果N无法让使用的每个袋子必须装满，返回-1

/**
 * 小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量。
 * 1）能装下6个苹果的袋子
 * 2）能装下8个苹果的袋子
 * 小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满。
 * 给定一个正整数N，返回至少使用多少袋子。如果N无法让使用的每个袋子必须装满，返回-1
 */
public class BuyApple {

    // 暴力方法求解
    public static int buyApple(int n){
        if((n & 1)!= 0){
            return -1;
        }

        // 从8个袋子开始尝试
        int max = n / 8;
        int min = Integer.MAX_VALUE;
        for(int i = max;i >=0;i--){
            int temp = n - (i * 8);
            if(temp != 0 && (temp % 6) != 0){
                continue;
            }

            min = Math.min(i + (temp/6),min);
        }

        return min == Integer.MAX_VALUE ? -1 : min;
    }

    // 打表
    public static int buyApple2(int n){
        if((n & 1) != 0){
            return -1;
        }

        if(n < 18){
            if(n == 6 || n == 8){
                return 1;
            }
            if(n == 12 || n == 14 || n ==16){
                return 2;
            }
            return -1;
        }

        return (n - 18) / 8 + 3;
    }
    public static void main(String[] args) {
        for (int i = 1; i <= 100; i++) {
            System.out.println(i + "  " +buyApple(i)+ "       "+i + "  " +buyApple2(i));

        }
    }
}

• 给定一个正整数N，表示有N份青草统一堆放在仓库里
  有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草
  不管是牛还是羊，每一轮能吃的草量必须是：
  1，4，16，64…(4的某次方)
  谁最先把草吃完，谁获胜
  假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定
  根据唯一的参数N，返回谁会赢

/**
 * 给定一个正整数N，表示有N份青草统一堆放在仓库里
 * 有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草
 * 不管是牛还是羊，每一轮能吃的草量必须是：
 * 1，4，16，64…(4的某次方)
 * 谁最先把草吃完，谁获胜
 * 假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定
 * 根据唯一的参数N，返回谁会赢
 */
public class WhoWin {
    public static String whoWin(int n){
        // 0   1   2    3 4
        // 后  先   hou   先
        if(n < 5){
            return n == 0 || n ==2 ?"后手" : "先手";
        }
        // 枚举先手吃所有次方开始的草
        int index = 1;
       while (index <= n){
           // 先手index这么多的草，后手继续
           // 因为先手本轮吃过了，在接下去的轮就变成了后手，如果返回后手赢
           // 起始是现在的当前的先手赢了。
           String s = whoWin(n - index);
           if( s == "后手"){
               return "先手";
           }
           // 判断index 的4次方后会不会越界
           if(index > n / 4){
               //index * 4 之后越界
               break;
           }
           index = index * 4;
       }
       return "后手";
    }
    public static void main(String[] args) {
        System.out.println(whoWin(2));
    }
}

• 定义一种数：可以表示成若干（数量>1）连续正数和的数
  比如:
  5 = 2+3，5就是这样的数
  12 = 3+4+5，12就是这样的数
  1不是这样的数，因为要求数量大于1个、连续正数和
  2 = 1 + 1，2也不是，因为等号右边不是连续正数
  给定一个参数N，返回是不是可以表示成若干连续正数和的数

/**
 * 定义一种数：可以表示成若干（数量>1）连续正数和的数
 * 比如:
 * 5 = 2+3，5就是这样的数
 * 12 = 3+4+5，12就是这样的数
 * 1不是这样的数，因为要求数量大于1个、连续正数和
 * 2 = 1 + 1，2也不是，因为等号右边不是连续正数
 * 给定一个参数N，返回是不是可以表示成若干连续正数和的数
 */
public class LianXiZhengShu {
    public static boolean isNum(int n){
        if(n <= 0){
            return false;
        }

        // 暴力遍历

        for (int i = 1; i <=n; i++) {
            int temp = 0;
            int index = i;
            for (int j = i;j <=n;j++){
                temp += j;
                // 个数要大于1
                if((temp == n) && (j - index) >= 1 ){
                    return true;
                }
            }
        }

        return false;
    }


    public static boolean isNum2(int n){
        if(n < 3){
            return false;
        }
        // 从4开始，只要满足2^x == n 就是false
        // 判断一个数是不是2的某次方，由于2的某次方只有一个最高为的1 ,所以得出一下公式
        // n & (n -1 ) == 0,
        return (n & (n -1 )) != 0;
    }
    
    public static void main(String[] args) {
        for (int i = 1; i < 100; i++) {
            System.out.println(i + " " + isNum(i) + "  "+ isNum2(i));

        }
    }
}

矩阵处理技巧--核心技巧：找到coding上的宏观调度

• zigzag打印矩阵

// 之字形打印举证
public class ZigZag {

    // 宏观调度
    // 利用两个指针A,B,  A B同时移动，A先水平移动，移到不能再移，就向下移动，
    // B向下移动，移到不能再移，就向右移动，直到AB到达终点。
    public static void zigzag(int[][] matrix){
        if(matrix == null || matrix.length == 0){
            return;
        }
        // 定义A、B两点
        int aR = 0;
        int aC = 0;
        int bR = 0;
        int bC = 0;
        // 终点
        int endR = matrix.length - 1;
        int endC = matrix[0].length - 1;

        // AB移动 一定是同时到达终点，只用判断一个点是否越界就可以了
        // 这里就用A点
        boolean from = true;
        while (aR <= endR && aC <= endC){
            // 没有越界就一直打印
            printLine(matrix,aR,aC,bR,bC,from);
            from = !from;
            // A的移动轨迹
            aR = aC != endC ? aR : ++aR ;
            aC = aC == endC ? endC : ++aC;
            // B的移动轨迹
            bC = bR != endR ? bC:++bC;
            bR = bR != endR ? ++bR:endR;
        }
    }

    // 给点A B 两点和打印方向，打印AB两点的连线
    private static void printLine(int[][] matrix,int aR,int aC,int bR,int bC,boolean from){
        if(from){
            // 从下到上
            while (bR >= aR && bC <= aC){
                System.out.print(matrix[bR--][bC++]);
            }
        }else{
            // 从上到下
            while (aR <= bR && aC >= bC){
                System.out.print(matrix[aR++][aC--]);
            }
        }
    }
    public static void main(String[] args) {
        int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
        zigzag(matrix);


    }
}

• 转圈打印矩阵

// 转圈打印矩阵
// 先打印外圈环，在打印内圈
public class PrintRing {
    public static void printRing(int[][] matrix){
        if(matrix == null || matrix.length == 0){
            return;
        }
        // 最外城点坐标
        int a = 0;int b = 0;
        int c = matrix.length -1 ;int d = matrix[0].length - 1;

        while (a <= c && b <= d){
            print(matrix,a++,b++,c--,d--);
        }
    }

    // 给定左上角点坐标，右下角点坐标，打印围成的圈。
    private static void print(int[][] matrix,int a,int b,int c,int d){
        if(a == c){
            // 同一条横线上,直接打印
            while (b <= d){
                System.out.print(matrix[a][b++] + " ");
            }
        }else if(b == d){
            // 同一条竖线
            while (a <= c){
                System.out.print(matrix[a++][b]+ " ");
            }
        }else{
            // 一般情况
            // 上横线
            int curR = a;
            int curC = b;
            while (curC < d){
                System.out.print(matrix[curR][curC++]+ " ");
            }
            // 右竖线
            while (curR < c){
                System.out.print(matrix[curR++][curC]+ " ");
            }

            // 下横线
            while (curC > b){
                System.out.print(matrix[curR][curC--]+ " ");
            }

            // 左竖线
            while (curR > a){
                System.out.print(matrix[curR--][curC]+ " ");
            }
        }
    }
    public static void main(String[] args) {
        int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
                { 13, 14, 15, 16 } };
        printRing(matrix);

    }
}

• 原地旋转正方形矩阵

// 原地旋转正方形矩阵 90度
// 先边外圈，然后向里面变
public class YuanDiPrint {

    public static void print(int[][] matrix){
        if(matrix == null || matrix[0].length == 0){
            return;
        }

        int a = 0;
        int b = 0;
        int c = matrix.length - 1;
        int d = matrix[0].length - 1;
        // 由于是正方形判断一遍就行了
        while (a <= c){
            bian(matrix,a++,b++,c--,d--);
        }

    }


    // 变换每一圈中左边的位置
    private static void bian(int[][] matrix,int a,int b,int c,int d){
        // 每一圈需要变换的个数，从0开始
        int num = d - b;
        for (int i = 0; i < num; i++) {
            // 每一组中的坐标变换
            int tmp = matrix[a][b + i];
            matrix[a][b + i] = matrix[c - i][b];
            matrix[c - i][b] = matrix[c][d - i];
            matrix[c][d - i] = matrix[a + i][d];
            matrix[a + i][d] = tmp;
        }
    }
    public static void printMatrix(int[][] matrix) {
        for (int i = 0; i != matrix.length; i++) {
            for (int j = 0; j != matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } };
        printMatrix(matrix);
        print(matrix);
        System.out.println("=========");
        printMatrix(matrix);

    }
}