Tabulation skills and matrix processing skills

Minimum number of bags

Ideas ： First, output a certain number of results in the form of violence , Find the rules according to the results

package com.zzf.algorithm;

/** * @author zzf * @date 2022-02-09 */
public class AppleMinBags {
    

    public static int minBags(int apple){
    
        if(apple < 0){
    
            return -1;
        }
        // Preferential secondary energy installation 8 Start with a bag 
        int bag8 = apple / 8;
        int rest = apple - (bag8 * 8);
        while (bag8 >= 0){
    
            if(rest % 6 == 0){
    
                return bag8 + (rest / 6);
            }
            // The rest cannot be loaded 6 The bag of , Choose to step back 
            else {
    
                bag8--;
                rest += 8;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
    
        for(int apple = 1; apple < 200;apple++) {
    
            System.out.println(apple + " : "+ minBags(apple));
        }

    }
}

The law discovered is from 18 Begin to have obvious grouping tendency , Every time 8 In groups , And the odd number returns -1, The remaining results are the current number of groups +3,18 Separate treatment within

package com.zzf.algorithm;

/** * @author zzf * @date 2022-02-09 */
public class AppleMinBags {
    

    public static int minBags(int apple){
    
        
        // Odd returns -1
        if((apple & 1) !=0){
    
            return -1;
        }
        if(apple < 18){
    
            return apple == 0 ? 0 :(apple == 6 || apple == 8) ? 1
                    : (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;
        }
        return (apple - 18) / 8 + 3;
    }

    public static void main(String[] args) {
    
        for(int apple = 1; apple < 200;apple++) {
    
            System.out.println(apple + " : "+ minBags(apple));
        }

    }
}

The sum of consecutive integers

Ideas ： According to the output of the violence table 200 Whether the number within is the sum of consecutive positive numbers , Try to find out the rules , Then use the rules to write better code

package com.zzf.algorithm;

/** * @author zzf * @date 2022-02-09 */
public class MSumToN {
    
    public static boolean isMSum(int num){
    
        for (int i = 1; i <= num; i++) {
    
            int sum = i;
            for (int j = i + 1; j <= num; j++) {
    
                if(sum + j > num){
    
                    break;
                }
                if(sum + j == num){
    
                    return true;
                }
                sum += j;
            }
        }
        return false;
    }

    public static void main(String[] args) {
    
        for (int num = 1; num < 200; num++) {
    
            System.out.println(num + " : " + isMSum(num));
        }
    }
}

Part of the result

According to the results, we can find that 2 The number to the power of does not satisfy the condition , So we can get better code according to this rule

package com.zzf.algorithm;

/** * @author zzf * @date 2022-02-09 */
public class MSumToN {
    
    public static boolean isMSum(int num){
    
        
        /* num & (num - 1) Is to judge whether it is 2 Bit operations to the power of   because num If it is 2 Power square , Only in binary numbers 1 individual 1 num-1 Will reverse the last few digits ,& The result of the operation will be 0 */
        return (num & (num - 1)) != 0;
    }

    public static void main(String[] args) {
    
        for (int num = 1; num < 200; num++) {
    
            System.out.println(num + " : " + isMSum(num));
        }
    }
}

Print zigzag matrix

Prepare to point to the starting position in the upper left corner A Point and B spot , Determine row and column boundary conditions ,A Click to move one step to the right first ,B Click to move down one step , Every time AB Form a slash ,A Until you can't go right , Just down ,B Until you can't go down, go right , Finally, control A,B Just don't cross the line , Add a variable to control the printing direction , Every time AB Update variables when slashes are formed , Can do zigzag printing

package com.zzf.algorithm;

/** * @author zzf * @date 2022-02-09 */
public class ZigZagPrintMatrix {
    

    public static void printMatrixZigZag(int[][] matrix){
    
        int AR = 0;
        int AC = 0;
        int BR = 0;
        int BC = 0;
        int endR = matrix.length - 1;
        int endC = matrix[0].length - 1;
        boolean fromUp = false;
        while(AR != endR +1){
    
            // Print 
            printLevel(matrix,AR,AC,BR,BC,fromUp);
            // After the unified movement 
            //A Move right until the last column goes down 
            AR = AC == endC ? AR + 1 : AR;
            AC = AC == endC ? AC : AC + 1;
            //B Move down until the last line goes right 
            BC = BR == endR ? BC + 1 : BC;
            BR = BR == endR ? BR : BR + 1;
            fromUp = !fromUp;
        }
        System.out.println();
    }

    public static void printLevel(int[][] m,int AR,int AC,int BR,int BC,boolean f){
    
        // Print from top to bottom 
        if(f){
    
            while (AR != BR + 1){
    
                System.out.print(m[AR++][AC--] + " ");
            }

        }
        // Print from the bottom up 
        else{
    
            while (BR != AR - 1){
    
                System.out.print(m[BR--][BC++] + " ");
            }
        }
    }

    public static void main(String[] args) {
    
        int[][] matrix = {
     {
     1, 2, 3, 4 }, {
     5, 6, 7, 8 }, {
     9, 10, 11, 12 } };
        printMatrixZigZag(matrix);

    }
}

Rotation print matrix

Ideas ： Prepare variables that mark the upper left column and the lower right column , Print one edge at a time , Start from top edge , Print right first , Until you meet the upper right corner , Just print down , Until you meet the lower right corner , Just print to the left , Until you meet the upper left corner , Be aware of special cases where there is only one row or column , Print by circle , From the outside to the inside

package com.zzf.algorithm;

/** * @author zzf * @date 2022-02-09 */
public class PrintMatrixSpiralOrder {
    

    public static void spiralOrderPrint(int[][] matrix){
    
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while (tR <= dR && tC <= dC){
    
            printEdge(matrix,tR++,tC++,dR--,dC--);
        }
    }
    /** * * @param m * @param tR： Top left row  * @param tC： The upper left column  * @param dR： The bottom right row  * @param dC： The lower right column  */
    public static void printEdge(int[][] m,int tR,int tC,int dR,int dC){
    
        if(tR == dR){
     // Only one line 
            for (int i = tC; i <= dC; i++) {
    
                System.out.print(m[tR][i] + " ");
            }
        }
        else if(tC == dC){
     // There is only one column 
            for (int i = tR; i <= dR; i++) {
    
                System.out.print(m[i][tC] + " ");
            }
        }else {
    
            // When the front row and the current row 
            int curC = tC;
            int curR = tR;
            while(curC != dC){
    
                System.out.print(m[curR][curC] + " ");
                curC++;
            }
            while (curR != dR){
    
                System.out.print(m[curR][curC] + " ");
                curR++;
            }
            while (curC != tC){
    
                System.out.print(m[curR][curC] + " ");
                curC--;
            }
            while (curR != tR){
    
                System.out.print(m[curR][curC] + " ");
                curR--;
            }
        }
    }
    public static void main(String[] args) {
    
        int[][] matrix = {
     {
     1, 2, 3, 4 }, {
     5, 6, 7, 8 }, {
     9, 10, 11, 12 },
                {
     13, 14, 15, 16 } };
        spiralOrderPrint(matrix);

    }
}

Rotate the square matrix clockwise 90 degree

Ideas ： Treat in circles , Rotate from outside to inside , Turn the upper left corner of the circle , Upper right corner , The lower right corner , The lower left corner is classified as 4 A group , And start as an edge in turn , Rotation is to exchange these positions in turn , And through observation , On one side , Take the group on the top side as an example , The number to be exchanged = Top right column position - Top left column position -1, reduce 1 It does not include the upper right corner position , After one revolution, the whole body shrinks to the inner circle , Keep cycling , Until the entire square matrix is rotated

package com.zzf.algorithm;

/** * @author zzf * @date 2022-02-09 */
public class RotateMatrix {
    


    public static void rotate(int[][] matrix){
    
        int a = 0;
        int b = 0;
        int c = matrix.length - 1;
        int d = matrix[0].length - 1;
        while(a < c){
    
            rotateEdge(matrix,a++,b++,c--,d--);
        }
    }
    public static void rotateEdge(int[][] m,int a,int b,int c,int d){
    
        int tmp = 0;
        for(int i = 0; i< d - b; i++){
    
            tmp = m[a][b+i];
            // Lower left corner to upper left corner 
            m[a][b+i] = m[c - i][b];
            // Bottom right corner to bottom left corner 
            m[c - i][b] = m[c][d - i];
            // Top right corner to bottom right corner 
            m[c][d - i] = m[a + i][d];
            // Top left corner to top right corner 
            m[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);
        rotate(matrix);
        System.out.println("=========");
        printMatrix(matrix);
    }
}