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 - iclass 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):
(x, y) → (x + y, y)(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";
}