UB

跳跃游戏

Given an array, representing a jump game starting from the first position. You can jump right either 1 step or x steps, where x is a prime number with the last digit as 3. Each position has a value, determine the maximum sum of values on a path ending at the last position.

class Solution {

    public int maxValue(int[] nums) {
        int n = nums.length;
        List<Integer> primes = primesEndingWith3(n);
        Integer[] memo = new Integer[n];
        // 从 index 0 开始跳
        return dfs(nums, primes, 0, memo);
    }

    private int dfs(int[] nums, List<Integer> primes, int index, Integer[] memo) {
        int n = nums.length;

        if (index >= n) return Integer.MIN_VALUE / 4; // 超界
        if (index == n - 1) return nums[index];       // 到终点，返回当前值

        if (memo[index] != null) return memo[index];

        int best = Integer.MIN_VALUE / 4;

        // +1 step
        best = Math.max(best, nums[index] + dfs(nums, primes, index + 1, memo));

        // +p step (primes ending with 3)
        for (int p : primes) {
            int next = index + p;
            if (next >= n) break;
            best = Math.max(best, nums[index] + dfs(nums, primes, next, memo));
        }

        memo[index] = best;
        return best;
    }

    // 生成 <= n 且个位为 3 的质数
    private List<Integer> primesEndingWith3(int n) {
        boolean[] isPrime = new boolean[n + 1000]; // 多开一点防止超界
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i < isPrime.length; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < isPrime.length; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 3; i <= n; i++) {
            if (isPrime[i] && i % 10 == 3)
                res.add(i);
        }
        return res;
    }
}

无向图路径可以组成回文串数量

Given an undirected graph's edge list and some queries, for each query, count how many paths from the start node to the target node can form a palindrome. Each edge in the graph is marked with a character. Note that the path is considered a palindrome if the sequence of characters on the path forms a palindrome.

Input

• An integer n, the number of nodes 2 <= n <= 500.
• An integer m, the number of edges 1 <= m <= 1000.
• A list of m tuples (from_i, to_i, char_i), representing an edge from from_i to to_i marked with char_i.
• An integer q, the number of queries, 1 <= q <= 100.
• A list of q tuples (start_i, end_i), representing queries from start point start_i to end point end_i.

Output

• For each query, output how many paths can form a palindrome.

Example

Input:
n = 3, m = 3
edges = [(1, 2, 'a'), (2, 3, 'b'), (3, 1, 'a')]
queries = [(1, 3), (2, 1)]
Output:
[1, 1]

Note

• The edges are bidirectional; paths can pass through the same node multiple times.

public class PalindromicPaths {

    static class Edge {
        int to;
        char ch;
        Edge(int to, char ch) {
            this.to = to;
            this.ch = ch;
        }
    }

    public static List<Integer> countPalindromicPaths(int n, List<int[]> edges, List<int[]> queries) {
        // Build graph
        List<Edge>[] graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>();
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            char c = (char) e[2];
            graph[u].add(new Edge(v, c));
            graph[v].add(new Edge(u, c));
        }

        List<Integer> results = new ArrayList<>();
        for (int[] q : queries) {
            int start = q[0], end = q[1];
            Set<String> seen = new HashSet<>();
            Map<Character, Integer> freq = new HashMap<>();
            results.add(dfs(graph, start, end, seen, freq));
        }
        return results;
    }

    private static int dfs(List<Edge>[] graph, int current, int target, Set<String> seen, Map<Character, Integer> freq) {
        if (current == target) {
            return isPalindrome(freq) ? 1 : 0;
        }
        int count = 0;
        for (Edge e : graph[current]) {
            String key = current + "," + e.to + "," + e.ch;
            if (seen.contains(key)) continue;

            // visit edge
            freq.put(e.ch, freq.getOrDefault(e.ch, 0) + 1);
            seen.add(key);

            count += dfs(graph, e.to, target, seen, freq);

            // backtrack
            seen.remove(key);
            freq.put(e.ch, freq.get(e.ch) - 1);
            if (freq.get(e.ch) == 0) freq.remove(e.ch);
        }
        return count;
    }

    private static boolean isPalindrome(Map<Character, Integer> freq) {
        int odd = 0;
        for (int v : freq.values()) {
            if (v % 2 != 0) odd++;
        }
        return odd <= 1;
    }

    // Example usage
    public static void main(String[] args) {
        int n = 3;
        List<int[]> edges = Arrays.asList(
                new int[]{1, 2, 'a'},
                new int[]{2, 3, 'b'},
                new int[]{3, 1, 'a'}
        );
        List<int[]> queries = Arrays.asList(
                new int[]{1, 3},
                new int[]{2, 1}
        );
        List<Integer> res = countPalindromicPaths(n, edges, queries);
        System.out.println(res); // [1, 1]
    }
}

从i开始往下走的最大关数

Given two arrays 'layers' and 'energy', along with an initial energy value K. Assume you start exploring from the i-th level, where layers[i] indicates the energy consumed by this level. If the remaining energy after consumption is greater than or equal to energy[i], the level is considered completed and 1 point is scored. If a level fails, subsequent levels cannot be attempted. Return a list of size n, where each element indicates the score achievable starting from that level.

public class AdventureGame {
    public List<Integer> adventureScores(int[] layers, int[] energy, int K) {
        int n = layers.length;
        List<Integer> result = new ArrayList<>(Collections.nCopies(n, 0));
        int[] score = new int[n];

        int r = 0;
        int curEnergy = K;

        for (int l = 0; l < n; l++) {
            // 向右扩展窗口
            while (r < n && curEnergy - layers[r] >= energy[r]) {
                curEnergy -= layers[r];
                r++;
            }
            score[l] = r - l;  // 从 l 开始最多能拿的分数

            // 左移窗口，释放左端消耗的能量
            if (r > l) {
                curEnergy += layers[l];
            } else {  // 当前关闯不过，直接跳过
                r = l + 1;
                curEnergy = K;
            }
        }

        // 转换成 List<Integer>
        for (int i = 0; i < n; i++) {
            result.set(i, score[i]);
        }
        return result;
    }
}