LeetCode周赛305，两千人通过第四题，手速场太可怕……

大家好，我是梁唐。

我们照例来聊聊昨天的LeetCode周赛。这次是第305场周赛，这场的赞助商是中国银联。前500名都能获得简历内推的机会。

这次的比赛由于题目比较简单，又引来了广泛吐槽，给大家截取一个比较有意思的。

群里的小伙伴对此也给与了吐槽：

好了，废话不多说，我们来看题吧。

算术三元组的数目

给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件，则三元组 (i, j, k) 就是一个 算术三元组 ：

• i < j < k ，
• nums[j] - nums[i] == diff 且
• nums[k] - nums[j] == diff

返回不同 算术三元组 的数目*。*

题解

首先读题要仔细，有几个重要的细节。第一个是数组严格递增，这可以保证不会出现重复的元素。其次diff是确定的，所以我们确定了最小或者最大的元素就可以确定出所有的三个值。

我们可以把所有元素放入set当中，然后遍历三元组中的最小值。假设这个值是x，我们只需要判断x+diff和x+2*diff是否在set当中就可以知道三元组是否存在。最后统计满足的答案个数即可。

class Solution {
public:
    int arithmeticTriplets(vector<int>& nums, int diff) {
        set<int> st;
        for (auto &x : nums) st.insert(x);
        int ret = 0;
        for (auto &x : nums) {
            if (st.count(x + diff) && st.count(x + 2 * diff)) {
                ret++;
            }
        }
        return ret;
    }
};

受限条件下可到达节点的数目

现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。

给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restricted 表示 受限 节点。

在不访问受限节点的前提下，返回你可以从节点 0 到达的 最多 节点数目*。*

注意，节点 0 不 会标记为受限节点。

题解

水题，使用邻接表重新存储树再使用搜索遍历即可。

dfs或bfs都可，dfs实现相对比较简单，因此选择dfs。

class Solution {
public:
    int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& rest) {
        set<int> visited, limited(rest.begin(), rest.end());
        
        vector<vector<int>> graph(n, vector<int>());
    
        for (auto &vt: edges) {
            int u = vt[0], v = vt[1];
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        
        function<void(int, int)> dfs = [&](int u, int f) {
          	// f是父亲节点
            for (auto &v: graph[u]) {
              	// 往下遍历的节点v，不能等于父节点
                if (v != f && !limited.count(v)) {
                    visited.insert(v);
                    dfs(v, u);
                }
            }
        };
        
        dfs(0, -1);
        return visited.size() + 1;
    }
};

检查数组是否存在有效划分

给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。

如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：

1. 子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
2. 子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
3. 子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。

如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。

题解

同样需要仔细读题，题目当中明确说了需要数组连续，这是一个很强的信号，也就是说我们不能改变数组当中的元素顺序。

我们假设有数组a0,a1,⋯ ,ana_0,a_1, \cdots, a_na0​,a1​,⋯,an​满足要求，我们考虑ana_nan​的情况。无非三种情况：

• an=an−1a_n = a_{n-1}an​=an−1​
• an=an−1,an−1=an−2a_n = a_{n-1}, a_{n-1} = a_{n-2}an​=an−1​,an−1​=an−2​
• an−2=an−1−1,an−2=an−2a_{n-2} = a_{n-1} - 1, a_{n-2} = a_n - 2an−2​=an−1​−1,an−2​=an​−2

不论哪一种情况成立，剩下的问题本质是一样的，只是规模变得更小。比如如果第一种情况成立，那么我们只需要考虑剩余的a0,⋯ ,an−2a_0, \cdots, a_{n-2}a0​,⋯,an−2​。这是一个规模更小的同样的问题。

如果大家对于算法比较敏感的话，可能已经有所感觉了，这符合动态规划的最优子结构问题。我们在日常做算法题的时候对于能够解决问题的解法是怎么想到的呢？其实就是从类似上述的推导和分析当中通过蛛丝马迹联想到的，而非生搬硬套来的。这种通过推导寻找正确解法既是一种能力，也需要一点经验，我们日常做算法训练其实就是为了这个。

确定了动态规划之后，剩下的就很简单了。我们用dp[i]记录以i结尾的子数组是否满足要求。当a[i] = a[i-1]时，dp[i] = dp[i-2]。同理当a[i] = a[i-1] = a[i-2]时，dp[i] = dp[i-3]。在推导的时候再考虑一下边界情况即可。

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        vector<bool> dp(n+1, 0);
        
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            int v = nums[i-1];
            if (i > 1 && nums[i-2] == v) {
                dp[i] = dp[i] | dp[i-2];
            }
            if (i > 2 && nums[i-3] == v && nums[i-2] == v) {
                dp[i] = dp[i] | dp[i-3];
            }
            if (i > 2 && nums[i-3] == v-2 && nums[i-2] == v-1) {
                dp[i] = dp[i] | dp[i-3];
            }
        }
        
        return dp[n];
    }
};

最长理想子序列

给你一个由小写字母组成的字符串 s ，和一个整数 k 。如果满足下述条件，则可以将字符串 t 视作是 理想字符串 ：

• t 是字符串 s 的一个子序列。
• t 中每两个 相邻 字母在字母表中位次的绝对差值小于或等于 k 。

返回 最长 理想字符串的长度。

字符串的子序列同样是一个字符串，并且子序列还满足：可以经由其他字符串删除某些字符（也可以不删除）但不改变剩余字符的顺序得到。

**注意：**字母表顺序不会循环。例如，'a' 和 'z' 在字母表中位次的绝对差值是 25 ，而不是 1 。

题解

表面上看这是最长不下降子序列问题的变种，我们用相同的算法也能得到答案。

对于最长不下降子序列问题而言，我们使用数组dp[i]记录以i为结尾的最长不下降子序列的长度。在状态转移的时候，我们遍历i之前的所有位置，找到满足转移条件的最优位置v，那么dp[i] = dp[v]+1。但显然这种算法的复杂度是O(n2)O(n^2)O(n2)，在本题的数据范围下肯定会超时。

但怎么优化呢？

我们还是要从题意当中找突破口，有一个突破口是在本题当中所有位置的范围都是英文字母，取值范围非常小，最大只有26。那么其实可以稍稍转变思路，我们可以用dp[i][v]记录长度为i，以字母v为结尾的符合题意的最长子序列的长度。那么：

由于我们是按照顺序遍历的，所以其实第一个维度没有作用。所以我们可以省略，用dp[i]记录遍历时以字母i结尾的理想子序列长度即可。

更多细节参考代码：

class Solution {
public:
    int longestIdealString(string s, int k) {
        int n = s.length();
        int dp[27];
        memset(dp, 0, sizeof dp);
        
        int ret = 1;
        for (int i = 0; i < n; i++) {
            int u = s[i] - 'a';
          	// 遍历 [-k, k] 符合理想子序列的范围内的最大长度
            for (int j = 0; j <= k; j++) {
                if (u >= j) dp[u] = max(dp[u], dp[u-j]);
                if (u + j <= 26) dp[u] = max(dp[u], dp[u+j]);
            }
            dp[u]++;
            ret = max(ret, dp[u]);
        }
        
        return ret;
    }
};

这次的题目总体来说难度偏简单，主要是一些基础算法以及相关的转化。对于新手来说，这样的题目其实做出来不是最重要的，更重要的是练习对于思路推导以及分析的敏感度，能够从题目描述以及推导得出的相关结论当中找到蛛丝马迹从而最终完成解答。

俗话说好记性不如烂笔头，看懂多少遍始终都不如亲自尝试尝试。尝试多了，自然就有收获了，加油。