登录
OAmaster

A sequence of numbers is said to be good if it satisfies the following two conditions:

  • All elements in the sequence are unique.
  • If the minimum element in the sequence is a, and the maximum element in the sequence is b, then all numbers in the range [a, b] are present in the sequence. For example, (4, 2, 5, 1, 3) is a good sequence, while (2, 2, 1) or (3, 7) are not. A subsequence of an array arr is a sequence that can be derived from the array arr by deleting some or no elements without changing the order of the remaining elements. Given an array of n integers, find the number of different good subsequences. Two subsequences are considered different if they include at least one different index. For example, for the sequence (2, 2, 1), both (2, 1) formed by indices 1 and 2 and (2, 1) formed by indices 0 and 2 are considered different subsequences. Function Description Complete the function countGoodSubsequences in the editor. countGoodSubsequences has the following parameter: int arr[n]: the given array of integers Returns long integer: the number of good subsequences which can be derived from the array.

Constraints

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ arr[i] ≤ 10⁵, for all i

解法

"good"子序列由互不相同元素且为 [a, b] 区间内的所有整数构成(顺序任意)，因为是子序列，相对顺序与原数组一致；good 子序列中元素无重复且值集为 [a, b] 完整。统计：枚举值区间 [a, b]，再统计 arr 中能取出 a, a+1, ..., b 各一次的子序列个数。对每个值 v 出现次数 cnt[v]。对固定 [a, b]，每个值 v ∈ [a, b] 必须挑一个位置；不同位置组合即 ∏_{v=a}^{b} cnt[v]，但是子序列还要求相对顺序保持，"挑选每个值各一个位置"已经天然满足子序列定义(无论挑哪个位置都对应一个子序列)。所以答案 = Σ over [a, b] (∏ cnt[v])。可双指针扫：从 a 开始连续延伸 b 直到 v=b+1 缺失(cnt=0)。用前缀乘积 / 段乘积。时间 O(max_v)。

from collections import Counter
from typing import List

MOD = 10 ** 9 + 7

def count_good_subsequences(arr: List[int]) -> int:
    cnt = Counter(arr)
    if not cnt: return 0
    max_v = max(cnt)
    total = 0
    v = 1
    while v <= max_v:
        if cnt.get(v, 0) == 0:
            v += 1
            continue
        # find longest run [v, e] with cnt[u] > 0
        e = v
        while e + 1 <= max_v and cnt.get(e + 1, 0) > 0:
            e += 1
        # sum over [a, b] subset of [v, e]: prod cnt[a..b]
        # = sum over a from v..e of (cnt[a] * (1 + cnt[a+1] * (1 + cnt[a+2] * ...)))
        # iterate from e down
        chain = 0
        for u in range(e, v - 1, -1):
            chain = cnt[u] * (1 + chain) % MOD
            total = (total + chain) % MOD
        # subtract? No, chain already covers all [a, b] starting at u.
        # But this DOUBLE-counts because we counted each (a, b). Let's verify: chain[a] = sum over b>=a of prod cnt[a..b]. So sum chain[a] over a = total #[a,b] pairs. Good.
        v = e + 1
    return total
import java.util.*;

class Solution {
    static final long MOD = 1_000_000_007L;
    public long countGoodSubsequences(int[] arr) {
        Map<Integer, Long> cnt = new HashMap<>();
        int maxV = 0;
        for (int x : arr) { cnt.merge(x, 1L, Long::sum); maxV = Math.max(maxV, x); }
        long total = 0;
        int v = 1;
        while (v <= maxV) {
            if (cnt.getOrDefault(v, 0L) == 0) { v++; continue; }
            int e = v;
            while (e + 1 <= maxV && cnt.getOrDefault(e + 1, 0L) > 0) e++;
            long chain = 0;
            for (int u = e; u >= v; u--) {
                chain = cnt.get(u) * (1 + chain) % MOD;
                total = (total + chain) % MOD;
            }
            v = e + 1;
        }
        return total;
    }
}
#include <bits/stdc++.h>
using namespace std;

class Solution {
    static constexpr long long MOD = 1000000007;
public:
    long long countGoodSubsequences(vector<int>& arr) {
        unordered_map<int, long long> cnt;
        int maxV = 0;
        for (int x : arr) { cnt[x]++; maxV = max(maxV, x); }
        long long total = 0;
        int v = 1;
        while (v <= maxV) {
            if (!cnt.count(v) || cnt[v] == 0) { v++; continue; }
            int e = v;
            while (e + 1 <= maxV && cnt.count(e + 1) && cnt[e + 1] > 0) e++;
            long long chain = 0;
            for (int u = e; u >= v; u--) {
                chain = cnt[u] * (1 + chain) % MOD;
                total = (total + chain) % MOD;
            }
            v = e + 1;
        }
        return total;
    }
};

Given a number line from 0 to n and a string denoting a sequence of moves, determine the number of subsequences of those moves that lead from a given point x to end at another point y. Moves will be given as a sequence of l and r instructions. An instruction l = left movement, so from position j the new position is j - 1, an instruction r = right movement, so from position j the new position would be j + 1. For example, given a number line from 0 to 6, and a sequence of moves rrlrr, the number of subsequences that lead from 1 to 4 on the number line is 3. Function Description Complete the function distinctMoves in the editor. distinctMoves has the following parameter(s):

  • s: a string that represents a sequence of moves
  • n: an integer that represents the upper bound of the number line
  • x: an integer that represents the starting point
  • y: an integer that represents the ending point Returns int: the number of distinct subsequences modulo 10⁹ + 7

Constraints

  • 1 ≤ |s| ≤ 10³
  • 0 ≤ x, y, n ≤ 2500

解法

DP dp[i][j] = 用 s 前 i 个字符的某个子序列，从 x 出发能到达位置 j 的方案数。转移：dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] if s[i-1]=='r' else 0) + (dp[i-1][j+1] if s[i-1]=='l' else 0)，需 0 ≤ j ≤ n。最终 dp[len(s)][y]。时间 O(|s|·n)。

MOD = 10 ** 9 + 7

def distinct_moves(s: str, n: int, x: int, y: int) -> int:
    dp = [0] * (n + 1)
    dp[x] = 1
    for c in s:
        nxt = [0] * (n + 1)
        for j in range(n + 1):
            nxt[j] = dp[j]
            if c == 'r' and j > 0:
                nxt[j] = (nxt[j] + dp[j - 1]) % MOD
            if c == 'l' and j < n:
                nxt[j] = (nxt[j] + dp[j + 1]) % MOD
        dp = nxt
    return dp[y]
class Solution {
    static final long MOD = 1_000_000_007L;
    public int distinctMoves(String s, int n, int x, int y) {
        long[] dp = new long[n + 1];
        dp[x] = 1;
        for (char c : s.toCharArray()) {
            long[] nxt = dp.clone();
            for (int j = 0; j <= n; j++) {
                if (c == 'r' && j > 0) nxt[j] = (nxt[j] + dp[j - 1]) % MOD;
                if (c == 'l' && j < n) nxt[j] = (nxt[j] + dp[j + 1]) % MOD;
            }
            dp = nxt;
        }
        return (int) dp[y];
    }
}
#include <bits/stdc++.h>
using namespace std;

class Solution {
    static constexpr long long MOD = 1000000007;
public:
    int distinctMoves(string s, int n, int x, int y) {
        vector<long long> dp(n + 1, 0);
        dp[x] = 1;
        for (char c : s) {
            vector<long long> nxt = dp;
            for (int j = 0; j <= n; j++) {
                if (c == 'r' && j > 0) nxt[j] = (nxt[j] + dp[j - 1]) % MOD;
                if (c == 'l' && j < n) nxt[j] = (nxt[j] + dp[j + 1]) % MOD;
            }
            dp = nxt;
        }
        return (int) dp[y];
    }
};

A school in HackerLand organized a scholarship exam with this interesting mathematics problem on addition. Given a string num that consists of digits ('0' to '9'), a '+' can be inserted between its characters. No adjacent '+' characters are allowed. The value of the expression is then evaluated. Find the sum of the values of all possible expressions after inserting '+' characters any number of times (possibly zero). Since the answer can be large, return the value modulo (10⁹ + 7). Function Description Complete the function getExpressionSums in the editor below. getExpressionSums has the following parameter(s):

Constraints

An unknown myth for now

Example 1

Input:

num = "123"

Output:

168

Explanation: All possible valid expressions are shown.

  • "1 + 23", value = 24
  • "12 + 3", value = 15
  • "1 + 2 + 3", value = 6
  • "123", value = 123 Their sum is 24 + 15 + 6 + 123 = 168. Thus, the answer is 168 modulo (10⁹ + 7) which is 168.

解法

考察每个数字 num[i] 对答案的总贡献。在 n-1 个空隙中各自独立决定是否加 '+'，共 2^(n-1) 种表达式。num[i] 在某段中所贡献的位权 = 10^(距离段右端)。汇总：对位置 i，遍历它在所有可能表达式中出现的"段长"。若 i 与 j 在同一段，意味着 i..j 之间无 '+'(共 j-i 个空隙都无 '+')，且 j 后面必须有 '+'(或 j == n-1)。所以贡献 = num[i] · Σ over j 10^(j-i) · 2^(其它空隙的自由选择)。复杂度 O(n²)。

MOD = 10 ** 9 + 7

def get_expression_sums(num: str) -> int:
    n = len(num)
    # pow10[k], pow2[k] precompute
    pow10 = [1] * (n + 1)
    pow2 = [1] * (n + 1)
    for i in range(1, n + 1):
        pow10[i] = pow10[i - 1] * 10 % MOD
        pow2[i] = pow2[i - 1] * 2 % MOD
    total = 0
    for i in range(n):
        # num[i] contributes when it sits at position (k from right) in its segment
        for j in range(i, n):
            d = j - i  # 10^d weight
            # gaps fixed: between i and j all "no +" (d gaps), gap after j is "+" if j < n-1 (1 gap fixed)
            fixed = d + (1 if j < n - 1 else 0)
            free = (n - 1) - fixed
            total = (total + int(num[i]) * pow10[d] % MOD * pow2[free]) % MOD
    return total
class Solution {
    static final long MOD = 1_000_000_007L;
    public int getExpressionSums(String num) {
        int n = num.length();
        long[] pow10 = new long[n + 1], pow2 = new long[n + 1];
        pow10[0] = pow2[0] = 1;
        for (int i = 1; i <= n; i++) { pow10[i] = pow10[i - 1] * 10 % MOD; pow2[i] = pow2[i - 1] * 2 % MOD; }
        long total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int d = j - i;
                int fixed = d + (j < n - 1 ? 1 : 0);
                int free = (n - 1) - fixed;
                total = (total + (num.charAt(i) - '0') * pow10[d] % MOD * pow2[free]) % MOD;
            }
        }
        return (int) total;
    }
}
#include <bits/stdc++.h>
using namespace std;

class Solution {
    static constexpr long long MOD = 1000000007;
public:
    int getExpressionSums(string num) {
        int n = num.size();
        vector<long long> pow10(n + 1, 1), pow2(n + 1, 1);
        for (int i = 1; i <= n; i++) { pow10[i] = pow10[i - 1] * 10 % MOD; pow2[i] = pow2[i - 1] * 2 % MOD; }
        long long total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int d = j - i;
                int fixed_ = d + (j < n - 1 ? 1 : 0);
                int free_ = (n - 1) - fixed_;
                total = (total + (num[i] - '0') * pow10[d] % MOD * pow2[free_]) % MOD;
            }
        }
        return (int) total;
    }
};
Pro 会员

解锁剩余 5 道 OA 真题

开通后立即解锁完整题面 + Python / Java / C++ 三语题解。 全站 165 家公司 · 1000+ 道 OA · 月度更新。

开通会员已是会员，去登录

Waymo

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

TradeDesk

TradeDesk 真实 OA 题库，多级 system design 一题完整覆盖。