Superhuman

01Lost Messages

A message is represented as a string of space-delimited words. You are given two strings:

sent: the original message
received: the message that was recovered after transmission Some words may be missing from received. It is guaranteed that all words in received appear in the same relative order as they do in sent. Return all words that appear in sent but do not appear in received, preserving their original order. Function Description Complete the function lostFragments in the editor below. lostFragments has the following parameters:
String sent: the original message that was sent
String received: the recovered message after transmission Returns String[]: the words from sent that are missing from received, in the order they appear in sent

Constraints

sent and received contain only lowercase or uppercase English letters and spaces.
Words are separated by single spaces.
1 ≤ received.length() < sent.length() ≤ 10⁵
The length of any individual word in sent or received is at most 15.
received is guaranteed to be a subsequence of sent at the word level.

Example 1

Input:

sent = "I am a programmer"
received = "I programmer"

Output:

["am", "a"]

Explanation: The words "am" and "a" appear in sent but are missing from received, so they are returned in order.

Example 2

Input:

sent = "we love coding daily"
received = "we coding"

Output:

["love", "daily"]

Explanation: The recovered message keeps "we" and "coding" in order, so the missing words are "love" and "daily".

Example 3

Input:

sent = "alpha beta gamma delta"
received = "alpha delta"

Output:

["beta", "gamma"]

Explanation: The recovered message is a subsequence of the sent message. The missing words between the matched endpoints are returned.

解法

双指针：把两条字符串按空格拆词，i 扫 sent、j 扫 received，若匹配则两指针都进，否则把 sent[i] 加入答案、i 进。时间 O(N+M)。

from typing import List

def lost_fragments(sent: str, received: str) -> List[str]:
    s = sent.split()
    r = received.split()
    out: List[str] = []
    j = 0
    for w in s:
        if j < len(r) and w == r[j]:
            j += 1
        else:
            out.append(w)
    return out

import java.util.*;

class Solution {
    public String[] lostFragments(String sent, String received) {
        String[] s = sent.split("\\s+"), r = received.split("\\s+");
        List<String> out = new ArrayList<>();
        int j = 0;
        for (String w : s) {
            if (j < r.length && w.equals(r[j])) j++;
            else out.add(w);
        }
        return out.toArray(new String[0]);
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> lostFragments(string sent, string received) {
        auto split = [](const string& s) { vector<string> v; stringstream ss(s); string t; while (ss >> t) v.push_back(t); return v; };
        auto s = split(sent), r = split(received);
        vector<string> out;
        size_t j = 0;
        for (auto& w : s) {
            if (j < r.size() && w == r[j]) j++;
            else out.push_back(w);
        }
        return out;
    }
};

You are given a sorted array points representing the point values of homework problems in the order they appear. A student must solve the first problem at index 0. After solving a problem at index i, the student may solve either the next problem i + 1 or skip one problem and solve i + 2. The student continues until the difference between the maximum and minimum point values among the solved problems is at least threshold. If that can never be achieved, the student must solve all problems. Return the minimum number of problems the student needs to solve. Function Description Complete the function minProblemsToSolve in the editor below. minProblemsToSolve has the following parameters:

int[] points: sorted point values for the homework problems
int threshold: the required spread between the minimum and maximum solved point values Returns int: the minimum number of problems that must be solved

Constraints

points is sorted in non-decreasing order.
1 ≤ points[i] < 1000.
1 ≤ threshold < 1000.

Example 1

Input:

points = [1, 2, 3, 5, 8]
threshold = 4

Output:

Explanation: Solve the problems worth 1, 3, and 8. The solved values have spread 8 - 1 = 7, and it takes only 3 problems.

Example 2

Input:

points = [1, 2, 3, 4, 5]
threshold = 4

Output:

Explanation: Solve the problems worth 1, 3, and 5. The spread is exactly 4, so the answer is 3.

Example 3

Input:

points = [4, 5, 6, 7]
threshold = 10

Output:

Explanation: Even after solving every problem, the spread is only 7 - 4 = 3, so the student must solve all 4 problems.

解法

从 0 出发，每步 +1 或 +2。要让最大值 − 最小值 ≥ threshold 用最少步。贪心：始终走 +2，因为序列非降，跳得远能更快拉大 max − min。只有当跳 +2 越过数组末尾时才退回 +1。模拟。时间 O(n)。

from typing import List

def min_problems_to_solve(points: List[int], threshold: int) -> int:
    n = len(points)
    i = 0; count = 1; min_v = max_v = points[0]
    while max_v - min_v < threshold:
        nxt = i + 2 if i + 2 < n else i + 1
        if nxt >= n:
            return n
        i = nxt
        min_v = min(min_v, points[i])
        max_v = max(max_v, points[i])
        count += 1
    return count

class Solution {
    public int minProblemsToSolve(int[] points, int threshold) {
        int n = points.length;
        int i = 0, count = 1, mn = points[0], mx = points[0];
        while (mx - mn < threshold) {
            int nxt = (i + 2 < n) ? i + 2 : i + 1;
            if (nxt >= n) return n;
            i = nxt;
            mn = Math.min(mn, points[i]);
            mx = Math.max(mx, points[i]);
            count++;
        }
        return count;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minProblemsToSolve(vector<int>& points, int threshold) {
        int n = points.size();
        int i = 0, count = 1, mn = points[0], mx = points[0];
        while (mx - mn < threshold) {
            int nxt = (i + 2 < n) ? i + 2 : i + 1;
            if (nxt >= n) return n;
            i = nxt;
            mn = min(mn, points[i]);
            mx = max(mx, points[i]);
            count++;
        }
        return count;
    }
};

03Optimal Transfer

There are n servers in a network, arranged in ascending order of their capacities. The capacity of server i is capacity[i], and all capacity values are distinct. The distance between server i and server j is |capacity[i] - capacity[j]|. For each server, its closest server is the one with the smallest distance in capacity, and that closest server is guaranteed to be unique. You may perform either of the following operations from a server x:

Connect directly to any server y at cost |capacity[x] - capacity[y]|.
Connect to the closest server of x at a fixed cost of 1. Given query arrays fromServer and toServer, compute the minimum cost required to connect from fromServer[i] to toServer[i] for each query. A path may be direct or may route through intermediate servers. Function Description Complete the function minimumTransferCost in the editor below. minimumTransferCost has the following parameters:
int[] capacity: distinct server capacities in ascending order
int[] fromServer: starting server index for each query
int[] toServer: destination server index for each query Returns int[]: the minimum connection cost for each query in order

Constraints

capacity is sorted in ascending order.
All values in capacity are distinct.
fromServer.length == toServer.length.

Example 1

Input:

capacity = [2, 7, 10]
fromServer = [0, 1, 2]
toServer = [2, 2, 1]

Output:

[2, 1, 1]

Explanation: The closest edges are 0 -> 1, 1 -> 2, and 2 -> 1, each costing 1. So the optimal costs are 0 -> 1 -> 2 = 2, 1 -> 2 = 1, and 2 -> 1 = 1.

Example 2

Input:

capacity = [1, 4, 9, 15]
fromServer = [0, 3, 1]
toServer = [3, 0, 3]

Output:

[3, 3, 2]

Explanation: Closest-server hops form a cheap chain: 0 -> 1, 1 -> 2, and 3 -> 2. The best routes are 0 -> 1 -> 2 -> 3 with cost 3, 3 -> 2 -> 1 -> 0 with cost 3, and 1 -> 2 -> 3 with cost 2.

Example 3

Input:

capacity = [5, 6, 20]
fromServer = [2, 0]
toServer = [0, 1]

Output:

[2, 1]

Explanation: Server 2 is closest to server 1, and server 1 is closest to server 0. So 2 -> 1 -> 0 costs 2, and 0 -> 1 costs 1.

解法

from typing import List

def minimum_transfer_cost(capacity: List[int], from_server: List[int], to_server: List[int]) -> List[int]:
    out: List[int] = []
    for a, b in zip(from_server, to_server):
        chain = abs(b - a)
        direct = abs(capacity[a] - capacity[b])
        out.append(min(chain, direct))
    return out

class Solution {
    public int[] minimumTransferCost(int[] capacity, int[] fromServer, int[] toServer) {
        int q = fromServer.length;
        int[] out = new int[q];
        for (int i = 0; i < q; i++) {
            int chain = Math.abs(toServer[i] - fromServer[i]);
            int direct = Math.abs(capacity[fromServer[i]] - capacity[toServer[i]]);
            out[i] = Math.min(chain, direct);
        }
        return out;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> minimumTransferCost(vector<int>& capacity, vector<int>& fromServer, vector<int>& toServer) {
        vector<int> out;
        for (int i = 0; i < (int)fromServer.size(); i++) {
            int chain = abs(toServer[i] - fromServer[i]);
            int direct = abs(capacity[fromServer[i]] - capacity[toServer[i]]);
            out.push_back(min(chain, direct));
        }
        return out;
    }
};

01Lost Messages

02Math Homework

03Optimal Transfer