咱们好，我是梁唐。

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

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

这次的竞赛因为标题比较简略，又引来了广泛吐槽，给咱们截取一个比较有意思的。

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

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

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

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

算术三元组的数目

给你一个下标从 0 开端、严厉递加 的整数数组 nums 和一个正整数 diff 。假如满意下述全部条件，则三元组 (i, j, k) 便是一个 算术三元组 ：

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

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

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

题解

首先读题要仔细，有几个重要的细节。第一个是数组严厉递加，这可以确保不会呈现重复的元素。其次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 不 会标记为受限节点。

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

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

题解

水题，运用邻接表重新存储树再运用查找遍历即可。

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 。

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

题解

同样需求仔细读题，标题傍边清晰说了需求数组接连，这是一个很强的信号，也便是说咱们不能改变数组傍边的元素次序。

咱们假定有数组a0,a1,⋯ ,ana_0,a_1, \cdots, a_n满意要求，咱们考虑ana_n的状况。无非三种状况：

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

不论哪一种状况成立，剩余的问题实质是一样的，仅仅规划变得更小。比如假如第一种状况成立，那么咱们只需求考虑剩余的a0,⋯ ,an−2a_0, \cdots, a_{n-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 。

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

题解

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

对于最长不下降子序列问题而言，咱们运用数组dp[i]记载以i为结束的最长不下降子序列的长度。在状况搬运的时分，咱们遍历i之前的一切方位，找到满意搬运条件的最优方位v，那么dp[i] = dp[v]+1。但显然这种算法的复杂度是O(n2)O(n^2)，在本题的数据规模下肯定会超时。

但怎样优化呢？

咱们仍是要从题意傍边找突破口，有一个突破口是在本题傍边一切方位的规模都是英文字母，取值规模十分小，最大只有26。那么其实可以稍稍改变思路，咱们可以用dp[i][v]记载长度为i，以字母v为结束的契合题意的最长子序列的长度。那么：

dp[i][v]=max(dp[i−1][u])+1(v−k≤u≤v+k)dp[i][v] = max(dp[i-1][u]) + 1 \quad (v – k \le u \le v + k)

因为咱们是依照次序遍历的，所以其实第一个维度没有效果。所以咱们可以省掉，用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;
    }
};

这次的标题整体来说难度偏简略，主要是一些根底算法以及相关的转化。对于新手来说，这样的标题其实做出来不是最重要的，更重要的是练习对于思路推导以及分析的敏感度，可以从标题描述以及推导得出的相关定论傍边找到蛛丝马迹从而最终完成解答。

俗话说好记忆不如烂笔头，看懂多少遍始终都不如亲自测验测验。测验多了，天然就有收成了，加油。