Given two sets of data, current and desired, each represents the order of n layers within the neural network architecture. During the training of the model, an operation can be performed to adjust the arrangement of layers. In one step, a layer is selected from the end of the list and inserted at any arbitrary position within the list.

Determine the minimum number of steps required to transform the initial arrangement (current) into the desired arrangement (desired) while training the neural network.

Note: It is guaranteed that the desired arrangement can always be achieved using the given operation.

Example

n = 5
current = [2, 1, 3, 5, 4]
required = [2, 4, 1, 5, 3]
Pick layer 4 and insert it in [2,1,3,5,4] as [2,4,1,3,5].
Pick layer 5 and insert it in [2,4,1,3,5] as [2,4,1,5,3].
Therefore, the answer is 2 steps.

解法

弹出并尾插等价于：找 desired 的最长前缀，使其在 current 中作为子序列出现；其余元素必须搬动。在 current 和 desired 上双指针计匹配数，答案 = n - matched。复杂度 O(N)。

def get_min_steps(current, desired):
    n = len(current)
    i = j = 0
    while i < n and j < n:
        if current[i] == desired[j]:
            i += 1
        j += 1
    return n - i

class Solution {
    static int getMinSteps(int[] current, int[] desired) {
        int n = current.length, i = 0, j = 0;
        while (i < n && j < n) {
            if (current[i] == desired[j]) i++;
            j++;
        }
        return n - i;
    }
}

int getMinSteps(vector<int>& current, vector<int>& desired) {
 int n = current.size(), i = 0, j = 0;
 while (i < n && j < n) {
 if (current[i] == desired[j]) i++;
 j++;
 }
 return n - i;
}

As part of enhancing a music streaming platform's user experience, your team wants to develop a ranking among songs by their popularity. Given n users and m songs, each user i has a preference list, pref[i], which is a permutation of numbers 0 to m−1, indicating the user's preference for a song. If a < b, the user prefers song pref[i][a] over song pref[i][b].

To rank the songs, use the following approach: song x is said to beat song y if it is preferred over y by more than half of the users or if exactly half of the users prefer x over y and x has a smaller id. Song x is more popular than y if x beats more songs than y. Ties on beat-count break by smaller id.

Output: list of song ids in ranking order (most popular first).

Example: n=3, m=3, pref = [[0,1,2], [0,2,1], [1,2,0]] → [0, 1, 2].

解法

对每个有序对 (x, y)，统计多少用户更喜欢 x。比较规则：x 胜过 y 当且仅当 2 · votes_x > n，或 2 · votes_x == n && x < y。按击败对数降序对歌曲 id 排序，平局取 id 小者。复杂度 O(M² · N)。

from functools import cmp_to_key

def rank_songs(n, m, pref):
    rank_of = [[0]*m for _ in range(n)]
    for u in range(n):
        for pos, s in enumerate(pref[u]):
            rank_of[u][s] = pos

    def cmp(x, y):
        votes_x = sum(1 for u in range(n) if rank_of[u][x] < rank_of[u][y])
        if 2 * votes_x > n:
            return -1
        if 2 * votes_x < n:
            return 1
        return x - y

    return sorted(range(m), key=cmp_to_key(cmp))

class Solution {
    static Integer[] rankSongs(int n, int m, int[][] pref) {
        int[][] rankOf = new int[n][m];
        for (int u = 0; u < n; u++)
            for (int pos = 0; pos < m; pos++) rankOf[u][pref[u][pos]] = pos;
        Integer[] ids = new Integer[m];
        for (int i = 0; i < m; i++) ids[i] = i;
        Arrays.sort(ids, (x, y) -> {
            int votesX = 0;
            for (int u = 0; u < n; u++) if (rankOf[u][x] < rankOf[u][y]) votesX++;
            if (2 * votesX > n) return -1;
            if (2 * votesX < n) return 1;
            return x - y;
        });
        return ids;
    }
}

vector<int> rankSongs(int n, int m, vector<vector<int>>& pref) {
 vector<vector<int>> rankOf(n, vector<int>(m));
 for (int u = 0; u < n; u++)
 for (int pos = 0; pos < m; pos++) rankOf[u][pref[u][pos]] = pos;
 vector<int> ids(m);
 iota(ids.begin(), ids.end(), 0);
 sort(ids.begin(), ids.end(), [&](int x, int y) {
 int votesX = 0;
 for (int u = 0; u < n; u++) if (rankOf[u][x] < rankOf[u][y]) votesX++;
 if (2 * votesX > n) return true;
 if (2 * votesX < n) return false;
 return x < y;
 });
 return ids;
}

A bot is at integer coordinates (sx, sy) and wants to reach (tx, ty). It can only make two moves from (x, y):

1. (x, y) → (x + y, y)
2. (x, y) → (x, x + y)

Both moves strictly increase a coordinate, so each step lands on a greater x or greater y. Given (sx, sy) and (tx, ty), return "Yes" if reachable, else "No".

Example: sx=1, sy=1, tx=3, ty=5 → Yes (path (1,1) → (1,2) → (3,2) → (3,5)).

解法

从 (tx, ty) 倒推欧几里得：tx > ty 时前驱必为 (tx % ty, ty)；否则为 (tx, ty % tx)。当某坐标等于起点时停止，另一坐标必须通过整数倍可达。等价于 gcd(tx, ty) == gcd(sx, sy) 且链上奇偶性匹配。复杂度 O(log(max(tx, ty)))。

def can_reach(sx, sy, tx, ty):
    while tx >= sx and ty >= sy:
        if tx == sx and ty == sy:
            return "Yes"
        if tx > ty:
            if ty == sy:
                return "Yes" if (tx - sx) % ty == 0 else "No"
            tx %= ty
        else:
            if tx == sx:
                return "Yes" if (ty - sy) % tx == 0 else "No"
            ty %= tx
    return "No"

class Solution {
    static String canReach(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (tx == sx && ty == sy) return "Yes";
            if (tx > ty) {
                if (ty == sy) return (tx - sx) % ty == 0 ? "Yes" : "No";
                tx %= ty;
            } else {
                if (tx == sx) return (ty - sy) % tx == 0 ? "Yes" : "No";
                ty %= tx;
            }
        }
        return "No";
    }
}

string canReach(int sx, int sy, int tx, int ty) {
 while (tx >= sx && ty >= sy) {
 if (tx == sx && ty == sy) return "Yes";
 if (tx > ty) {
 if (ty == sy) return (tx - sx) % ty == 0 ? "Yes" : "No";
 tx %= ty;
 } else {
 if (tx == sx) return (ty - sy) % tx == 0 ? "Yes" : "No";
 ty %= tx;
 }
 }
 return "No";
}

There is a row of two-position switches aligned in a row and numbered consecutively starting from 1. Each of the switches is initially in its "Off" position. Over some number of operations, a left and right index will be provided. When a current is applied to two switches, a NOT operation is applied to each switch in the inclusive interval between those switches. That is, if a switch is off, it is turned on, and vice versa. Given a series of operations, determine their final state. Calculate the sum of all indices where a switch is on. Function Description Complete the function calculateTheSum in the editor. calculateTheSum has the following parameter:

• int n: the number of operations
• int[][] operations: a 2D array of integers where each element is an array of two integers representing the left and right indices for the operation Returns int: the sum of all indices where a switch is on

Constraints

(˶˃ ᵕ ˂˶) .ᐟ.ᐟ

When evaluating a machine learning model, n test cases are provided. Each is associated with an arrivalTime[i] indicating the times each test case was given. The testing environment is activated once for some time, then enters an inactive state. If activated at time t1 and deactivated at time t2, tests with arrival times between t1 and t2 (inclusive) are executed. The total time the system was active is t2 - t1. Efficiency of testing system = number of test cases tested - total time the system was active. Determine the maximum efficiency when the testing environment selects optimum activation and deactivation times. The environment must execute at least two test cases during its active period. Return the maximum possible efficiency. Notes:

• Execution time for test cases is practically instantaneous; that is, it takes almost no time.
• If two test cases share the same arrival time, they are evaluated simultaneously.
• Efficiency may take negative values. Function Description Complete the function getMaxEfficiency in the editor below. getMaxEfficiency takes the following parameter(s):
• int arrivalTime[n]: the arrival time of each prompt Returns int: the maximum efficiency possible

Constraints

• 2 ≤ n ≤ 2 * 10⁵
• 1 ≤ arrivalTime[i] ≤ 10⁹

Example 1

Input:

arrivalTime = [9, 1, 3, 5, 6]

Output:

1

Explanation: It is optimal to choose t1 = 5 and t2 = 6. If the testing environment is active from t = 5 to 6, the 4th and 5th test cases will be executed. The number of test cases tested = 2 and the time the system was active is 6 - 5 = 1. The efficiency of the system is 2 - 1 = 1. Return 1 as the answer.

Example 2

Input:

arrivalTime = [4, 2, 1]

Output:

1

Explanation: Choose t1 = 1 and t2 = 2. If the system is active from t = 1 to 2, test cases 1 and 2 will be tested. The efficiency of the system is 2 - 1 = 1.