Complete the function below. The function receives the full standard input as a single string and returns the exact standard output lines.
Decode strings that contain repeated parenthesized groups. Plain characters are copied directly. A group has the form (substring){k}, meaning the decoded substring inside the parentheses is repeated k times. Groups may be nested.
For each encoded string, output its decoded form.
Function Description
Complete solveDecodeRepeatedGroups. It has one parameter, String input. The first line is q, followed by q encoded strings. Return one decoded string per query.
Constraints
Repeat counts are non-negative integers written inside braces after a closing parenthesis. Parentheses and braces are balanced in valid inputs.
Example 1
Input:
input = "3\nabs(cs){3}g\na(b(c){2}){2}\nx(yz){0}q"Output:
["abscscscsg","abccbcc","xq"]Explanation:
The second case decodes the nested group b(c){2} as bcc, then repeats it twice.
解法
栈式解析：维护栈帧(每帧是 StringBuilder)。遇 ( push 新帧；遇 ) 看接下来的 {k}，把顶帧重复 k 次合并到下层；其它字符追加到当前顶帧。最终 join。每行处理时间 O(总输出长度)。
from typing import List
def _decode(s: str) -> str:
stack: List[List[str]] = [[]]
i = 0
while i < len(s):
c = s[i]
if c == '(':
stack.append([])
i += 1
elif c == ')':
# parse {k}
assert s[i + 1] == '{'
j = i + 2
k = 0
while s[j] != '}':
k = k * 10 + int(s[j])
j += 1
top = stack.pop()
stack[-1].append(''.join(top) * k)
i = j + 1
else:
stack[-1].append(c)
i += 1
return ''.join(stack[0])
def solve_decode_repeated_groups(input: str) -> List[str]:
lines = input.split('\n')
q = int(lines[0])
return [_decode(lines[i + 1]) for i in range(q)]import java.util.*;
class Solution {
public String[] solveDecodeRepeatedGroups(String input) {
String[] lines = input.split("\n");
int q = Integer.parseInt(lines[0].trim());
String[] out = new String[q];
for (int i = 0; i < q; i++) out[i] = decode(lines[i + 1]);
return out;
}
private String decode(String s) {
Deque<StringBuilder> stack = new ArrayDeque<>();
stack.push(new StringBuilder());
int i = 0;
while (i < s.length()) {
char c = s.charAt(i);
if (c == '(') { stack.push(new StringBuilder()); i++; }
else if (c == ')') {
int j = i + 2; int k = 0;
while (s.charAt(j) != '}') { k = k * 10 + (s.charAt(j) - '0'); j++; }
StringBuilder top = stack.pop();
StringBuilder rep = new StringBuilder();
for (int t = 0; t < k; t++) rep.append(top);
stack.peek().append(rep);
i = j + 1;
} else { stack.peek().append(c); i++; }
}
return stack.peek().toString();
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
string decode(const string& s) {
vector<string> stack(1);
int i = 0;
while (i < (int)s.size()) {
char c = s[i];
if (c == '(') { stack.emplace_back(); i++; }
else if (c == ')') {
int j = i + 2, k = 0;
while (s[j] != '}') { k = k * 10 + (s[j] - '0'); j++; }
string top = stack.back(); stack.pop_back();
string rep; rep.reserve(top.size() * k);
for (int t = 0; t < k; t++) rep += top;
stack.back() += rep;
i = j + 1;
} else { stack.back() += c; i++; }
}
return stack[0];
}
public:
vector<string> solveDecodeRepeatedGroups(string input) {
vector<string> lines;
stringstream ss(input); string ln;
while (getline(ss, ln, '\n')) lines.push_back(ln);
int q = stoi(lines[0]);
vector<string> out;
for (int i = 0; i < q; i++) out.push_back(decode(lines[i + 1]));
return out;
}
};You are given a directed weighted graph with n nodes labeled 1 through n. Each edge is represented as [u, v, w], meaning there is an edge from u to v with non-negative weight w.
Also given are a source node source and a list of target nodes targets. Compute the shortest distance from source to each target in order. If a target is unreachable, return -1 for that target.
Function Description
Complete the function shortestPathsToTargets in the editor below.
shortestPathsToTargets has the following parameters:
int n: the number of nodesint[][] edges: directed edges[u, v, w]int source: the source nodeint[] targets: the targets to query Returnslong[]: shortest distances to the targets in the same order.
Constraints
1 ≤ n ≤ 2 * 10⁵0 ≤ edges.length ≤ 3 * 10⁵0 ≤ w ≤ 10⁹- Multiple edges and self-loops are allowed.
Example 1
Input:
n = 5
edges = [[1, 2, 2], [1, 3, 5], [2, 3, 1], [2, 4, 2], [3, 5, 1], [4, 5, 2]]
source = 1
targets = [3, 4, 5]Output:
[3, 4, 4]Explanation:
Running Dijkstra from node 1 gives distances 3, 4, and 4 to targets 3, 4, and 5.
Example 2
Input:
n = 4
edges = [[1, 2, 5]]
source = 1
targets = [2, 3]Output:
[5, -1]Explanation:
Node 2 is reachable with cost 5, while node 3 is unreachable.
解法
从 source 跑 Dijkstra，得到 dist[1..n]，对每个 target 取 dist[t](unreachable 用 −1)。时间 O((V+E) log V)。
import heapq
from typing import List
def shortest_paths_to_targets(n: int, edges: List[List[int]], source: int, targets: List[int]) -> List[int]:
graph = [[] for _ in range(n + 1)]
for u, v, w in edges:
graph[u].append((v, w))
INF = float('inf')
dist = [INF] * (n + 1)
dist[source] = 0
pq = [(0, source)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return [-1 if dist[t] == INF else dist[t] for t in targets]import java.util.*;
class Solution {
public long[] shortestPathsToTargets(int n, int[][] edges, int source, int[] targets) {
List<long[]>[] g = new List[n + 1];
for (int i = 0; i <= n; i++) g[i] = new ArrayList<>();
for (int[] e : edges) g[e[0]].add(new long[]{e[1], e[2]});
long[] dist = new long[n + 1];
Arrays.fill(dist, Long.MAX_VALUE);
dist[source] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.add(new long[]{0, source});
while (!pq.isEmpty()) {
long[] cur = pq.poll();
long d = cur[0]; int u = (int) cur[1];
if (d > dist[u]) continue;
for (long[] e : g[u]) {
long nd = d + e[1];
if (nd < dist[(int) e[0]]) { dist[(int) e[0]] = nd; pq.add(new long[]{nd, (int) e[0]}); }
}
}
long[] out = new long[targets.length];
for (int i = 0; i < targets.length; i++) out[i] = dist[targets[i]] == Long.MAX_VALUE ? -1 : dist[targets[i]];
return out;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<long long> shortestPathsToTargets(int n, vector<vector<int>>& edges, int source, vector<int>& targets) {
vector<vector<pair<int, long long>>> g(n + 1);
for (auto& e : edges) g[e[0]].push_back({e[1], e[2]});
vector<long long> dist(n + 1, LLONG_MAX);
dist[source] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto& [v, w] : g[u]) {
long long nd = d + w;
if (nd < dist[v]) { dist[v] = nd; pq.push({nd, v}); }
}
}
vector<long long> out;
for (int t : targets) out.push_back(dist[t] == LLONG_MAX ? -1 : dist[t]);
return out;
}
};