【大厂秋招高频算法】阿里秋招高频算法题汇总（进阶篇）

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

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

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

感谢你的关注！

阿里秋招高频算法题汇总（进阶篇）

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

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

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

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

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

进阶篇

在进阶篇中主要考察的算法更加偏向于 动态规划 、 DFS 、 双指针 这几个方面，这些都是高频考点：

动态规划（高频考点）
DFS（高频考点）
双指针（高频考点）

LC 237. 删除链表中的节点（中等）

题目描述：

现在有一个单链表，给定一个 node 节点，让你删除这个 node 节点

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

题目给定 node 节点，并没有给定这个单链表的 head 节点，因此你是无法找到 node 节点的前置节点，所以肯定 无法删除 node 节点

解题思路就是将 node 节点的下一个节点值赋给当前 node 节点，将 node 的下一个节点删除掉

（这道题感觉有点像脑筋急转弯）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

LC 152. 乘积最大子数组（中等）

题目描述：

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

首先要找到乘积最大的子数组，那么这个最大成绩可能是 任何个区间内 的子数组的乘积

先说一下 暴力解法 ，只需要出来所有的子区间，再去计算乘积就好了，这个暴力解法的时间复杂度是 O(N³) ，比较高，所以考虑优化一下

使用 动态规划 来进行优化：

f[i] 表示在数组 0-i 中，选取 nums[i] 时的最大乘积
g[i] 表示在数组 0-i 中，选取 nums[i] 时的最小乘积

题目中给出的数都是整数，没有小数，所以乘积的绝对值只要不碰到 0 就会越来越大，那么我们可以使用 f[i] 记录从 0 到 i 的最大的乘积，使用 g[i] 记录从 0 到 i 的最小的乘积，那么遍历数组，就有两种情况：

如果当前 nums[i] 不是 0，于是取 $f [i] = ma x (n u m s [i] * f [i - 1], n u m s [i] * g [i - 1])$ ，取 $g [i] = min (n u m s [i] * f [i - 1], n u m s [i] * g [i - 1])$ ，这样就可以维护 f 和 g 数组的值了
如果当前 nums[i] 是 0，那么 nums[i] 和任意数乘积都为 0，那么就是当前区间就被隔断了，接着从下一个区间开始计算就好（如果不理解，可以手动计算一下就好）

计算流程如下：

可以发现， f[i] 的状态只与 f[i-1] 有关，因此还可以进行空间优化，这里就不需要维护一个数组了，直接使用 f 变量来进行状态转移就好了

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int f = 1;
        int g = 1;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i ++) {
            // 计算和最大乘积相乘的结果
            int fi = nums[i] * f;
            // 计算和最小乘积相乘的结果
            int gi = nums[i] * g;
            // 如果 nums[i-1] 是 0 的话，那么 fi 一定是 0，这里计算最大乘积的话，就不能和 fi 相乘了
            // 因此如果 fi 和 gi 是 0 的话，那么这里还要和 nums[i] 判断一下取最大值
            f = Math.max(nums[i], Math.max(fi, gi));
            g = Math.min(nums[i], Math.min(fi, gi));
            // 每一次子区间都计算一下最大值
            res = Math.max(f, res);
        }
        return res;
    }
}

LC 279. 完全平方数（中等）

题目描述：

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

这道题目使用 动态规划 来解，对于给定的 n 来说，并不知道它是由几个完全平方数组成的，所以如果暴力计算的话，时间复杂度是比较高的，使用 动态规划 进行状态转移来优化

定义动态规划数组 f[i] ：

f[i] 表示组成 i 的完全平方数的最少个数

对于 i 来说，最差情况下就是由 i 个 1 组成，所以可以初始化 f[i] = i

状态转移 的话，对于 i 来枚举 j ，转移方程为： $f [i] = min (f [i], f [i - j * j] + 1)$

也就是 f[i] 的状态可以由 f[i- j*j] 转移而来，j*j 也是一个完全平方数，因此 $f [i] = f [i - j * j] + 1$

class Solution {
    public int numSquares(int n) {
        int[] f = new int[n+1];
        for (int i = 1; i <= n; i ++) {
            f[i] = i;
            // 枚举 j 的话，注意控制条件 i-j*j >= 0，避免数组越界
            for (int j = 1; i - j * j >= 0; j ++) {
                // 状态转移
                f[i] = Math.min(f[i], f[i- j*j] + 1);
            }
        }
        return f[n];
    }
}

LC 93. 复原 IP 地址（中等）

题目描述：

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

这道题目中，限制了 s 字符串的长度最大为 20，所以可以直接 dfs 暴力接触所有情况就可以

ip 地址由 4 个整数组成，我们就去枚举每一个数，当枚举完 4 个数之后，并且遍历完了整个 s 字符串，说明这次的 ip 是合法的，加入到结果集中

这里枚举数的时候，还要注意不能有前导 0，并且不能超过 255

代码如下：

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        dfs(0, 0, s, "");
        return res;
    }
    // u：已经枚举的整数的个数
    // k：枚举到 s 中的下标
    // cur：当前已经组好的 ip 地址
    public void dfs(int u, int k, String s, String cur) {
        // 如果枚举完 4 个数
        if (u == 4) {
            // 并且已经遍历完 s 字符串
            if (k == s.length()) {
                // 这里将 cur 的最后一个 . 给截取掉
                res.add(cur.substring(0, cur.length() - 1));
            }
            // 定义递归终点
            return;
        }

        // 计算当前这一个整数的值
        int sum = 0;
        // 从下标 k 开始枚举当前这一个整数的值
        for (int i = k; i < s.length(); i ++) {
            // 如果第 k 位是 0，由于不能有前导 0，因此 0 后边不可以跟其他数了，直接 break 掉就好
            if (i > k && s.charAt(k) == '0') break;
            // 上一位作为十分位了，因此乘上 10，计算这一个整数的和
            sum = sum * 10 + s.charAt(i) - '0';
            // 如果 sum <= 255 的话，这一位是合法的，递归继续搜
            if (sum <= 255) dfs(u + 1, i + 1, s, cur + String.valueOf(sum) + ".");
            // 如果 sum 超过 255 的话，已经不合法了，没必要递归搜索了
            else break;
        }
    }
}

LC 3. 无重复字符的最长子串（中等）

题目描述：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

这道题考察了 双指针 ，定义两个指针 l 和 r ，判断 l ~ r 这一段区间内有无重复字符，记录最长字串长度即可

使用哈希表 cnt 对每个字符的出现次数计数

两个指针的 移动规则 如下：

l 指针 ：如果发现 l ~ r 区间内有重复字符，就将 l 指针右移，直到没有重复字符
r 指针 ：每次右移一个位置，将当前字符在 cnt 数组中计数

代码如下：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0, r = 0;
        int res = 0;
        int n = s.length();
        Map<Character, Integer> cnt = new HashMap<>();
        while (r < n) {
            char ch = s.charAt(r);
            // 如果发现 l-r 区间内有重复的字符
            while (cnt.containsKey(ch)) {
                // 删除左指针对应的字符
                cnt.remove(s.charAt(l));
                // 左指针右移
                l ++;
            }
            // 将当前字符加入 cnt 中记录
            cnt.put(ch, 1);
            // 记录最大区间长度
            res = Math.max(res, r - l + 1); 
            // 右移右指针
            r ++;
        }
        return res;
    }
}

LC 409. 最长回文串（简单）

题目描述：

给定一个包含大写字母和小写字母的字符串 s ，返回通过这些字母构造成的 最长的回文串 。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

这一道题的话，就是给一个字符串，你可以选择任意字符来构成回文串，看构造的最长回文串的长度

这道题也没有考某一个算法，主要是 回文串的特性 ：

回文串长度为偶数 ：只要有两个相同的字符，那么一个放左边，一个放右边，肯定是可以构成回文串的
回文串长度为奇数 ：这种情况的话，中间还可以放一个字符，不需要对应的字符，如 aba ，b 可以放在中间，构成奇数长度的回文串

解题思路 就是遍历字符串 s ，一个字符出现的次数为偶数，就一定可以组成回文串，直接将偶数次数的字符加到回文长度即可

再判断字符串 s 中是否有出现奇数次的字符，如果有的话，可以将奇数的字符放在中间，回文串的长度还可以加 1

代码如下：

class Solution {
    public int longestPalindrome(String s) {
        // 结果
        int res = 0;
        // 记录每个字符出现的次数，char 是 1 个字节，最多只有 128 个 char，因此这里数组长度声明为 128
        char[] ch = new char[128];
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            ch[c]++;
            if (ch[c] == 2){
                res += 2;
                ch[c] = 0;
            }
        }
        if(s.length() % ) res += 1;
        return res;
    }
}

LC 88. 合并两个有序数组（简单）

题目描述：

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

这道题目也是 双指针 ，同时遍历两个数组，取较小的值就好了，实现起来比较简单，就不细说了

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int sum = m + n;
        int[] res = new int[sum];
        int idx = 0;
        int i = 0, j = 0;
        // 遍历两个数组，当两个数组都没有遍历结束
        while(i < m && j < n){
            int a = nums1[i];
            int b = nums2[j];
            // 取较小值，放入到结果数组
            if (a < b){
                res[idx ++] = a;
                i ++;
            }else{
                res[idx ++] = b;
                j ++;
            }
        }
        // 两个数组长度可能不同，一个数组遍历完，另一个可能还没有，这里对没有遍历完的数组继续遍历
        while(i < m){
            res[idx ++] = nums1[i ++];
        }
        while(j < n){
            res[idx ++] = nums2[j ++];
        }
        nums1 = res;
        // 结果要求需要放在 nums1 数组中，这里赋值一下
        for (int cc = 0; cc < idx; cc ++) {
            nums1[cc] = res[cc];
        }
    }
}

LC 1143. 最长公共子序列（中等）

题目描述：

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

这道题目要求出两个字符串的 最长公共子序列 ，如果暴力做的话，需要枚举每一个字符串的子序列，再对子序列判断是否相同，这样时间复杂度直接爆表了，面试官肯定也不愿意看到这样的写法！

还是 动态规划 来做，先说动态规划数组含义：

f[i][j] ：表示第一字符串的前 i 个字符和第二个字符串的前 j 个字符的最长公共子序列

假设两个字符串为 s1 和 s2 ，那么 状态转移 为：

如果 $s 1 [i] == s 2 [j]$ ，那么 $f [i] [j] = f [i - 1] [j - 1] + 1$ ，也就是 f[i][j] 的状态由 f[i-1][j-1] 转移而来，并且 s1[i] == s2[j] ，因此这里长度再加一
如果 $s 1 [i]! = s 2 [j]$ ，那么分为两种情况：
- 忽略 s1[i] ，那么 f[i][j] 状态由 f[i-1][j] 转移过来
- 忽略 s2[j] ，那么 f[i][j] 状态由 f[i][j-1] 转移过来

代码如下 ：

class Solution {
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        // dp 题一般下标从 1 开始计算，这样 i-1 就不会小于 0 了
        int[][] f = new int[n+1][m+1];
        s1 = " " + s1;
        s2 = " " + s2;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                // 分为两种情况进行状态转移
                if (s1.charAt(i) == s2.charAt(j)) {
                    f[i][j] = f[i-1][j-1] + 1;
                } else {
                    f[i][j] = Math.max(f[i-1][j], f[i][j-1]);
                }
            }
        }
        return f[n][m];
    }
}