1、打印转圈数组

思路：按圈打印，并判断圈的四条边是否存在

public class RotatePrint {

    public static void printOneCircle(int[][] arr,int start,int rows,int cols){
        //上面一行
        for(int i=start;i<cols-start;i++)
            System.out.println(arr[start][i]);
        //右边一列,至少有两行
        if(rows > (start * 2 + 1)){
            for(int i=start+1;i<rows-start;i++)
                System.out.println(arr[i][cols-start-1]);
        }
        //下方一行，至少两行两列
        if(rows > (start * 2 + 1) && cols > (start * 2 + 1)){
            for(int i=cols-start-2;i>=start;i--)
                System.out.println(arr[rows-start-1][I]);
        }
        //左边一列，至少三行两列
        if(rows > (start * 2 + 2) && cols > (start * 2 + 1)){
            for(int i = rows-start-2;i>=start+1;i--)
                System.out.println(arr[i][start]);
        }
    }



    public static void printRotateMatrix(int[][] arr){
        int rows = arr.length;
        int cols = arr[0].length;
        for(int i = 0;i<(rows + 1) / 2;i++){
            printOneCircle(arr,i,rows,cols);
        }
    }

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

        printRotateMatrix(arr);
    }
}

2、将正方形矩阵顺时针转动90度

思路：不同于书中的做法，我们首先将数组按照正对角线进行翻转，然后按照中线左右翻转，即可得到最终的结果。

public class RotateArray90 {

    public static void rotateArrayBy90(int[][] arr){
        for(int i=0;i<arr.length;i++){
            for(int j=i+1;j<arr[i].length;j++){
                int tmp = arr[i][j];
                arr[i][j] = arr[j][i];
                arr[j][i] = tmp;
            }
        }
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[0].length / 2;j++){
                int tmp = arr[i][j];
                arr[i][j] = arr[i][arr[0].length-j-1];
                arr[i][arr[0].length-j-1] = tmp;
            }
        }
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[0].length;j++){
                System.out.print(arr[i][j] + " ");
            }
            System.out.println(" ");
        }
    }
    public static void main(String[] args){
        int[][] arr = {
                {1,2,3,4},
                {5,6,7,8},
                {9,10,11,12},
                {13,14,15,16}
        };
        rotateArrayBy90(arr);
    }
}

3、找到无序数组中最小的K个数

思路：这里我们只介绍O(Nlogk)的思路，O（N）的思路感兴趣的同学可以翻阅原书。我们使用的是堆排序，对于堆排序来说，因为是要找到最小的K个数，因此我们首先用前K个数建立大根堆，然后对于每一个新的元素，判断其与堆顶元素的大小，如果比堆顶元素还要大，那说明肯定不是最小的K个数中的，如果比堆顶元素小，则说明可能是最小的K个数之一，因此替换掉堆顶元素，并调整堆。

public class HeapSort {

    public static void perceDown(int[] arr,int i,int k){
        int tmp = arr[i];
        int child = i * 2 + 1;
        while(child < k){
            if(child + 1 < k && arr[child+1] > arr[child])
                child = child + 1;
            if(arr[child] > tmp){
                arr[i] = arr[child];
                i = child;
            }
            else
                break;
            child = i * 2 + 1;
        }
        arr[i] = tmp;
    }


    public static void heapSort(int[] arr,int k){
        for(int i=(k-1)/2;i>=0;i--){
            perceDown(arr,i,k-1);
        }
        for(int i=k;i<arr.length;i++){
            if(arr[i] < arr[0]){
                int tmp = arr[i];
                arr[i] = arr[0];
                arr[0] = tmp;
                perceDown(arr,0,k);
            }
        }
        for(int i=0;i<k;i++){
            System.out.println(arr[i]);
        }
    }

    public static void main(String[] args){
        int[] arr = {49,38,65,97,76,13,27,49,78,34,12,64,18};

        heapSort(arr,3);

    }
}

4、需要排序的最短子数组长度

思路：这里我们就是要找到两个位置，为需要排序的数组的两端，

public class MinSortArrayLength {

    public static int getMinSortArrayLength(int[] arr){
        if(arr==null || arr.length==0)
            return 0;
        int min = arr[arr.length-1];
        int noMinIndex = -1;
        for(int i = arr.length-2;i>=0;i--){
            if(arr[i] > min){
                noMinIndex = I;
            }
            else{
                min = Math.min(min,arr[I]);
            }
        }
        if(noMinIndex == -1)
            return 0;
        int max = arr[0];
        int noMaxIndex = -1;
        for(int i=1;i<arr.length;i++){
            if(arr[i] < max)
                noMaxIndex = I;
            else
                max = Math.max(max,arr[I]);
        }
        return noMaxIndex - noMinIndex + 1;
    }


    public static void main(String[] args){
        int[] arr = {1,5,3,4,2,6,7};
        System.out.println(getMinSortArrayLength(arr));
    }
}

5、在数组中找到出现次数大于N／K的数

5.1 在数组中找到出现次数大于一半的数

思路：这里我们运用这样一种消除的思想，选一个候选者，如果当前遍历到的位置和候选者不同，那么我们就把这两个数一并从数组中消除，每次从数组中消除两个不一样的数，那么最后的数要么是符合我们条件的数，要么是数组中最后一个数，再判断一下这个数的出现次数是否真的是大于一半即可。

public class FindAppearMoreThanHalfTimes {

    public static void getAppearMoreThanHalfTimes(int[] arr){

        int cand = arr[0];
        int times= 1;
        for(int i=1;i<arr.length;i++){
            if (times == 0){
                cand = arr[i];
                times = 1;
            }
            else if(arr[i] == cand){
                times++;
            }
            else{
                times--;
            }
        }
        times = 0;
        for(int i=0;i<arr.length;i++){
            if(arr[i] == cand)
                times ++;
        }
        if(times > arr.length / 2){
            System.out.println(cand);
        }
        else{
            System.out.println("no such number");
        }

    }

5.2 在数组中找到出现次数大于N／K的数

思路：同样的道理，我们设置K-1个候选者，如果新遇到的数和K-1个候选者都不同，那么我们就从数组中消除K个数。遍历完数组后，判断候选者出现次数是否符合要求即可。

public class FindAppearMoreThanNDivKTimes {

    public static void allCandsMinusOne(HashMap<Integer,Integer> cands){
        List<Integer> removeList = new LinkedList<Integer>();
        for(Map.Entry<Integer,Integer> set: cands.entrySet()){
            Integer key = set.getKey();
            Integer value = set.getValue();
            if(value == 1){
                removeList.add(key);
            }
            cands.put(key,value-1);
        }
        for(Integer removeKey:removeList){
            cands.remove(removeKey);
        }
    }

    public static HashMap<Integer,Integer> getReals(int[] arr,HashMap<Integer,Integer> cands){
        HashMap<Integer,Integer> reals = new HashMap<Integer,Integer>();
        for(int i=0;i<arr.length;i++){
            int curNum = arr[i];
            if (cands.containsKey(curNum)) {
                if(reals.containsKey(curNum))
                    reals.put(curNum,reals.get(curNum) + 1);
                else
                    reals.put(curNum,1);
            }
        }
        return reals;
    }

    public static void printKMajor(int[] arr,int k){
        if(k<2)
            return;
        HashMap<Integer,Integer> cands = new HashMap<Integer,Integer>();
        for(int i =0;i<arr.length;i++){
            if(cands.containsKey(arr[I]))
                cands.put(arr[i],cands.get(arr[i])+1);
            else{
                if(cands.size() == k-1){
                    allCandsMinusOne(cands);
                }
                else{
                    cands.put(arr[i],1);
                }
            }
        }
        HashMap<Integer,Integer> reals = getReals(arr,cands);
        boolean hasPrint = false;
        for(Map.Entry<Integer,Integer> set:cands.entrySet()){
            Integer key = set.getKey();
            if(reals.get(key) > arr.length/k){
                hasPrint = true;
                System.out.print(key + " ");
            }
        }
        System.out.println(hasPrint ? "":"no such number!");
    }

    public static void main(String[] args){
        int[] arr = {1,3,3,6,43,5,6,3,23643,3,52423,3,446,2,32,562,4,2,2,2,4,4,3,5,2,2,2,4,4,4};
        printKMajor(arr,5);
    }
}

6、在行列都排好序的矩阵中找数

思路：从矩阵的右上角或者左下角开始即可

public class FindKin2DMatrix {
    public static boolean findK(int[][] arr,int k){
        int rows = arr.length;
        int cols = arr[0].length;
        int m = 0;
        int n = cols - 1;
        while(m < rows && n >= 0){
            if(arr[m][n] == k)
                return true;
            else if(arr[m][n] < k){
                m++;
            }
            else
                n--;
        }
        return false;
    }

    public static void main(String[] args){
        int[][] arr = {{0,1,2,5},{2,3,4,7},{4,4,4,8},{5,7,7,9}};
        System.out.println(findK(arr,7));
    }
}

7、不重复打印排序数组中相加和为给定值的所有二元组和三元组

7.1 二元组

思路：由于是排好序的数组，因此设置两个指针，一个从左侧开始遍历，一个从右侧开始遍历，每次判断两个指针对应位置的数是否和目标相同即可。这里需要注意的是要去除重复值

public class FindAllTwoTuples {

    public static void findAllTwoTuples(int[] arr,int k){
        int left = 0;
        int right = arr.length-1;
        while(left < right){
            if(arr[left] + arr[right] == k ){
                if(left == 0 || arr[left] != arr[left-1]){
                    System.out.println(arr[left] + "," + arr[right]);
                }
                left++;
                right--;
            }
            else if(arr[left] + arr[right] < k)
                left ++;
            else
                right--;
        }
    }
    public static void main(String[] args){
        int[] arr = {-8,-4,-3,0,1,2,4,5,8,9};
        findAllTwoTuples(arr,10);
    }
}

7.2 三元组

思路：三元组和二元组的思路相同，我们每次先指定一个值，可以三元组问题转化为二元组问题。同样需要注意判断重复值的问题

public class FindAllThreeTuples {

    public static void findAllThreeTuples(int[] arr,int k){
        if(arr == null || arr.length < 3)
            return;
        for(int i = 0;i<arr.length - 2;i++){
            if(i==0 || arr[i] != arr[i-1]){
                int tmp = k - arr[i];
                int left = i + 1;
                int right = arr.length - 1;
                while(left < right){
                    if(arr[left] + arr[right] < tmp)
                        left++;
                    else if(arr[left] + arr[right] > tmp)
                        right--;
                    else{
                        if(left==i+1 || arr[left] != arr[left-1]){
                            System.out.println(arr[i] + "," + arr[left]+ "," + arr[right]);
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
    }

    public static void main(String[] args){
        int[] arr = {-8,-4,-3,0,1,2,4,5,8,9};
        findAllThreeTuples(arr,10);
    }
}

8、未排序数组中累加和为给定值的最长子数组长度

8.1 数组全为正数

思路：设置两个指针left和right，指针都从index=0的位置开始，指针的位置代表left-right的子数组的和。如果当前的和小于目标值，right++，如果大于目标值，则left++。

public class MaxLengthSubArrayWithSumK {

    public static int findMaxLengthSubArrayWithSumK(int[] arr,int k){
        if(arr==null || arr.length==0)
            return 0;
        int left = 0;
        int right = 0;
        int maxlen = 0;
        int sum = arr[0];
        while(right < arr.length){
            if(sum == k){
                maxlen = Math.max(maxlen,right-left+1);
                sum -= arr[left++];
            }
            else if(sum < k){
                right++;
                if(right == arr.length)
                    break;
                sum += arr[right];
            }
            else{
                sum -= arr[left];
                left++;
            }

        }
        return maxlen;
    }

    public static void main(String[] args){
        int[] arr = {1,2,1,1,1};
        System.out.println(findMaxLengthSubArrayWithSumK(arr,3));
    }
}

8.2 数组可正可负

思路：用一个map结构，map的key是sum值，代表数组从0到i的一个累积和，value是对应的sum第一次出现的位置index。很关键的一点是，我们要预先在map中存储一个(0,-1)。

public class MaxLengthSubArrayWithSumKV2 {
    public static int findMaxLengthSubArrayWithSumK(int[] arr,int k){
        if(arr==null || arr.length==0)
            return 0;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        map.put(0,-1);
        int maxlen = 0;
        int sum = 0;
        for(int i=0;i<arr.length;i++){
            sum += arr[i];
            if(map.containsKey(sum - k)){
                maxlen = Math.max(i-map.get(sum-k),maxlen);
            }
            if(!map.containsKey(sum)){
                map.put(sum,i);
            }
        }
        return maxlen;
    }

    public static void main(String[] args){
        int[] arr = {-1,1,2,0,1,1,1};
        System.out.println(findMaxLengthSubArrayWithSumK(arr,3));
    }
}

9、子数组的最大累积和问题

思路：

public class MaxCumSumSubArray {
    public static int findMaxCumSumSubArray(int[] arr){
        int maxCur = arr[0];
        int maxSoFar = arr[0];
        for(int i=1;i<arr.length;i++){
            maxCur = Math.max(arr[i],maxCur + arr[i]);
            maxSoFar = Math.max(maxCur,maxSoFar);
        }
        return maxSoFar;
    }

    public static void main(String[] args){
        int[] arr = {1,-2,3,5,-2,6,-1};
        System.out.println(findMaxCumSumSubArray(arr));
    }
}

10、子矩阵的最大累积和问题

思路：跟第九题一样的思路，我们把矩阵按列相加，转换为一维数组的问题即可。

public class MaxCumSumSubMatrix {

    public static int findMaxCumSumSubMatrix(int[][] arr){
        if(arr == null || arr.length == 0 || arr[0].length == 0)
            return 0;
        int max = Integer.MIN_VALUE;
        int cur = 0;
        int[] s = null;
        for(int i=0;i<arr.length;i++){
            s = new int[arr[0].length];
            for(int j = i;j<arr.length;j++){
                s[0] += arr[j][0];
                cur = s[0]; // 每一行开始的时候，都变成0
                max = Math.max(cur,max);
                for(int k = 1;k<s.length;k++){
                    s[k] += arr[j][k];
                    cur = Math.max(s[k] ,s[k] + cur);
                    max = Math.max(max,cur);
                }

            }
        }
        return max;
    }

    public static void main(String[] args){
        int[][] arr = {{-90,48,78},{64,-40,64},{-81,-7,66}};
        System.out.println(findMaxCumSumSubMatrix(arr));

    }
}

11、数组中子数组的累乘积

思路：维护两个值，一个是以i位置结尾的子数组最大乘积，一个是以i位置结尾的子数组最小乘积。

public class MaxCumMulitSubArray {

    public static double findMaxCumMultiSubArray(double[] arr){
        if(arr==null || arr.length==0)
            return 0;
        double max = arr[0];
        double min = arr[0];
        double res = arr[0];
        double maxEnd = 0;
        double minEnd = 0;

        for(int i = 1;i<arr.length;i++){
            maxEnd = max * arr[i];
            minEnd = min * arr[i];
            max = Math.max(Math.max(maxEnd,minEnd),arr[i]);
            min = Math.min(Math.min(maxEnd,minEnd),arr[i]);
            res = Math.max(max,res);
        }
        return res;
    }

    public static void main(String[] args){
        double[] arr = {-2.5,4,0,3,0.5,8,-1};
        System.out.println(findMaxCumMultiSubArray(arr));
    }
}

12、边界都是1的最大正方形大小

思路：维护两个数组，一个right，表示从i，j位置开始，向右最多有多少个连续的1，一个down，表示从i，j位置开始，向下最多有多少个连续的1。要想得到这两个数组，必须从原数组的右下角开始向上向左遍历。

public class MaxSquareWithAllOne {

    public static int findMaxSquareWithAllOne(int[][] arr){
        if(arr==null || arr.length==0 || arr[0].length ==0)
            return 0;
        int[][] right = new int[arr.length][arr[0].length];
        int[][] down = new int[arr.length][arr[0].length];
        for(int i =arr.length-1;i>=0;i--){
            for(int j=arr[0].length-1;j>=0;j--){
                if(i==arr.length-1 && j==arr[0].length-1){
                    right[i][j] = arr[i][j] == 1 ? 1:0;
                    down[i][j] = arr[i][j] == 1? 1:0;
                }
                else if(i==arr.length-1){
                    down[i][j] = arr[i][j] == 1?1:0;
                    right[i][j] = arr[i][j] == 1?right[i][j+1] + 1:0;
                }
                else if(j==arr.length-1){
                    right[i][j] = arr[i][j] == 1 ? 1:0;
                    down[i][j] = arr[i][j] == 1?down[i+1][j] + 1:0;
                }
                else{
                    down[i][j] = arr[i][j] == 1?down[i+1][j] + 1:0;
                    right[i][j] = arr[i][j] == 1?right[i][j+1] + 1:0;
                }
            }
        }
        int maxSize = 0;
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[0].length;j++){
                int n = Math.min(right[i][j],down[i][j]);
                for(int k=1;k<=n;k++){
                    if((j + k - 1) <arr[0].length && down[i][j+k-1] >= k && (i+k-1) < arr.length && right[i+k-1][j] >= k)
                        maxSize = Math.max(maxSize,k);
                }
            }
        }
        return maxSize;

    }

    public static void main(String[] args){
        int[][] arr = {{0,1,1,1,1},{0,1,0,0,1},{0,1,0,0,1},{0,1,1,1,1},{0,1,0,1,1}};
        System.out.println(findMaxSquareWithAllOne(arr));
    }
}

13、不包含本位置的累乘数组

思路：维护两个数组，left和right，left[i]表示数组从0到i-1位置的累乘，right[I]表示数组从i+1位置到数组结束的累乘值。最后将两个数组的对应位置相乘即可得到最后的结果。

public class ProductWIthoutSelf {

    public static void getProductWithOutSelf(int[] arr){
        if(arr==null || arr.length==0)
            return;
        int[] left = new int[arr.length];
        int[] right = new int[arr.length];
        int[] res = new int[arr.length];
        left[0] = 1;
        for(int i=1;i<arr.length;i++){
            left[i] = left[i-1] * arr[i-1];
        }
        right[arr.length-1] = 1;
        for(int i=arr.length-2;i>=0;i--){
            right[i] = right[i+1] * arr[i+1];
        }
        for(int i=0;i<arr.length;i++){
            res[i] = left[i] * right[i];
            System.out.println(res[i]);
        }

    }
    public static void main(String[] args){
        int[] arr = {2,3,1,4};
        getProductWithOutSelf(arr);
    }
}