转圈打印矩阵
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;
}
