You are given vehicle event logs in chronological order. Each log contains a license plate and one of three event types: entry, road, or exit.
A completed trip is counted when the same plate appears in order as entry -> road -> exit.
Count the total number of completed trips across all plates.
Function Description
Complete the function countCompletedTrips in the editor below.
countCompletedTrips has the following parameter:
String[] logs: log lines formatted as"plate event"Returnsint: the number of completed trips.
Constraints
- Logs are processed in chronological order.
- The same plate may complete multiple trips.
- Incomplete or invalid event sequences should not be counted.
Example 1
Input:
logs = ["A entry", "A road", "A exit"]Output:
1Explanation:
Plate A completes one valid entry -> road -> exit sequence.
Example 2
Input:
logs = ["A entry", "B entry", "A road", "A exit", "B exit"]Output:
1Explanation:
Plate A completes one trip. Plate B does not, because it never reaches the road event before exiting.
解法
每个 plate 维护一个状态机：None -> entry -> road -> exit。遇到事件按当前状态推进；到 exit 时若来自 road 计数 + 1 并重置。其他不合法序列(如 entry 后直接 exit)将其状态停留或重置但不计数。复杂度 O(n)。
from typing import List
def count_completed_trips(logs: List[str]) -> int:
state = {}
count = 0
for log in logs:
plate, event = log.split()
s = state.get(plate, "init")
if event == "entry":
state[plate] = "entry"
elif event == "road":
state[plate] = "road" if s == "entry" else "init"
elif event == "exit":
if s == "road":
count += 1
state[plate] = "init"
return countimport java.util.*;
class Solution {
int countCompletedTrips(String[] logs) {
Map<String, String> state = new HashMap<>();
int count = 0;
for (String log : logs) {
String[] p = log.split(" ");
String plate = p[0], ev = p[1];
String s = state.getOrDefault(plate, "init");
if (ev.equals("entry")) state.put(plate, "entry");
else if (ev.equals("road")) state.put(plate, s.equals("entry") ? "road" : "init");
else if (ev.equals("exit")) {
if (s.equals("road")) count++;
state.put(plate, "init");
}
}
return count;
}
}class Solution {
public:
int countCompletedTrips(vector<string>& logs) {
unordered_map<string, string> state;
int count = 0;
for (auto& log : logs) {
auto sp = log.find(' ');
string plate = log.substr(0, sp), ev = log.substr(sp + 1);
string& s = state[plate];
if (s.empty()) s = "init";
if (ev == "entry") s = "entry";
else if (ev == "road") s = (s == "entry") ? "road" : "init";
else if (ev == "exit") { if (s == "road") count++; s = "init"; }
}
return count;
}
};A hiker is planning a multi-day trek through the mountains. There are trails, each with a certain length, given as a list, trails, that need to be hiked in the order in the list. The hiker wants to achieve a new world record by completing the trek in record number of days. Each day, the hiker will cover at least one trail and must minimize the sum of the lengths of the longest trail hiked each day. Find this minimum sum.
Example:
There are n = 6 trails with lengths trails= [10, 5, 9, 3, 8, 15] and record = 2.
One optimal solution is for the hiker to cover the first trail on the first day, and the remaining trails on the second day. On the first day, the longest trail is 10, and on the second day, it is max(5, 9, 3, 8, 15) = 15. The sum of the lengths of the longest trails is 10 + 15 = 25. Return 25.
Function Description
Complete the function efficientTrek in the editor.
efficientTrek has the following parameters:
int trails[]: an array of integers denoting the order and length of the trails.int record: the number of days to cover all the trails. Returnsint: the minimum sum of the longest trails on each day
Constraints
1 ≤ n ≤ 3001 ≤ record ≤ n ≤ 3001 ≤ trails[i] ≤ 10⁵
解法
DP：dp[i][k] = 把 trails[0..i-1] 切成 k 段时每段最长元素和的最小值。转移 dp[i][k] = min_{j<i} dp[j][k-1] + max(trails[j..i-1])。复杂度 O(n² · record)，n ≤ 300 可接受。
from typing import List
def efficient_trek(trails: List[int], record: int) -> int:
n = len(trails)
INF = float("inf")
dp = [[INF] * (record + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
for k in range(1, record + 1):
cur_max = 0
for j in range(i - 1, -1, -1):
if trails[j] > cur_max:
cur_max = trails[j]
if dp[j][k - 1] + cur_max < dp[i][k]:
dp[i][k] = dp[j][k - 1] + cur_max
return dp[n][record]class Solution {
int efficientTrek(int[] trails, int record) {
int n = trails.length;
long INF = Long.MAX_VALUE / 4;
long[][] dp = new long[n + 1][record + 1];
for (long[] row : dp) Arrays.fill(row, INF);
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= record; k++) {
int curMax = 0;
for (int j = i - 1; j >= 0; j--) {
curMax = Math.max(curMax, trails[j]);
if (dp[j][k - 1] + curMax < dp[i][k]) dp[i][k] = dp[j][k - 1] + curMax;
}
}
}
return (int) dp[n][record];
}
}class Solution {
public:
int efficientTrek(vector<int>& trails, int record) {
int n = trails.size();
const long long INF = 1e18;
vector<vector<long long>> dp(n + 1, vector<long long>(record + 1, INF));
dp[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int k = 1; k <= record; k++) {
int curMax = 0;
for (int j = i - 1; j >= 0; j--) {
curMax = max(curMax, trails[j]);
if (dp[j][k - 1] + curMax < dp[i][k]) dp[i][k] = dp[j][k - 1] + curMax;
}
}
return (int) dp[n][record];
}
};A perfect pair (x, y) is such
Example 1
Input:
nums = [2, -3, 5]Output:
2Explanation: (2, -3) and (-3, 5) are perfect pairs
解法
"perfect pair" 通常指 |x - y| ≤ min(|x|, |y|) && |x + y| ≤ max(|x|, |y|)(LinkedIn 经典)。等价于 max(|x|, |y|) ≤ 2 * min(|x|, |y|) 排序后双指针。复杂度 O(n log n)。
from typing import List
def find_number_of_perfect_pairs(nums: List[int]) -> int:
arr = sorted(abs(x) for x in nums)
n = len(arr)
count = 0
j = 0
for i in range(n):
if j < i + 1: j = i + 1
while j < n and arr[j] <= 2 * arr[i]:
j += 1
count += j - i - 1
return countimport java.util.*;
class Solution {
long findNumberOfPerfectPairs(int[] nums) {
int n = nums.length;
long[] arr = new long[n];
for (int i = 0; i < n; i++) arr[i] = Math.abs((long) nums[i]);
Arrays.sort(arr);
long count = 0;
int j = 0;
for (int i = 0; i < n; i++) {
if (j < i + 1) j = i + 1;
while (j < n && arr[j] <= 2 * arr[i]) j++;
count += j - i - 1;
}
return count;
}
}class Solution {
public:
long long findNumberOfPerfectPairs(vector<int>& nums) {
int n = nums.size();
vector<long long> arr(n);
for (int i = 0; i < n; i++) arr[i] = abs((long long) nums[i]);
sort(arr.begin(), arr.end());
long long count = 0;
int j = 0;
for (int i = 0; i < n; i++) {
if (j < i + 1) j = i + 1;
while (j < n && arr[j] <= 2 * arr[i]) j++;
count += j - i - 1;
}
return count;
}
};