力扣第305场周赛复盘

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int arithmeticTriplets(int[] nums, int diff) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) map.put(nums[i], i);
        int ans = 0;
        for (int i = 1; i + 1 < n; i++) {
            int prev = map.getOrDefault(nums[i] - diff, n);
            int next = map.getOrDefault(nums[i] + diff, -1);
            if (prev < i && next > i) ans++;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    int ans = 0;

    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++)
            graph[i] = new ArrayList<>();
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        HashSet<Integer> res = new HashSet<>();
        for (int x : restricted) res.add(x);
        boolean[] vis = new boolean[n];
        dfs(graph, 0, res, vis);
        return ans;
    }

    void dfs(List<Integer>[] graph, int u, HashSet<Integer> res, boolean[] vis) {
        vis[u] = true;
        ans++;
        for (int v : graph[u]) {
            if (!res.contains(v) && !vis[v])
                dfs(graph, v, res, vis);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        // dp[i] 表示前 i 个元素是否存在有效划分
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        dp[2] = nums[0] == nums[1];
        for (int i = 2; i < n; i++) {
            dp[i + 1] = dp[i - 1] && nums[i] == nums[i - 1] ||
                        dp[i - 2] && nums[i] == nums[i - 1] && nums[i] == nums[i - 2] ||
                        dp[i - 2] && nums[i] - 1 == nums[i - 1] && nums[i] - 2 == nums[i - 2];
        }
        return dp[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int longestIdealString(String s, int k) {
        int[] dp = new int[26];
        for (char c : s.toCharArray()) {
            int x = c - 'a';
            int maxLen = 0;
            for (int i = Math.max(0, x - k); i <= Math.min(25, x + k); i++)
                maxLen = Math.max(maxLen, dp[i]);
            d[x] = maxLen + 1;
        }
        int ans = 0;
        for (int x : dp) ans = Math.max(ans, x);
        return ans;
    }
}