一、数组问题

获取最多1的行的坐标

/**
 * @Author: 郜宇博
 * @Date: 2021/11/23 14:59
 */
public class MaxCountLine {
    public static void main(String[] args) {
        int[][] ar = {
                {0,1,1,1,1},
                {0,0,0,1,1},
                {0,0,1,1,1},
                {0,0,0,0,0}
        };
        System.out.println(getMamLine(ar));
    }

    /**
     * 获取1最多的行坐标，从右上角开始遍历，如果左边为1，则左移
     * 左边不为1，下移
     * @param arr
     * @return
     */
    public static int getMamLine(int[][] arr){
        List<Integer> list = new ArrayList<>();
        int count = 0;
        int j = arr[0].length;
        int res = 0;
        for (int i =0; i < arr.length; i++){
            //j = arr[0].length-1;
            while (j >=0){
                if (arr[i][j-1] == 1){
                     count++;
                     j--;
                     res = i;
                } else {
                    break;
                }
            }
        }
        return res;
    }
}

蛇形打印

用zigzag的方式打印矩阵，比如如下的矩阵 0 1 2 3 4 5 6 7 8 9 10 11
打印顺序为：0 1 4 8 5 2 3 6 9 10 7 11

package day14;

/**
 * @Author: 郜宇博
 * @Date: 2021/11/27 13:05
 */
public class ArrayPrintSnake {
    public static void main(String[] args) {
        int[][]arr = {
                {0,1,2,3,5},
                {4,5,6,7,3},
                {8,9,10,11,34}
        };
        print(arr);
    }
    /**
     * 蛇形打印
     * 指定两个坐标，打印斜对角线（1，左下打印；2右上）
     * 初始两个坐标都在0位置，index1向下走到头向右走，index2向右走到头向下走，相碰停止。
     * 每次两坐标都移动，移动一次打印一趟，更换一下打印方向。
     */
    public static void print(int[][] arr){
        int index1R=0,index2R = 0;
        int index1C=0,index2C = 0;;
        boolean ifRightUp = true;
        do {
            //右上方向打印
            print(arr,index1R,index1C,index2R,index2C,ifRightUp);
            //1坐标移动(先看列需不需要动)
            index1C = index1R == arr.length-1?index1C+1:index1C;
            index1R = index1R == arr.length-1?index1R:index1R+1;
            //2坐标移动（先看行需不需要动）
            index2R = index2C == arr[0].length-1?index2R+1:index2R;
            index2C = index2C == arr[0].length-1?index2C:index2C+1;
            ifRightUp = !ifRightUp;
        }while ((index1R != index2R) && (index1C != index2C));
        System.out.println(arr[index1R][index1C]);
    }
    private static void print(int [][] arr,int index1R, int index1C, int index2R, int index2C, boolean ifRightUp) {
        //右上方打印
        if (ifRightUp){
            int times = index2C -index1C;
            for (int i = 0; i <= times; i++){
                System.out.print(arr[index1R--][index1C++]+" ");
            }
        }
        else {
            int times = index2C -index1C;
            for (int i = 0; i <= times; i++){
                System.out.print(arr[index2R++][index2C--]+" ");
            }
        }
    }
}

螺旋打印

用螺旋的方式打印矩阵，比如如下的矩阵 0 1 2 3 4 5 6 7 8 9 10 11
打印顺序为：0 1 2 3 7 11 10 9 8 4 5 6

package day14;

/**
 * @Author: 郜宇博
 * @Date: 2021/11/27 14:11
 */
public class ArrayPrintCricle {
    public static void main(String[] args) {
        int[][] matrix = {
                { 1, 2, 3, 4 }, 
                { 5, 6, 7, 8 }, 
                { 9, 10, 11, 12 },
                { 13, 14, 15, 16 } };
        print(matrix);
    }

    /**
     * 一圈一圈打印
     * 然后坐标1向右下方移动
     * 坐标2向左上方移动
     * 错开的时候：index2R < index1R,停止
     * @param arr
     */
    public static void print(int[][]arr){
        int index1R = 0;
        int index1C = 0;
        int index2R = arr.length-1;
        int index2C = arr[0].length-1;
        while (index2R >= index1R){
            printCricle(arr,index1R++,index1C++,index2R--,index2C--);
        }
    }
    private static void printCricle(int[][] arr, int index1R, int index1C, int index2R, int index2C) {
        //如果在同一行
        if (index2R == index1R){
            while (index1C+1 <= index2C){
                System.out.print(arr[index1R][index1C++]+" ");
            }
        }
        //如果在同一列
        if (index1C == index2C){
            while (index1R+1 <= index2R){
                System.out.print(arr[index1R++][index1C]+" ");
            }
        }
        //正常情况
        else {
            int curC = index1C;
            int curR = index1R;
            //向左
            while (index1C != index2C){
                System.out.print(arr[index1R][index1C++]+" ");
            }
            //向下
            while (index1R != index2R){
                System.out.print(arr[index1R++][index1C]+" ");
            }
            //向左
            while (index1C != curC){
                System.out.print(arr[index1R][index1C--]+" ");
            }
            //向上
            while (index1R != curR){
                System.out.print(arr[index1R--][index1C]+" ");
            }
        }
    }
}

二、机器人打包问题

有n个打包机器从左到右一字排开，上方有一个自动装置会抓取一批放物品到每个打包机上，放到每个机器上的这些物品数量有多有少，由于物品数量不相同，需要工人将每个机器上的物品进行移动从而到达物品数量相等才能打包。每个物品重量太大、每次只能搬一个物品进行移动，为了省力，只在相邻的机器上移动。请计算在搬动最小轮数的前提下，使每个机器上的物品数量相等。如果不能使每个机器上的物品相同，返回-1。例如[1,0,5]表示有3个机器，每个机器上分别有1、0、5个物品，经过这些轮后：第一轮：1 0 <- 5 =>
1 1 4 第二轮：1 <-1<- 4 =>
2 1 <- 3 => 2 2 2 移动了3轮，每个机器上的物品相等，所以返回3
例如[2,2,3]表示有3个机器，每个机器上分别有2、2、3个物品，
这些物品不管怎么移动，都不能使三个机器上物品数量相等，返回-1

package day14;

/**
 * @Author: 郜宇博
 * @Date: 2021/11/27 12:40
 */
public class PackingMachine {
    public static void main(String[] args) {
        System.out.println(MinOp2(new int[]{20,20, 5,5,2,8}));
    }
    public static int MinOp2(int[] arr){
        if (arr == null || arr.length ==0){
            return -1;
        }
        int size = arr.length;
        int sum = 0;
        int avg = 0;
        for (int j : arr) {
            sum += j;
        }
        if (sum % size != 0){
            return -1;
        }
        avg = sum/size;
        //左侧需要给出多少件，负数表示需要多少
        int leftGive = 0;
        int rightGive = 0;
        //左侧的累加和
        int leftSum = 0;
        int minOp = Integer.MIN_VALUE;
        for (int i = 0; i < size;i++){
            leftGive = leftSum - avg*i;
            rightGive = sum -leftSum-arr[i]- (avg *(size - i - 1));
            //如果左右都不足，那么需要中间的一次一次给两边，操作数为和
            if(leftGive < 0 && rightGive < 0){
                //解决最痛的步骤，其他步骤就解决了，因此选择操作数做多的那个一个
                minOp = Math.max(minOp,Math.abs(leftGive)+Math.abs(rightGive));
            }
            else {
                //其他情况，只需要所需数或要给数多那个步骤（可以中间边给两边，两边边给中间；也可以两边一起给中间）
                minOp = Math.max(minOp,Math.max(Math.abs(leftGive),Math.abs(rightGive)));
            }
            //更新左边和
            leftSum += arr[i];
        }
        return minOp;
    }
}

三、栈转队列

package day14;

import java.util.Stack;

/**
 * @Author: 郜宇博
 * @Date: 2021/11/27 15:42
 */
public class StackToQueue {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.add(1);
        myQueue.add(2);
        myQueue.add(3);
        System.out.println(myQueue.poll());
        myQueue.add(4);
        System.out.println(myQueue.poll());
    }
    static class MyQueue{
        private Stack<Integer> pushStack = new Stack<>();
        private Stack<Integer> popStack = new Stack<>();

        public void add(Integer num){
            pushStack.add(num);
            //加入弹出栈中
            toPopStack();
        }
        private void toPopStack() {
            if ( !popStack.isEmpty()){
                return;
            }
            while (!pushStack.isEmpty()){
                popStack.add(pushStack.pop());
            }
        }
        public int poll(){
            return popStack.pop();
        }
    }
}

四、队列转栈

package day14;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 郜宇博
 * @Date: 2021/11/27 15:52
 */
public class QueueToStack {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.add(1);
        myStack.add(2);
        System.out.println(myStack.pop());
        myStack.add(3);
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        //System.out.println(myStack.pop());
    }

    static class MyStack {
        private Queue<Integer> queue1 = new LinkedList<>();
        private Queue<Integer> queue2 = new LinkedList<>();

        public void add(Integer num) {
            queue1.add(num);
        }
        public int pop() {
            if (queue1.isEmpty()){
                throw  new RuntimeException("空");
            }
            while (queue1.size() > 1) {
                queue2.add(queue1.poll());
            }
            int res = queue1.poll();
            swap();
            return res;
        }
        private void swap() {
            Queue<Integer> temp = queue2;
            queue2 = queue1;
            queue1 = temp;
        }

    }
}

五、容器盛水

给定一个数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水比如，arr = {3，1，2，5，2，4}，根据值画出的直方图就是容器形状，该容器可以装下5格水
再比如，arr = {4，5，1，3，2}，该容器可以装下2格水

/**
 * @Author: 郜宇博
 * @Date: 2021/11/27 16:06
 */
public class ContainWater {
    public static void main(String[] args) {
        for (int i = 0; i < 100; i++){
            int[] ints = randomArray(10);
            if (getContain2(ints) != getContain1(ints)){
                System.out.println("no");
            }
        }
    }
    /**
     * 预处理法获取各个位置左右的最大值
     * @param arr
     * @return
     */
    public static int getContain1(int[] arr){
        //预处理获取各左右最大高度
        int[] leftMax = new int[arr.length];
        leftMax[0] = -1;
        int[] rigthtMax = new int[arr.length];
        rigthtMax[arr.length-1] = -1;
        for (int i = 1; i < leftMax.length; i++){
            leftMax[i] = Math.max(arr[i-1],leftMax[i-1]);
        }
        for (int i = rigthtMax.length-2; i >=0; i--){
            rigthtMax[i] = Math.max(rigthtMax[i+1],arr[i+1]);
        }
        //获取每个位置积水
        int res = 0;
        int part = 0;
        for (int i = 1; i < arr.length-1;i++){
            part = Math.max((Math.min(leftMax[i], rigthtMax[i])) - arr[i], 0);
            res+=part;
        }
        return res;
    }
    /**
     * 双指针法
     * @param arr
     * @return
     */
    public static int getContain2(int[] arr){
        int leftBorder = 1;
        int rightBorder = arr.length-2;
        int leftMax = arr[0];
        int rightMax = arr[arr.length-1];
        int res = 0;
        while (leftBorder <= rightBorder ){
            //左边界移动
            if (leftMax <= rightMax){
                res += Math.max(leftMax - arr[leftBorder],0);
                leftMax = Math.max(arr[leftBorder++],leftMax);
            }
            //右边界移动
            else {
                res += Math.max(rightMax - arr[rightBorder],0);
                rightMax = Math.max(arr[rightBorder--],rightMax);
            }
        }
        return res;
    }
    public static int[] randomArray(int num){
        int[] ints = new int[num];
        for (int i = 0; i < num; i++){
            ints[i] = new Random().nextInt(10);
        }
        return ints;
    }

}

六、旋转词字符串

如果一个字符串为str，把字符串str前面任意的部分挪到后面形成的字符串叫作str的旋转词。比如str="12345"，str的旋转词有"12345"、"23451"、 "34512"、"45123"和"51234"。给定两个字符串a和b，请判断a和b是否互为旋转
词。比如： a="cdab"，b="abcd"，返回true。 a="1ab2"，b="ab12"，返回false。
a="2ab1"，b="ab12"，返回true。

/**
 * @Author: 郜宇博
 * @Date: 2021/11/27 18:26
 */
public class ChildString {
    public static void main(String[] args) {
        System.out.println(isChild("2ab1", "ab12"));
    }
    /**
     * 将str1拼为str1+str1,如果新的字符串有子串str2,则互为旋转词
     * @param str1
     * @param str2
     * @return
     */
    public static boolean isChild(String str1,String str2){
        char[] char1 = (str1+str1).toCharArray();
        char[] char2 = str2.toCharArray();
        return KMP(char1,char2);
    }
    public static boolean KMP(char[] char1, char[] char2) {
        int[] next = getNext(char2);
        int cur1 = 0;
        int cur2 = 0;
        while (cur1 < char1.length && cur2 < char2.length){
            if (char1[cur1] == char2[cur2]){
                cur1++;
                cur2++;
            }
            else {
                if (next[cur2] == -1){
                    cur1++;
                }
                else {
                    cur2 = next[cur2];
                }
            }
        }
        return cur2 == char2.length;
    }
    public static int[] getNext(char[] chars){
        if (chars.length == 1){
            return new int[]{-1};
        }
        int[] next = new int[chars.length - 1];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        for (int i =2; i < next.length; i++){
            cn = next[i-1];
            if (chars[i-1] == chars[cn]){
                next[i++] = ++cn;
            }
            else {
                if (cn == 0){
                    next[i++] = 0;
                }
                else {
                    cn = next[cn];
                }
            }
        }
        return next;
    }
}