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.
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理