浅浅记录一下周赛「2022-08-07」

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

对于这个题目，直接用vis[]记录访问情况，然后dfs即可

不过注意，这里有一个图的转化问题，需要把edges转换成graph，关于图的处理细节，详情可见图的遍历


private int ans = 0;
private boolean[] vis;
public int reachableNodes(int n, int[][] edges, int[] restricted) {
    // 转换成 graph
    List<Integer>[] graph = new ArrayList[n];
    for (int i = 0; i < n; i++) {
        graph[i] = new ArrayList<>();
    }
    // 无向树
    for (int[] e : edges) {
        graph[e[0]].add(e[1]);
        graph[e[1]].add(e[0]);
    }
    vis = new boolean[n];
    // 先把 restricted 中的点标记成 true
    for (int r : restricted) vis[r] = true;
    // 从 0 开始
    dfs(graph, 0);
    return ans;
}

private void dfs(List<Integer>[] graph, int s) {
    if (vis[s]) return ;
    vis[s] = true;
    ans++;
    // 遍历 s 的邻居节点
    for (int v : graph[s]) {
        dfs(graph, v);
    }
}

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

题目详情可见检查数组是否存在有效划分

对于这个题目，直接用「回溯」的思想，关于回溯的详细介绍可见回溯(DFS)

每次可以有三种选择：两个相等的元素、三个相等的元素、三个连续递增的元素

显然，如果纯暴力回溯，肯定会超时，所以这里用备忘录emeo[]记录子结果，emeo[i]表示[i..n-1]是否存在有效划分

这个问题的进阶版，可见经典回溯算法：集合划分问题


private int n;
private int[] emeo;
public boolean validPartition(int[] nums) {
    n = nums.length;
    emeo = new int[n];
    return backtrack(nums, 0);
}
private boolean backtrack(int[] nums, int index) {
    if (index == n) return true;
    if (emeo[index] != 0) return emeo[index] == 1;
    boolean sub = false;
    // 选择 1
    if (index + 1 < n && nums[index] == nums[index + 1]) {
        sub |= backtrack(nums, index + 2);
    }
    // 选择 2
    if (index + 2 < n && nums[index] == nums[index + 1] && nums[index] == nums[index + 2]) {
        sub |= backtrack(nums, index + 3);
    }
    // 选择 3
    if (index + 2 < n && nums[index] + 1 == nums[index + 1] && nums[index] + 2 == nums[index + 2]) {
        sub |= backtrack(nums, index + 3);
    }
    emeo[index] = sub ? 1 : -1;
    return sub;
}

最长理想子序列

题目详情可见最长理想子序列

对于这个题目，其实和「最长递增子序列」如出一辙！关于最长递增子序列的详细介绍可见动态规划设计：最长递增子序列

先给出第一版代码：


public int longestIdealString(String s, int k) {
    int[] dp = new int[s.length()];
    int res = 0;
    Arrays.fill(dp, 1);
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < i; j++) {
            // 绝对值相差不大于 k
            if (Math.abs(s.charAt(i) - s.charAt(j)) <= k) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

$1 \le s.length \le 10^5$

当k = 3，如果当前字母为g，那么它只能接在d e f g h i j为结尾的子序列后面

按照上面代码，我们把区间[0, i-1]全部遍历了，显然有很多无效分支

这里给出一种优化方法：用Map<Character, Integer>记录以某个字母结尾的最长子序列的长度

$10^5$ 简直少太多了

下面直接给出代码：


public int longestIdealString(String s, int k) {
    Map<Character, Integer> map = new HashMap<>();
    int[] dp = new int[s.length()];
    int res = 0;
    Arrays.fill(dp, 1);
    for (int i = 0; i < s.length(); i++) {
        char cur = s.charAt(i);
        // 第二层循环最多 26 次
        for (int j = 0; j <= k; j++) {
            // 比 cur 少 j 的字母
            char t1 = (char) (cur - j);
            // 比 cur 多 j 的字母
            char t2 = (char) (cur + j);
            if (map.containsKey(t1)) {
                dp[i] = Math.max(dp[i], map.get(t1) + 1);
            }
            if (map.containsKey(t2)) {
                dp[i] = Math.max(dp[i], map.get(t2) + 1);
            }
        }
        // 更新以 cur 结尾的最长子序列的长度
        map.put(cur, dp[i]);
        res = Math.max(res, dp[i]);
    }
    return res;
}

进一步优化！！

在上述优化的代码中，用到了一个dp[]来保存以下标为i结尾的最长递增序列的长度；同时还用到了一个Map来保存以某个字母结尾的最长子序列的长度，其实这两者可以合并成一个

让我们来重新定义一波dp[]，直接表示以某个字母结尾的最长子序列的长度。由于只有 26 个字母，所以dp的长度为 26 就行！！

下面直接给出代码：


xxxxxxxxxx
public int longestIdealString(String s, int k) {
    // Map<Character, Integer> map = new HashMap<>();
    int[] dp = new int[26];
    int res = 0;
    // Arrays.fill(dp, 1);
    for (int i = 0; i < s.length(); i++) {
        // 把字母转换成对应的数字，从 0 开始
        int cur = s.charAt(i) - 'a';
        for (int j = 0; j <= k; j++) {
            int t1 = cur - j;
            int t2 = cur + j;
            // 在 [0, 26) 范围内
            if (t1 >= 0 && t1 < 26) dp[cur] = Math.max(dp[cur], dp[t1]);
            if (t2 >= 0 && t2 < 26) dp[cur] = Math.max(dp[cur], dp[t2]);
        }
        // 切记不能直接在 Math.max(dp[cur], dp[t1] + 1) 中更新
        dp[cur]++;
        res = Math.max(res, dp[cur]);
    }
    return res;
}