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" Returns int: 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:

1

Explanation: Plate A completes one valid entry -> road -> exit sequence.

Example 2

Input:

logs = ["A entry", "B entry", "A road", "A exit", "B exit"]

Output:

1

Explanation: 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 count

import 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 perfect pair (x, y) is such

Example 1

Input:

nums = [2, -3, 5]

Output:

2

Explanation: (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 count

import 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;
    }
};

Given a graph of N nodes named with 1<

Example 1

Input:

N = 4
edges = [[1, 2, 4], [1, 3, 2], [2, 4, 5], [2, 3, 6]]
K = 3

Output:

5

Explanation: Note: I'm more than happy to make modifications if anything in the input seems incorrect. You can reach me in our Discord group! Possible routes from 1 to 4 is [1->2->3, 1->3->2->4] As the maximum in path 1 -> 2 -> 4 is 5 on the edge 2->4, while in 1->3->2->4 is 6 at edge 3->2.

解法

求从 1 到 K 的路径中"路径上最大边权"的最小值(最小化最大边)。修改版 Dijkstra：状态值 = 已遍历最大边权，松弛时取 max(cur, edge_weight)，用最小堆按状态值排序。复杂度 O((V+E) log V)。

from typing import List
import heapq

def find_the_path(N: int, edges: List[List[int]], K: int) -> int:
    adj = [[] for _ in range(N + 1)]
    for u, v, w in edges:
        adj[u].append((v, w)); adj[v].append((u, w))
    INF = float("inf")
    best = [INF] * (N + 1)
    best[1] = 0
    pq = [(0, 1)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > best[u]: continue
        if u == K: return d
        for v, w in adj[u]:
            nd = max(d, w)
            if nd < best[v]:
                best[v] = nd
                heapq.heappush(pq, (nd, v))
    return -1

import java.util.*;

class Solution {
    int findThePath(int N, int[][] edges, int K) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= N; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            adj.get(e[1]).add(new int[]{e[0], e[2]});
        }
        int[] best = new int[N + 1];
        Arrays.fill(best, Integer.MAX_VALUE);
        best[1] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{0, 1});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], u = cur[1];
            if (d > best[u]) continue;
            if (u == K) return d;
            for (int[] e : adj.get(u)) {
                int nd = Math.max(d, e[1]);
                if (nd < best[e[0]]) { best[e[0]] = nd; pq.add(new int[]{nd, e[0]}); }
            }
        }
        return -1;
    }
}

class Solution {
public:
    int findThePath(int N, vector<vector<int>>& edges, int K) {
        vector<vector<pair<int, int>>> adj(N + 1);
        for (auto& e : edges) {
            adj[e[0]].push_back({e[1], e[2]});
            adj[e[1]].push_back({e[0], e[2]});
        }
        vector<int> best(N + 1, INT_MAX);
        best[1] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({0, 1});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > best[u]) continue;
            if (u == K) return d;
            for (auto& [v, w] : adj[u]) {
                int nd = max(d, w);
                if (nd < best[v]) { best[v] = nd; pq.push({nd, v}); }
            }
        }
        return -1;
    }
};

Given s and x, determine the zero-based index of the first occurrence of x in s. String s consists of lowercase letters in the range ascii[a-z]. String x consists of lowercase letters and may also contain a single wildcard character, *, that represents any one character. Function Description Complete the function firstOccurrence in the editor below. The function must return an integer denoting the zero-based index of the first occurrence of string x in s. If x is not in s, return -1 instead. firstOccurrence has the following parameter(s):

• string s: a string of lowercase letters
• string x: a string of lowercase letters which may contain 1 instance of the wildcard character *

There is a dual core processor with one process queue for each core. There are n processes, where the time to process the ith process is denoted by time[i] (1 ≤ i ≤ n). There is a latch that helps decide which process is processed by which core. Initially, the first core has the latch. Suppose the latch is currently with the cth core, where c is either 1 or 2, and the ith process needs to be assigned. Then one of the following operations must be performed: The i+1th process assigned to the core c and the latch is given to the other core. The i+1th process is assigned to the other core, and the latch is retained by the core c. The aim of each core is to have a maximum sum of time of processes with them for better performance. So, while assigning the ith process, the core with the latch decides the operation to be performed such that the total sum of time of processes assigned to it is maximized after all the processes are assigned. Find the sum of the time of processes assigned to the first and second cores if both the cores work optimally. Return an array of two integers, where the first integer is the sum of the time of processes assigned to the first core, and the second integer is the aim of the time of processes assigned to the second core. Function Description Complete the function getProcessTime in the editor below. getProcessTime has the following parameter:

• int time[n]: the processing time required for each process Returns long[2]: the sums of processing times of the first and second cores

Constraints

• 1

Example 1

Input:

time = [10, 21, 10, 21, 10]

Output:

[41, 31]

Explanation: Let's have an example, initially, the first core has the latch and the total time of processes for the first core is (10 + 21) = 31, and the total time of processes for the second core is (10 + 10 + 20). The given assignment is not optimal, the optimal time for the processes for the first core is (21+10+21)=52, and the total time of processes for the second core is (10 + 10) = 20. The given assignment is not optimal total as for the 4th process, the 2nd core assigned the process with process time = 21 to core 1 and got the 5th process with process time = 10, which is not an optimal move by core 2. The optimal move by the 2nd core would have been to assign the 4th process to itself and the 5th process to core, this would have given the total process time to the 2nd core = 31, which is better than 20. An optimal assignment is shown. Hence, the total time of processes for the first core is (10 + 21 + 10) = 41, and the total time of processes for the second core is (10 + 21) = 31. Return the answer array, [41, 31].

LC 1048 :) The other question is shown in the img below:

You are given an array of words where each word consists of lowercase English letters. word₁ is a predecessor of word₂ if and only if we can insert exactly one letter anywhere in word₁ without changing the order of the other characters to make it equal to word₂. For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcaa". A word chain is a sequence of words [word₁, word₂, ..., wordₖ] with k ≥ 1, where word₁ is a predecessor of word₂, word₂ is a predecessor of word₃, and so on. A single word is trivially a word chain with k = 1. Return the length of the longest possible word chain with words chosen from the given list of words.

Constraints

• 1 ≤ words.length ≤ 1000
• 1 ≤ words[i].length ≤ 16
• words[i] only consists of lowercase English letters.

Example 1

Input:

words = ["a","b","ba","bca","bda","bdca"]

Output:

4

Explanation: One of the longest word chains is ["a","ba","bda","bdca"].

Example 2

Input:

words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]

Output:

5

Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Example 3

Input:

words = ["abcd","dbqca"]

Output:

1

Explanation: The trivial word chain ["abcd"] is one of the longest word chains. ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

A team must optimize context switching between processes. There are n segments where a thread is assigned to each segment. The maximum stack size of a thread assigned in the ith segment is denoted by threadSize[i], for all 1 ≤ i ≤ n. For any high-priority process, some stack size of the segments must be increased. A segment is said to be special when threadSize[i - 1] threadSize[i + 1]. The segments at each end cannot be special. The stack sizes must be modified in such a way as to maximize the number of special segments. To do so, choose any segment and increase the stack size by x. More formally,

• Choose an index i and an integer x, where 0 ≤ x ≤ 10¹⁸.
• Increase the stack size of the ith segment from threadSize[i] to threadSize[i] + x. Find the minimum total increase in the stack size of the segments.

Given an array of integers arr and an integer K. While maintaining the order, split into exactly K pieces such the sum of maximum of every sub-array is minimum. For example, given arr = [1, 5, 3, 4, 2] and K = 2, the output should be 6. Possible splits are: [[1], [5, 3, 4, 2]], [[1, 5], [3, 4, 2]], [[1, 5, 3], [4, 2]], [[1, 5, 3, 4], [2]]. The minimum sum of maximum would be [1], [5, 3, 4, 2] = 1 + 5 = 6. Function Description Complete the function splitArrayLargestSum in the editor. splitArrayLargestSum has the following parameters:

• 1. int[] arr: an array of integers
• 2. int K: the number of pieces to split the array into Returns int: the minimum sum of the maximums of K sub-arrays

Constraints

• 1 < K ≤ N < 300
• 1 < arr[i] < 10⁵

Example 1

Input:

arr = [1, 5, 3, 4, 2]
K = 2

Output:

6

Explanation: Possible splits are: [[1], [5, 3, 4, 2]], [1, 5], [3, 4, 2], [1, 5, 3], [4, 2], [1, 5, 3, 4], [2]] The minimum sum of maximum would be = [1], [5, 3, 4, 2] = 1 + 5 = 6