Array

转圈打印矩阵

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

    // 左上边界
    int row = 0;
    int col = 0;
    // 右下边界
    int rowEnd = matrix.length - 1;
    int colEnd = matrix[0].length - 1;
    int i = 0;
    int j = 0;

    while (row <= rowEnd && col <= colEnd) {
        while (j < colEnd) {
            System.out.print(matrix[i][j++] + " ");
        }
        while (i < rowEnd) {
            System.out.print(matrix[i++][j] + " ");
        }
        while (j > col) {
            System.out.print(matrix[i][j--] + " ");
        }
        while (i > row) {
            System.out.print(matrix[i--][j] + " ");
        }
        i++;
        j++;
        row++;
        col++;
        rowEnd--;
        colEnd--;
    }
}

将正方形矩阵顺时针转动90°

思路：外层遍历交换，之后由外层向内层调整，继续遍历交换

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

    int temp;
    int begin = 0;
    int end = matrix.length - 1;
    int rowEnd = matrix.length - 1;
    int colEnd = matrix[0].length - 1;

    while (begin < end) {
        for (int i = begin; i < end; i++) {
            temp = matrix[begin][i];
            matrix[begin][i] = matrix[rowEnd - i][begin];
            matrix[rowEnd - i][begin] = matrix[end][colEnd - i];
            matrix[end][colEnd - i] = matrix[i][end];
            matrix[i][end] = temp;
        }
        begin++;
        end--;
    }
}

"之"字形打印矩阵

space = 1
二维矩阵 (5, 3) 代表5行3列，arr.length代表行数，arr[0].length代表列数

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

    // 上坐标 (tR, tC)
    int tR = 0;
    int tC = 0;
    // 下坐标 (dR, dC)
    int dR = 0;
    int dC = 0;
    // 打印方向
    boolean fromDown = Boolean.TRUE;
    int rowEnd = matrix.length - 1;
    int colEnd = matrix[0].length - 1;

    while (tR != rowEnd + 1) {
        printLevel(matrix, tR, tC, dR, dC, fromDown);
        // 向右或向下移动上坐标
        if (tC == colEnd) {
            tR++;
        } else {
            tC++;
        }
        // 向下或向右移动下坐标
        if (dR == rowEnd) {
            dC++;
        } else {
            dR++;
        }
        // 反向
        fromDown = fromDown ? Boolean.FALSE : Boolean.TRUE;
    }
}

// "之"字打印
private void printLevel(int[][] arr, int tR, int tC, int dR, int dC, boolean fromDown) {
    if (fromDown) {
        while (tR != dR + 1) {
            System.out.print(arr[dR--][dC++] + " ");
        }
    } else {
        while (dC != tC + 1) {
            System.out.print(arr[tR++][tC--] + " ");
        }
    }
}

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

time = O(n), space = O(1)
从右往左，始终保存遇到的最小值，如果出现遍历到的数比保存的最小值大，则记录这个坐标。
从左往右，始终保存遇到的最大值，如果出现遍历到的数比保存的最大值小，则记录这个坐标。
两坐标及中间的位置就是要进行排序的区间

public int getMinLength(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }

    int len = arr.length;
    int min = arr[len - 1];
    int left = -1;
    for (int i = len - 2; i != -1; i--) {
        if (arr[i] < min) {
            min = arr[i];
        } else {
            left = i;
        }
    }
    if (left == -1) {
        return 0;
    }
    
    int max = arr[0];
    int right = -1;
    for (int i = 1; i != len; i++) {
        if (arr[i] > max) {
            max = arr[i];
        } else {
            right = i;
        }
    }
    return right - left + 1;
}

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

time = M + N, space = 1

public boolean isContains(int[][] matrix, int k) {
    int row = 0;
    int col = matrix[0].length - 1;
        int xLen  = matrix.length;

    while (row < xLen && col > -1) {
        if (matrix[row][col] < k) {
            row++;
        } else if (matrix[row][col] > k) {
            col--;
        } else {
            return true;
        }
    }
    return false;
}

自然数数组的排序

time = N, space = 1

public void sort1(int[] arr) {
    int tmp;
    for (int i = 0; i != arr.length; i++) {
        if (arr[i] != i + 1) {
            tmp  = arr[i];
            arr[i] = arr[tmp  - 1];
            arr[tmp  - 1] = tmp ;
        }
    }
}

奇数下标都是奇数或者偶数下标都是偶数

time = N, space = 1
思路：判断末尾奇偶并交换

public void modify(int[] arr) {
    if (arr == null || arr.length <2) {
        return;
    }
    
    // 偶数下标
    int even = 0;
    // 奇数下标
    int odd = 1;
    int end = arr.length - 1;
    
    while (even != end && odd != end) {
        if ((arr[end] & 1) == 0) {
            swap(arr, end, even);
            even += 2;
        } else {
            swap(arr, end, odd);
            odd += 2;
        }
    }
}

public void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

子数组的最大累加和问题

要求：time = N,space = 1

public int maxcur(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }

    // 考虑到数组可能数值为负的情况 ，这里必须给到最小整数
    int max = Integer.MIN_VALUE;
    int cur = 0;

    for (int i : arr) {
        cur += i;
        max = Math.max(cur, max);
        cur = cur < 0 ? 0 : cur;
    }
    return max;
}

不包含本位置值的累乘数组

time = N, space = 1
注：要考虑0对累乘的影响

public int[] product1(int[] arr) {
    if (arr == null || arr.length < 2) {
        return null;
    }

    // 数字所有非零数累乘值
    int all = 1;
    // 数组中0的个数
    int count = 0;
    
    for (int i : arr) {
        if (i == 0) {
            count++;
        } else {
            all *= i;
        }
    }

    int[] res = new int[arr.length];
    if (count == 0) {
        for (int i = 0; i != arr.length; i++) {
            arr[i] = all / arr[i];
        }
    }
    // 如果数组中有1个0，0位置为all / arr[i]，非0位置置为0
    if (count == 1) {
        for (int i = 0; i != arr.length; i++) {
            res[i] = arr[i] == 0 ? all : res[i];
        }
    }
    // 如果数组中有2个或以上0，全都是0
    return res;
}

数组的partition调整

time = N, space = 1
注：swap操作单独写一个函数出来，写完代码可以优化，缩减代码行数，使得代码看起来更加精炼简短

public void leftUnique(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int pre = 0;
    int i = 1;
    while (i != arr.length) {
        if (arr[pre] != arr[i++]) {
            swap(arr, ++pre, i - 1);
        }
    }
}

public void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}