跳跃游戏
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 nodes2 <= n <= 500. - An integer
m, the number of edges1 <= m <= 1000. - A list of
mtuples(from_i, to_i, char_i), representing an edge fromfrom_itoto_imarked withchar_i. - An integer
q, the number of queries,1 <= q <= 100. - A list of
qtuples(start_i, end_i), representing queries from start pointstart_ito end pointend_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;
}
}