OAmaster
— / 6已做

01Good Subsequences

A subsequence of a given string is generated by deleting zero or more characters from a string, then concatenating the remaining characters. A good subsequence is one where the frequency of each character is the same. Given a string that consists of n Latin letters, determine how many good subsequences it contains. Since the answer can be quite large, compute its modulo (10⁹ + 7). Note: An empty subsequence is not a good subsequence. Function Description Complete the function countGoodSubsequences in the editor below. countGoodSubsequences has the following parameter(s):

  • string word: a string that consists of only lowercase Latin letters Returns int: the number of good subsequences modulo (10⁹ + 7)

Example 1

Input:

word = "abca"

Output:

12

Explanation: A total of 15 non-empty subsequences can be formed from words: "a", "a", "aa", "ab", "aba", "abc", "abca", "ac", "aca", "b", "ba", "bc", "bca", "c", and "ca". The only subsequences that are not good are "aba," "aca," and "abca" as the frequency of character "a" is 2, and every other character is 1. The total number of good subsequences = 15 - 3 = 12 and answer to the above example = 12 modulo (10⁹+7) = 12.

Example 2

Input:

word = "abcd"

Output:

15

Explanation: All of the non-empty subsequences are good subsequences. They are "a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", and "d".

解法

统计每个字符出现次数 cnt[c]。枚举"每个字符出现 k 次"(k 从 1 到 max(cnt))，对每个 k 把所有 cnt[c] ≥ k 的字符各选 k 个的方案数相乘累加，即 ∏ C(cnt[c], k) 求和。预处理阶乘逆元，时间 O(26 · max_cnt + n)。

def countGoodSubsequences(word: str) -> int:
    MOD = 10**9 + 7
    n = len(word)
    cnt = [0] * 26
    for ch in word:
        cnt[ord(ch) - 97] += 1
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], MOD - 2, MOD)
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    def comb(a, b):
        if b < 0 or b > a:
            return 0
        return fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD
    ans = 0
    max_cnt = max(cnt)
    for k in range(1, max_cnt + 1):
        prod = 1
        for c in cnt:
            if c >= k:
                prod = prod * (comb(c, k) + 1) % MOD
        # prod 包含"每种字符可选 k 个或不选"，减去全不选的 1 种
        ans = (ans + prod - 1) % MOD
    return ans
class Solution {
    static final int MOD = 1_000_000_007;
    long[] fact, invFact;
    int countGoodSubsequences(String word) {
        int n = word.length();
        int[] cnt = new int[26];
        for (char ch : word.toCharArray()) cnt[ch - 'a']++;
        fact = new long[n + 1];
        invFact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
        invFact[n] = modPow(fact[n], MOD - 2);
        for (int i = n - 1; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % MOD;
        int maxCnt = 0;
        for (int c : cnt) maxCnt = Math.max(maxCnt, c);
        long ans = 0;
        for (int k = 1; k <= maxCnt; k++) {
            long prod = 1;
            for (int c : cnt) {
                if (c >= k) prod = prod * (comb(c, k) + 1) % MOD;
            }
            ans = (ans + prod - 1 + MOD) % MOD;
        }
        return (int) ans;
    }
    long comb(int a, int b) {
        if (b < 0 || b > a) return 0;
        return fact[a] * invFact[b] % MOD * invFact[a - b] % MOD;
    }
    long modPow(long b, long e) {
        long r = 1;
        b %= MOD;
        while (e > 0) { if ((e & 1) == 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
        return r;
    }
}
class Solution {
public:
    static const int MOD = 1'000'000'007;
    vector<long long> fact, invFact;
    long long modPow(long long b, long long e) {
        long long r = 1; b %= MOD;
        while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
        return r;
    }
    long long comb(int a, int b) {
        if (b < 0 || b > a) return 0;
        return fact[a] * invFact[b] % MOD * invFact[a - b] % MOD;
    }
    int countGoodSubsequences(string word) {
        int n = word.size();
        vector<int> cnt(26, 0);
        for (char ch : word) cnt[ch - 'a']++;
        fact.assign(n + 1, 1);
        invFact.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
        invFact[n] = modPow(fact[n], MOD - 2);
        for (int i = n - 1; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % MOD;
        int maxCnt = *max_element(cnt.begin(), cnt.end());
        long long ans = 0;
        for (int k = 1; k <= maxCnt; k++) {
            long long prod = 1;
            for (int c : cnt) if (c >= k) prod = prod * (comb(c, k) + 1) % MOD;
            ans = (ans + prod - 1 + MOD) % MOD;
        }
        return (int) ans;
    }
};

02Work Schedules (for MTS2)

An employee has to work exactly as many hours as they are told to each week, scheduling no more than a given daily maximum number of hours. On some days, the hours worked will be given. The employee gets to choose the remainder of their schedule, within the given limits. A completed schedule consists of exactly 7 digits in the range 0 to 8 that represent each day's work hours. A pattern string similar to the schedule is given, but the scheduled hours are marked by a question mark, ?, (ascii 63 decimal). Given a maximum number of hours that can be worked in a day, replace the question marks with digits so the scheduled hours is exactly the total hours that must be worked in a week. Determine all possible work schedules that meet the requirements and return them as a list of strings, sorted ascending. Function Description Complete the function findSchedules in the editor. findSchedules has the following parameter(s):

    1. int work_hours: the hours that must be worked in the week
    1. int day_hours: the maximum hours that may be worked in a day
    1. String pattern: the partially completed schedule Returns String arr[]: represents all possible valid schedules (must be ordered lexicographically ascending)

Constraints

  • 1 ≤ work_hours ≤ 56
  • 1 ≤ day_hours ≤ 8
  • | pattern | = 7
  • Each character of pattern ∈ {0, 1, ..., 8}
  • There is at least one correct schedule.

Example 1

Input:

work_hours = 24
day_hours = 4
pattern = "08??840"

Output:

["0804840", "0813840", "0822840", "0831840", "0840840"]

Explanation: There are 2 days on which they must work 24-20=4 more hours for the week. All of the possible schedules are listed below: 0804840 0813840 0822840 0831840 0840840

Example 2

Input:

work_hours = 56
day_hours = 8
pattern = "???8???"

Output:

["8888888"]

Explanation: There is only one way to work 56 hours in 7 days of 8 hours.

Example 3

Input:

work_hours = 3
day_hours = 8
pattern = "??2??00"

Output:

["0020100", "0021000", "0120000", "1020000"]

Explanation: work_hours = 3 day_hours = 2 pattern = '??2??00' They only need to schedule 1 more hour for the week, and it can be on any one of the days in question.

解法

回溯枚举每个 ? 填 0..day_hours，剪枝：剩余 ? 个数乘 day_hours 必须 ≥ 还差的小时数，已填总和不能超 work_hours。按位置从左到右填，自然得到字典序升序结果。时间 O((day_hours+1)^q)，q ≤ 7。

from typing import List

def findSchedules(work_hours: int, day_hours: int, pattern: str) -> List[str]:
    chars = list(pattern)
    q_idx = [i for i, c in enumerate(chars) if c == '?']
    fixed_sum = sum(int(c) for c in chars if c != '?')
    need = work_hours - fixed_sum
    res = []
    def dfs(i: int, remain: int):
        if i == len(q_idx):
            if remain == 0:
                res.append(''.join(chars))
            return
        left = len(q_idx) - i
        # 剪枝：剩余位置最多能填 left * day_hours
        if remain < 0 or remain > left * day_hours:
            return
        for d in range(0, day_hours + 1):
            chars[q_idx[i]] = str(d)
            dfs(i + 1, remain - d)
        chars[q_idx[i]] = '?'
    dfs(0, need)
    return res
import java.util.*;

class Solution {
    List<String> res;
    char[] chars;
    int[] qIdx;
    int dayHours;
    List<String> findSchedules(int work_hours, int day_hours, String pattern) {
        chars = pattern.toCharArray();
        dayHours = day_hours;
        List<Integer> qs = new ArrayList<>();
        int fixed = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '?') qs.add(i);
            else fixed += chars[i] - '0';
        }
        qIdx = qs.stream().mapToInt(Integer::intValue).toArray();
        res = new ArrayList<>();
        dfs(0, work_hours - fixed);
        return res;
    }
    void dfs(int i, int remain) {
        if (i == qIdx.length) {
            if (remain == 0) res.add(new String(chars));
            return;
        }
        int left = qIdx.length - i;
        if (remain < 0 || remain > (long) left * dayHours) return;
        for (int d = 0; d <= dayHours; d++) {
            chars[qIdx[i]] = (char) ('0' + d);
            dfs(i + 1, remain - d);
        }
        chars[qIdx[i]] = '?';
    }
}
class Solution {
public:
    vector<string> res;
    string chars;
    vector<int> qIdx;
    int dayHours;
    vector<string> findSchedules(int work_hours, int day_hours, string pattern) {
        chars = pattern;
        dayHours = day_hours;
        int fixed = 0;
        for (int i = 0; i < (int) chars.size(); i++) {
            if (chars[i] == '?') qIdx.push_back(i);
            else fixed += chars[i] - '0';
        }
        dfs(0, work_hours - fixed);
        return res;
    }
    void dfs(int i, int remain) {
        if (i == (int) qIdx.size()) {
            if (remain == 0) res.push_back(chars);
            return;
        }
        int left = (int) qIdx.size() - i;
        if (remain < 0 || remain > left * dayHours) return;
        for (int d = 0; d <= dayHours; d++) {
            chars[qIdx[i]] = (char) ('0' + d);
            dfs(i + 1, remain - d);
        }
        chars[qIdx[i]] = '?';
    }
};

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val. Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Constraints

  • 1 ≤ points.length ≤ 1000
  • -10⁶ ≤ xi, yi ≤ 10⁶
  • All pairs (xi, yi) are distinct.

Example 1

Input:

points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

Output:

20

Explanation: We can connect the points as shown above to get the minimum cost of 20. Notice that there is a unique path between every pair of points.

Example 2

Input:

points = [[3,12],[-2,5],[-4,1]]

Output:

18

Explanation: The points can be connected in various ways to get the minimum cost of 18.

解法

完全图 + 曼哈顿距离的最小生成树。点数较小时直接 Prim(稠密图 O(n²))：维护每个未加入点到已选集合的最小距离 minDist，每轮挑最小值加入并松弛邻接距离。

from typing import List

def minCostConnectPoints(points: List[List[int]]) -> int:
    n = len(points)
    if n <= 1:
        return 0
    INF = float('inf')
    min_dist = [INF] * n
    min_dist[0] = 0
    in_mst = [False] * n
    total = 0
    for _ in range(n):
        u = -1
        best = INF
        for v in range(n):
            if not in_mst[v] and min_dist[v] < best:
                best = min_dist[v]
                u = v
        in_mst[u] = True
        total += best
        xu, yu = points[u]
        for v in range(n):
            if not in_mst[v]:
                d = abs(xu - points[v][0]) + abs(yu - points[v][1])
                if d < min_dist[v]:
                    min_dist[v] = d
    return total
class Solution {
    int minCostConnectPoints(int[][] points) {
        int n = points.length;
        if (n <= 1) return 0;
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[0] = 0;
        boolean[] inMst = new boolean[n];
        int total = 0;
        for (int k = 0; k < n; k++) {
            int u = -1, best = Integer.MAX_VALUE;
            for (int v = 0; v < n; v++) {
                if (!inMst[v] && minDist[v] < best) {
                    best = minDist[v];
                    u = v;
                }
            }
            inMst[u] = true;
            total += best;
            for (int v = 0; v < n; v++) {
                if (!inMst[v]) {
                    int d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
                    if (d < minDist[v]) minDist[v] = d;
                }
            }
        }
        return total;
    }
}
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 1) return 0;
        vector<int> minDist(n, INT_MAX);
        vector<bool> inMst(n, false);
        minDist[0] = 0;
        int total = 0;
        for (int k = 0; k < n; k++) {
            int u = -1, best = INT_MAX;
            for (int v = 0; v < n; v++) {
                if (!inMst[v] && minDist[v] < best) {
                    best = minDist[v];
                    u = v;
                }
            }
            inMst[u] = true;
            total += best;
            for (int v = 0; v < n; v++) {
                if (!inMst[v]) {
                    int d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]);
                    if (d < minDist[v]) minDist[v] = d;
                }
            }
        }
        return total;
    }
};

Given an array arr of length n, the following types of operations can be performed on it:

  • Operation type 1: Shift the array cyclically by 1 towards the left.
  • Operation type 2: Swap any 2 elements of the array. However, once an operation of type 2 is performed, operations of type 1 cannot be performed again. The participants are required to find the minimum number of operations in which the given array can be converted into the sequence (1, 2, 3, ..., n). Note: It is guaranteed that the array arr is a permutation of the target array [1, 2, 3, ..., n] and hence, the answer will always exist. Function Description Complete the function minimumOperationsToConvertArray in the editor. minimumOperationsToConvertArray has the following parameter:
  • int[] arr: an array of integers Returns int: the minimum number of operations required

Constraints

N/A

Example 1

Input:

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

Output:

2

Explanation: The following sequence of operations can be performed:

  • Type 1: Shift the array cyclically left once to obtain (3, 2, 1, 4, 5).
  • Type 2: Swap the first and third elements, the array becomes (1, 2, 3, 4, 5) which is the required target. It can be shown that the array cannot be transformed in less than 2 operations. Thus, the answer is 2.
Pro解法 · 三语代码 · 复杂度分析
边界讨论 + 面试官追问 · $98 / 一年解锁

05No Adjacent Characters

You are given a string with only one repetitive alphabet. Determine if it is possible to create a string with no adjacent alphabets being the same. Return "NOT POSSIBLE" if:

  • Re-arrangement is required but is not possible. Return "POSSIBLE" if:
  • There is no rearrangement required as the string is already in the right format.
  • Re-arrangement is required and a new string has no adjacent alphabets which are the same. Function Description Complete the function canRearrangeString in the editor. canRearrangeString has the following parameter:
  • String s: the string to check Returns String: either "POSSIBLE" or "NOT POSSIBLE"

Constraints

N/A

Example 1

Input:

s = "ab"

Output:

"POSSIBLE"

Explanation: Re-arrangement is required and the new string has no adjacent alphabets which are the same. We can create the string as "aba".

Pro解法 · 三语代码 · 复杂度分析
边界讨论 + 面试官追问 · $98 / 一年解锁

A group of friends are playing a video game together. During the game, each player earns a number of points. At the end of a round, players who achieve at least a certain rank k get to "level up" their characters to gain increased abilities. Given the scores of the players at the end of a round, how many players will be able to level up? Note: Players with equal scores will have equal ranks, but the player with the next lower score will be ranked based on the position within the list of all players' scores. For example, if there are four players, and three of them tie for first place, their ranks are 1, 1, 1, and 4. Note: No player with a score of 0 can level up, regardless of rank. Function Description Complete the function numPlayers in the editor. numPlayers has the following parameters:

    1. k: the cutoff rank to level up a player's character
    1. scores[n]: the players' scores Returns int: the number of players who can level up after this round

Constraints

  • 1 ≤ n ≤ 10⁵
  • 0 ≤ scores[i] ≤ 100
  • k ≤ n

Example 1

Input:

k = 3
scores = [100, 50, 50, 25]

Output:

3

Explanation: These players' ranks are [1, 2, 2, 4]. Because the players need to have a rank of at least k = 3 to level up, only the first three players qualify. Therefore, the answer is 3.

Example 2

Input:

k = 4
scores = [20, 40, 60, 80, 100]

Output:

4

Explanation: The players achieve the ranks [5, 4, 3, 2, 1] in order. Since the cutoff k, is rank ≥ 4, there are 4 players who can level up.

Example 3

Input:

k = 4
scores = [2, 2, 3, 4, 5]

Output:

5

Explanation: The players achieve the ranks [4, 4, 3, 2, 1] in order. Since the cutoff rank is 4, all 5 players can level up.

Pro解法 · 三语代码 · 复杂度分析
边界讨论 + 面试官追问 · $98 / 一年解锁
Pro 会员

解锁全部 3 道题的解法

题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.

Pro 解锁全部
  • 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
  • 📊个人 dashboard + 进度可视化 + 14 天活跃图
  • 📝题目笔记跨设备同步 + 个人复盘库
  • 🔓随时取消下次续费, Stripe Customer Portal 自助管理
$12/月($98/年, 一次付清省 32%)

≈ 北美 SWE 工资 10 分钟 · LeetCode Premium $35/月 的 23%

立即解锁 $98/年已是会员, 去登录

Upstart

Upstart OA 真题，三语题解(Python / Java / C++)。

Rubrik

Rubrik 真实 OA 题库，三语题解 (Python / Java / C++)。