套路
纯数组问题通常分为两类解决：
- 单纯考察代码实现能力，（新建数组）往往是对现实的抽象建模。只要注意中间不出数组越界问题把所有可能的分支和边界情况处理好就可以了。
- 新要保存的标记或建数组作为容器，存放一些需者值来辅助运算。
注意点
- 小心数组下标越界问题
- 逻辑复杂时，带入简单的通用demo和特殊情况demo辅助检验
- 返回值要求为数组的题目里，尽量不要直接返回null，这样不好。我们可以返回一个空数组，即长度为0的数组，写法是：return new int[0];
- 返回动态数组也是，如果可以返回空的动态数组，尽量不要返回null，返回null值不是一个好的习惯。
- 如果要求答案为不止一个值时，如果其他值可以通过前面的值得到帮助，缩短求值步骤，那么尽量不要重新计算，利用已求得的答案求解，可以使代码的时间复杂度达到最低。
目录
- 构建乘积数组（最优解还需要练习）
- 顺时针打印矩阵
- 旋转数组的最小数字
- 和为S的两个数字
- 孩子们的游戏(圆圈中最后剩下的数)（代码实现还需要练习）
构建乘积数组
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。
- 常规解法：穷举法。时间复杂度 O(n^2)
- 最优解法：B [ i ] 利用现成的 B [ i - 1 ] 的结果进行计算，从而降低时间复杂度。时间复杂度 O(n)
public int[] multiply(int[] A) {
if (A == null || A.length == 0) {
return new int[0];
}
int n = A.length, temp = 1;
int[] B = new int[n];
B[0] = 1;
for (int i = 1; i < n; i++) {
B[i] = B[i - 1] * A[i - 1];
}
for (int j = n - 2; j >= 0; j--) {
temp *= A[j + 1];
B[j] *= temp;
}
return B;
}
顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
- 考察代码实现能力
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
if (matrix == null || matrix[0] == null) {
return list;
}
int i = 0, j = 0;
int iMax = matrix.length, jMax = matrix[0].length;
int iCur = iMax - 1, jCur = jMax - 1;
// 矩阵宽高大于1
while (iCur > 0 && jCur > 0) {
for (int k = 0; k < jCur; k++) {
list.add(matrix[i][j++]);
}
for (int k = 0; k < iCur; k++) {
list.add(matrix[i++][j]);
}
for (int k = 0; k < jCur; k++) {
list.add(matrix[i][j--]);
}
for (int k = 0; k < iCur; k++) {
list.add(matrix[i--][j]);
}
i++;
j++;
iCur -= 2;
jCur -= 2;
}
// 矩阵宽高等于1
if (iCur == 0 && jCur == 0) {
list.add(matrix[i][j]);
// 矩阵高为1
} else if (iCur == 0) {
for (int k = 0; k <= jCur; k++) {
list.add(matrix[i][j++]);
}
// 矩阵宽为1
} else if (jCur == 0) {
for (int k = 0; k <= iCur; k++) {
list.add(matrix[i++][j]);
}
}
return list;
}
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
- 最优解：时间复杂度 O（n），平均执行时间是数组长度的一半。
public int minNumberInRotateArray(int [] array) {
if (array == null || array.length == 0) {
return 0;
}
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
return array[i];
}
}
return array[0];
}
和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> res = new ArrayList<>();
if (array == null || array.length < 2) {
return res;
}
int left = 0, right = array.length - 1;
while (left < right) {
int ans = array[left] + array[right];
if (ans < sum) {
left++;
} else if (ans > sum) {
right--;
} else {
res.add(array[left]);
res.add(array[right]);
return res;
}
}
return res;
}
孩子们的游戏(圆圈中最后剩下的数)
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
public int LastRemaining_Solution(int n, int m) {
if (n <= 0 || m <= 0) {
return -1;
}
// 模拟0~n-1个孩子
int[] arr = new int[n];
// count代表圈中孩子的个数，i代表报数的位置, step代表每轮报数的孩子个数
int count = n, i = 0, step = 1;
while (count > 0) {
i++;
if (i == n) {
i = 0;
}
if (arr[i] == -1) {
continue;
}
step++;
if (step == m) {
// 赋值为-1代表出列
arr[i] = -1;
count--;
step = 0;
}
}
return i;
}
