一般ArrayList面试考点都在考察应聘者是否知道ArrayList底层是数组，优缺点，各种操作的时间复杂度，最后是跟其他容器的区别。
而笔试单独考察比较少，会借着数组的特定排序，考察应聘者是否会充分利用数组的优点。
我们来看看leetcode的第905题按奇偶排序数组：
//给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
//
// 你可以返回满足此条件的任何数组作为答案。
//
//
//
// 示例：
//
// 输入：[3,1,2,4]
//输出：[2,4,3,1]
//输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
//
//
//
//
// 提示：
//
//
// 1 <= A.length <= 5000
// 0 <= A[i] <= 5000
//
// Related Topics 数组
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int[] sortArrayByParity(int[] A) {
}
}
//leetcode submit region end(Prohibit modification and deletion)
如果我们不考虑数组的优缺点，不考虑性能，不考虑空间，这样做最简单：
- 新建一个跟A长度一样的数组res
- 遍历2遍数组A，第一遍把偶数都插入res，第二遍把奇数都插入到res
- 最后返回res
但是，我们在上一篇学过，数组最擅长是按索引随机访问，时间复杂度都是O(1)的。如果能把前面的奇数与后面的偶数交换，不就可以节省空间和时间吗？
那么，我们再仔细读读这句话：
把前面的奇数与后面的偶数交换
那我们可以同时准备2个索引，一个从前往后，另一个从后往前，同时遍历数组，当前面发现奇数就停下来，当后面发现偶数也停下来，然后2个数交换，继续，一直到2个索引相等，不就完成了吗？
好，下面我们整理下思路：
- 准备2个索引
- 同时遍历数组，一个从前往后，另一个从后往前
- 当前面索引发现奇数就停下来
- 当后面索引发现偶数也停下来
- 前后两数交换
- 2个索引相等时候退出
class Solution {
public int[] sortArrayByParity(int[] A) {
// 准备2个索引
int left = 0;
int right = A.length - 1;
// 同时遍历数组，2个索引相等时候退出
while (left < right) {
// 一个索引从左往右，当左索引发现奇数就停下来
while (A[left] % 2 == 0 && left < right) {
left++;
}
// 一个索引从右往左，当右索引发现偶数也停下来
while (A[right] % 2 > 0 && left < right) {
right--;
}
// 前后两数交换
if (left < right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
}
}
return A;
}
}
提交下，通过了，各方面都还不错。
Runtime: 1 ms, faster than 99.97% of Java online submissions for Sort Array By Parity.
Memory Usage: 41.4 MB, less than 77.78% of Java online submissions for Sort Array By Parity.
当然，不仅仅是左右索引，用奇偶索引一起从左边开始也是可以的。我们就不再用代码详述了。
所以，一般遇到数组排序，都是考虑充分利用数组索引访问O(1)的特性，进行解题，这样一般解出来的题目性能都不会差。
我们再来看一题118. 杨辉三角，还是用到ArrayList的通过索引访问是最快的，这样一个特性，来降低代码复杂度。
//给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
//
//
//
// 在杨辉三角中，每个数是它左上方和右上方的数的和。
//
// 示例:
//
// 输入: 5
//输出:
//[
// [1],
// [1,1],
// [1,2,1],
// [1,3,3,1],
// [1,4,6,4,1]
//]
// Related Topics 数组
我们先观察下，每一行是一个数组。每个数组第一个数值是1。以后每个索引j对应的数值，就是上一个数组的索引j-1的数值，加上索引j的数值。
很绕口对吧，假设第一个数组是A，第二个数组是B，那么：
B[ j ] = A[ j-1 ] + A[ j ]
所以代码如下：
import java.util.ArrayList;
import java.util.List;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<List<Integer>> generate(int numRows) {
// 先准备一个数组
List<Integer> arrayList = new ArrayList<>();
// 保存返回的结果
List<List<Integer>> listListRet = new ArrayList<List<Integer>>();
// 用户输入多少行，就生成多少数组
for (int i = 0; i < numRows; i++) {
// 每个数组第一个数固定是1
arrayList.add(0, 1);
// 每个数组第二个数开始，都根据规律计算即可
for (int j = 1; j < i; j++) {
// 这里的 j 是上一个数组的索引，所以计算下一个数组数值就是 B[j] = A[j] + A[j+1]
arrayList.set(j, arrayList.get(j) + arrayList.get(j+1));
}
//System.out.println(arrayList.toString());
// 保存每一行生成的结果
listListRet.add(new ArrayList<Integer>(arrayList));
}
//System.out.println(listListRet.toString());
return listListRet;
}
}
//leetcode submit region end(Prohibit modification and deletion)
提交看看结果，看来还不错。
执行结果：通过 显示详情
执行用时 :1 ms, 在所有 Java 提交中击败了99.05%的用户
内存消耗 :33.7 MB, 在所有 Java 提交中击败了90.02%的用户
网友评论