【10天刷题计划】阿里巴巴常考面试算法题（一）

阿里巴巴常考的面试算法题，比如LRT缓存机制，无重复字符的最长子串，比较版本号等......

三石说

1269人浏览 · 2022-01-09 22:42:11

三石说 · 2022-01-09 22:42:11 发布

题目列表

自上而下面试考到的频次由高到低

解题思路

第一天

LRU缓存机制

第一种方法：直接继承LinkedHashMap<Integer, Integer>, 它里面有一个特性，就是如果指定了accessOrder为true，那么每次get之后，这个节点就会被放到链表的尾部，并且每次在put完的时候，都会调用一下afterNodeInsertion方法，这里面又调用removeEldestEntry(first)表示是否移除第一个节点，所以我们可以重写这个方法，让容量超过capcity的时候，删除第一个节点。
第二种方法：自实现LinkedHashMap，也就是通过HashMap+双链表就可以完成，主要就是在实现put和get方法的时候要注意是否需要移动当前节点到链表的尾部，这其中的逻辑要注意一下就行了。同时还有一个设置伪头部和伪尾部节点的技巧，方便边界的统一处理

无重复字符的最长子串

题目是要求一个最长的子串，连续的，立马想到滑动窗口
- 定义左右两个指针l和r
- 什么时候开始移动左指针呢？
  - 当右指针指向的字符在窗口中的个数超过1的时候
- 什么时候记录当前窗口的最优解呢？
  - 本题可以在收缩窗口之后进行记录（有些是在收缩窗口内进行更新）

两数之和

用一个hashmap就可以了，保存元素到下标的映射
扩展：
- 三数之和：排序+一层循环+双指针
- 四数之和：排序+二层循环+双指针

数组中的第K个最大元素

基于快速排序的模板进行改进就可以了

// 快速排序模板
if (low >= high)
    return;
int i = low;
int j = high;
int pivot = arr[i]; // 选择当前区间的第一个元素作为基准元素
while (i < j) {
    while (i < j && arr[j] >= pivot)// 从后向前
        j--;
    swap(arr, i, j);
    while (i < j && arr[i] <= pivot)// 从前向后
        i++;
    swap(arr, i, j);
}
quickSort(arr, low, j - 1);
quickSort(arr, j + 1, high);
// 改进计算第k个最大元素
// 在while循环之后，判断枢纽之前共有多少个数字，如果大于等于k，那么第k大的数字一定位于前半部分，否则，位于后半部分
int s = i - low + 1;
if (s >= k)
	return quickSort(nums, k, low, i);
else
	return quickSort(nums, k - s, i + 1, high);

反转链表

双指针：第一个指针指向head的前一个节点也就是空，记为prev；第二个指针指向head节点，记为cur。

第二天

三数之和

排序+一层循环+双指针
如果采用暴力法，那么就是三重循环，时间复杂度为O(n^3)，那么经过优化采用双指针技巧，就可以让时间复杂度减小为O(n^2)
能够用双指针也是因为前面进行了数组的排序，我们就可以首先固定第一个值，然后双指针判断第二个值和第三个值，当三者之和等于0，就将这三个值加入结果集中，当三者之和大于0，那么就要将右指针左移，当三者之和小于0，那么就要将左指针右移

二叉树的层序遍历

模板题，非常重要！！！

List<List<Integer>> res = new ArrayList<>();
if (root == null)
    return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    List<Integer> path = new ArrayList<>();
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        TreeNode tmp = queue.poll();
        path.add(tmp.val);
        if (tmp.left != null)
            queue.offer(tmp.left);
        if (tmp.right != null)
            queue.offer(tmp.right);
    }
    res.add(path);
}
return res;

比较版本号

利用双指针法
- 先对版本号进行切分，然后利用两个指针分别指向两个版本号，依次进行比较（需要两个版本长短不一致的问题）

二叉树的中序遍历

这个递归法想必大家都会写，但是面试官有时候会让你用迭代法实现中序遍历。

List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
    if (cur != null) {
        stack.push(cur);
        cur = cur.left;
    } else {
        cur = stack.pop();
        ans.add(cur.val);
        cur = cur.right;
    }
}
return ans;