【大厂秋招高频算法】阿里秋招高频算法题汇总

欢迎关注公众号（通过文章导读关注：【11来了】），及时收到 AI 前沿项目工具及新技术的推送！

在我后台回复 「资料」 可领取编程高频电子书！
在我后台回复「面试」可领取硬核面试笔记！

文章导读地址：点击查看文章导读！

感谢你的关注！

阿里秋招高频算法题汇总！

这里讲一下阿里秋招中的高频算法题，分为三个部分： 基础篇 、 中级篇 、 进阶篇

目的就是为了应对秋招中的算法题，其实过算法题的诀窍就在于 理解的基础上 + 背会

看到一个题目，首先要了解题目考察的算法是什么，这个算法要理解，至于具体实现的话，就靠背会了（多写、多练），没有什么捷径！

还有一点要注意的是，在大厂的比试中， 可能考察算法的方式是 ACM 模式 ，这一点和力扣上不同，ACM 模式需要我们自己去引入对应的包，以及自己写算法，力扣是将方法框架给定，只需要在方法内写代码就可以了，这一点要注意！

接下来开始阿里秋招算法的算法讲解，文章内的题目都在 LeetCode 上，因此这里只列出对应的题目序号、题目简介！

基础篇

在基础篇中考察算法更偏向于基础的数据结构，以及 dfs，包括：

• 深度优先搜索：dfs
• 队列
• 动态规划：dp
• 栈

LC 225. 用队列实现栈（简单）

这个考察就是基础数据结构是否会应用 ，题目要求：使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）

实现思路比较简单，队列是 先进先出 ，而栈是 先进后出 ，那么使用队列模拟栈的话，只要使用两个队列，使用【队列1】作为中转，添加的新元素先加入【队列1】，再将【队列2】的元素加入到【队列1】的后边，这样在【队列1】中添加的新元素就在第一个的位置，可以实现栈 最后加入的元素最先被弹出 的特性！

流程如下：

步骤1：先加入元素 A，【队列1】作为中转，因此元素 A 先加入【队列1】

步骤2：再加入元素 B，将 B 先加入【队列1】，此时元素 B 是在第一个位置，再将【队列2】中的元素 A 加入到【队列1】，此时元素顺序就被反转了，符合栈 后入先出 的顺序

可以看到，元素 A 先入队，在队列 2 弹出的时候，元素 A 是最后弹出的，和栈的特性一致，接下来看一下代码实现，注释已经放在代码中了：

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
        // 初始化两个队列
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    // 向栈中加入元素
    public void push(int x) {
        // 先加入到队列 1 中，队列 1 作为一个中转的作用
        q1.offer(x);
        // 将队列 2 的元素一个一个放入队列 1，这样在队列 1 中最后加入的元素其实是在第一个的位置，实现了栈的特性
        while (!q2.isEmpty()) {
            q1.offer(q2.poll());
        }
        // 交换两个队列
        Queue<Integer> tmp = new LinkedList<>();
        tmp = q1;
        q1 = q2;
        q2 = tmp;
    }

    public int pop() {
        // 弹出队列 2 的元素，并返回
        return q2.poll();
    }

    public int top() {
        // 返回队列 2 的队头元素，不弹出
        return q2.peek();
    }

    public boolean empty() {
        // 判空
        return q2.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

LC 44. 通配符匹配（困难）

这个题目是进行字符串匹配，使用 动态规划 DP 来做

动态规划类的问题怎么学？

动态规划类的问题比较吃经验，做的题目如果少的话，看到新的题目一般都是做不出来的，所以对于动态规划类的问题，建议是把我们写过的题型给记住，知道他们的状态是如何转移的，这样就够了，毕竟我们是学习的，并不是发明创造算法的！

题目大致意思就是给定一个字符串 s 和字符模式 p，p 中有通配符 ? 和 * ：

• ? 匹配单个字符
• * 匹配任意字符

答案输出 s 和 p 是否匹配

比如

s = "abc"
p = "a?c"
输出：true 表示 匹配
s = "abc"
p = "*"
输出：true 表示 匹配

首先定义动态规划数组 dp[n][m] ，dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配

那么主要分为两种情况：

• 第一种情况：p[j] != * ，如果 p[j] 不是 * 的话

  • 当 p[j] == s[j] 或者 p[j] == ''?' ，此时 s[i] 和 p[j] 是匹配的，那么此时 dp[i][j] 的状态由 dp[i-1][j-1] 转移过来

• 第二种情况：p[j] == * ，这种情况比较复杂，因为我们并不清楚这个 * 到底可以匹配多少个字符，可能匹配 0 个、1个、… j 个字符，如下：

  • 如果匹配 0 个字符，dp[i][j] = dp[i][j-1]
  • 如果匹配 1 个字符，dp[i][j] = dp[i-1][j-1]
  • 如果匹配 2 个字符，dp[i][j] = dp[i-2][j-1]

  那么这样的话，计算 dp 的状态还需要再次遍历一下 i，时间复杂度比较高，因此这里简化一下

  dp[i-1][j] 的状态其实是由 dp[i-1][j-1]、dp[i-2][j-1]... 转移过来，那么这里可以发现 dp[i-1][j] 的状态就符合了上边匹配 1 个、2 个字符的情况，因此这里就不需要进行循环了，此时 dp[i][j] 的状态如下：

  • 如果匹配 0 个字符，dp[i][j] = dp[i][j-1]
  • 如果匹配 1 个、2 个…多个字符，dp[i][j] = dp[i-1][j]

  所以这里 dp 的状态转换简化为： dp[i][j] = dp[i][j-1] && dp[i-1][j]

综上，DP 状态转移主要分为两个状态：

• p[j] != '*' 时，dp[i][j] = dp[i-1][j-1]
• p[j] == '*' 时，dp[i][j] = dp[i][j-1] && dp[i-1][j]

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        s = " " + s;
        p = " " + p;
        char[] s1 = s.toCharArray();
        char[] p1 = p.toCharArray();
        boolean[][] dp = new boolean[n+1][m+1];
        // 状态初始化，这个状态影响着后边的状态，所以需要初始化一下
        dp[0][0] = true;

        // i 从 0 开始遍历，因为 dp[0][j] 表示如果 s 串为空串，p 是否匹配 s，这其实是有可能会匹配的，如果 p 全是 * 的话，会匹配
        // 因此 i 从 0 开始遍历，需要对 dp[0][j] 的状态进行设置
        for (int i = 0; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                if (i > 0 && (s1[i] == p1[j] || p1[j] == '?')) {
                    // 如果字符相等，或者是 ? 通用匹配符的话，dp[i][j] 的状态从 dp[i-1][j-1] 转移而来
                    dp[i][j] = dp[i-1][j-1];
                } else if (p1[j] == '*') {
                    // 这里表示 p[j] 为 * 匹配 0 个字符的情况
                    dp[i][j] = dp[i][j-1];
                    if (i > 0) {
                        // dp[i-1][j] 表示 p[j] 为 * 匹配 1 个、2个...多个字符的情况
                        dp[i][j] = dp[i][j] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[n][m];
    }
}

LC 78. 子集（中等）

这道题是给定一个数组，让你返回所有的子数组，示例输入输出如下：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

可以看到，就是通过不同的排列组合，将所有可能的情况给查出来就好了

这里使用 二进制枚举 来做，对于 nums 数组种的每一位都可能取或者不取，这样就可以枚举出来所有的子数组了，二进制枚举也是比较常用的算法

这里画图举个例子：

可以看到，只需要 枚举所有的二进制 就可以枚举出来所有的子数组了

这里怎么枚举所有的二进制呢？

比如说 nums 数组长度为 3，那么只需要从 0 遍历到 1 <<< 3 - 1 也就是从 0 遍历到 7，这样就可以将所有的二进制全部遍历出来了

代码如下：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        // 枚举所有的二进制
        for (int i = 0; i < 1 << n; i++) {
            List<Integer> tmp = new ArrayList<>();
            // 遍历每一位
            for (int j = 0; j < n; j ++) {
                // 如果第 j 位是 1，表示子数组取这一位，加入到子数组 tmp 中去
                if ((i >> j & 1) == 1) {
                    tmp.add(nums[j]);
                }
            }
            res.add(tmp);
        }
        return res;
    }
}

LC 145. 二叉树的后序遍历（简单）

二叉树的遍历其实还是比较容易考察的，这里写两版代码：

• dfs 解决：使用 dfs 解决的话，比较方便
• 迭代解决：迭代解决的话，需要我们手动记录上次访问的节点，来手动实现回溯，因此稍微麻烦一些

后序遍历的话就是先遍历左子树，再遍历右子树，最后遍历根节点，也就是 LRN

dfs 实现

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        dfs(root);
        return res;
    }

    void dfs(TreeNode root) {
        // 如果到空节点了，就不接着往下走了，返回
        if (root == null) return;
        // 先遍历左子树
        dfs(root.left);
        // 再遍历右子树
        dfs(root.right);
        // 最后是根节点
        res.add(root.val);
    }
}

迭代实现

迭代实现的话，需要我们手动记录上一次节点，来实现回溯

首先要使用栈来记录我们遍历的节点，这里使用链表来模拟栈

之后一直向左子树遍历，当没有左子树之后，就向右子树遍历，在右子树中也还是先向左子树遍历再向右子树遍历

这里定义了 last 节点 来记录回溯的上一个节点，避免回溯之后，由继续向下遍历，导致死循环

这里为了回溯，使用了栈，将元素都推入栈中，当遍历到最底层之后，再从栈中取出元素进行回溯即可！

代码的话，实现的比较精妙（如果有不理解的地方，直接背了就好了，因为这类题型其实是比较固定的），看着流程，自己模拟画图一下就好了， 注意在理解的基础上，可以自己手敲个 3-5 遍，提升一下印象！

class Solution {

    public List<Integer> postorderTraversal(TreeNode root) {
        // 这里使用链表来模拟栈了
        LinkedList<TreeNode> s = new LinkedList<>();
        TreeNode now = root;
        TreeNode last = null;
        List<Integer> res = new ArrayList<>();
        // 如果当前节点为空，并且栈中没有元素了，说明所有元素都遍历完毕了
        while (now != null || !s.isEmpty()) {
            // 如果当前节点不是空，就都压入到栈中
            if (now != null) {
                s.addFirst(now);
                now = now.left;
            } else {
                now = s.getFirst();
                // 如果还有右子树，就往右子树遍历
                // last != now.right 表示可能刚刚才从右子树遍历完回到当前节点，既然回溯了，如果继续向右子树遍历，就反复横跳，死循环了
                if (now.right != null && last != now.right) {
                    now = now.right;
                } else {
                    // 到了这个 if 分支，说明右子树已经为空，或者已经遍历过右子树了
                    // 于是将当前节点加入数组
                    now = s.removeFirst();
                    res.add(now.val);
                    last = now;
                    // 这里将 now 定义为 null，避免重入压入到栈中
                    now = null;
                }
            }
        }
        return res;
    }
}

LC 268. 丢失的数字（简单）

这个题目比较简单了，给定一个数组，长度为 n，找出来 [0, n] 范围内的数字，哪一个数字没有在数组中出现

这里题目给定的数据范围 n 最大为 10⁴ ，所以直接声明一个长度为 n+1 的数组，如果出现过的数字标记为 true，再遍历一遍，标位为 fasle 的表明在数组中没有出现，如下图：

代码如下：

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        // 标记数组 0-n
        boolean[] flag = new boolean[n + 1];
        for (int i = 0; i < n; i ++) {
            // 取出 nums[i] 的值，作为下标，在 flag 数组标记
            int idx = nums[i];
            flag[idx] = true;
        }
        for (int i = 0; i <= n; i ++) {
            // 如果标记为 false，说明这个下标没有在 nums 中出现，返回即可
            if (flag[i] == false) {
                return i;
            }
        }
        return -1;
    }
}

LC 344. 反转字符串（简单）

这道题也是简单题，对字符串反转

反转前：hello
反转后：olleh

不过这道题目有一点要求， 只能原地反转 ，不可以定义额外的数组进行操作，因此这里使用 递归 来做

定义一个递归函数 dfs(char[] s, int l, int r) 表示将 s[l] 和 s[r] 进行互换，只要将两边的所有字符串都互换一下就可以了

代码如下：

class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        // 对 0 和 n-1 位置上的字符互换
        dfs(s, 0, n-1);
    }
    // dfs(s, i, j) 就是将 s[i] 和 s[j] 互换
    public void dfs(char[] s, int l, int r) {
        // 如果左指针 >= 右指针，就不需要反转了，退出递归就好
        if (l >= r) return;

        // 将 left 和 right 位置上的字符串互换进行反转
        char tmp = s[l];
        s[l] = s[r];
        s[r] = tmp;
        dfs(s, l + 1, r - 1);
    }
}

LC 350. 两个数组的交集 II（简单）

这道题目是返回两个数组的交集

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

如下：

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums1.length;
        int m = nums2.length;
        for (int i = 0; i < n; i ++) {
            map.put(nums1[i], map.getOrDefault(nums1[i], 0) + 1);
        }
        // 记录交集的数的下标
        int k = 0; 
        for (int i = 0; i < m; i ++) {
            // map 中记录了 nums1 中的所有数字出现的次数
            if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
                nums1[k ++] = nums2[i];
                // 已经放入到交集数组中了，因此对 nums1 中出现的次数减 1
                map.put(nums2[i], map.get(nums2[i]) - 1);
            }
        }
        // 交集放在了 nums1 数组的 [0, k) 的位置上
        return Arrays.copyOfRange(nums1, 0, k);
    }
}

LC 557. 反转字符串中的单词 III（简单）

这道题目就是让反转字符串中的每一个单词：

输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

像这一种反转类的题目都可以使用 栈 来做，比如 hello ，按顺序压入栈为：hello，再一个个弹出顺序就反过来为：olleh

这里使用链表来模拟栈了，只操作一边就可以了

class Solution {
    public String reverseWords(String s) {
        StringBuilder res = new StringBuilder("");
        // 使用链表模拟栈
        LinkedList<Character> stack = new LinkedList<>();
        int i = 0, n = s.length();
        while (i < n) {
            while (i < n && s.charAt(i) != ' ') {
                stack.addFirst(s.charAt(i));
                i ++;
            }
            while(!stack.isEmpty()) {
                res.append(stack.removeFirst());
            }
            if (i < n) {
                res.append(" ");
            }
            i ++;
        }
        return res.toString();
    }
}

LC 617. 合并二叉树（简单）

给定两个二叉树，对两个二叉树进行合并，重叠的节点合并为两个节点相加的值，否则，合并为不为 null 的节点值，如下：

使用 dfs 来做，两个树一起递归就可以了，分为三种情况：

• 其中一个树为 null，返回不为 null 的节点
• 两个节点都为 null，返回 null
• 两个节点都不为 null，返回节点相加的值

这里前两种情况可以合并，如果有一个节点为 null，返回另一个节点就可以了，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 递归，需要做空判断及时返回
        if (root1 == null) return root2;
        if (root2 == null) return root1;
        // 对两个节点合并
        TreeNode mergedNode = new TreeNode(root1.val + root2.val);
        // 对左子树合并
        mergedNode.left = mergeTrees(root1.left, root2.left);
        // 对右子树合并
        mergedNode.right = mergeTrees(root1.right, root2.right);
        return mergedNode;
    }
}