登录
OAmaster

Same as LC.2964 The cost of a stock on each day is given in an array, arr. An investor wants to buy the stocks in triplets such that the sum of the cost for three days is divisible by d. The goal is to find the number of distinct triplets (i, j, k) such that i Function Description Complete the function getTripletCountin the editor below. The function must return an integer denoting the total number of distinct triplets.getTripletCount` has the following parameters:

  • int arr[n]: array of integers
  • int d: the divisor

Example 1

Input:

arr = [3, 3, 4, 7, 8]
d = 5

Output:

3

Explanation: The triplets whose sum is divisible by d are shown.

  • Triplet with indices - (0, 1, 2), sum = 3+3+4 = 10
  • Triplet with indices - (0, 2, 4), sum = 3+4+8 = 15
  • Triplet with indices - (1, 2, 4), sum = 3+4+8 = 15 Hence, the answer is 3.

解法

LC 2964。统计每个余数 mod d 的频次 cnt[0..d-1]，枚举 (r1, r2, r3)(每个从 0 到 d-1)使 (r1+r2+r3) % d == 0；对不同余数组合用乘法，相同需用组合数。时间复杂度 O(d²)，空间复杂度 O(d)。

from typing import List

def getTripletCount(arr: List[int], d: int) -> int:
    cnt = [0] * d
    for x in arr:
        cnt[x % d] += 1
    ans = 0
    for r1 in range(d):
        for r2 in range(r1, d):
            r3 = (-(r1 + r2)) % d
            if r3 < r2: continue
            if r1 == r2 == r3:
                ans += cnt[r1] * (cnt[r1] - 1) * (cnt[r1] - 2) // 6
            elif r1 == r2:
                ans += cnt[r1] * (cnt[r1] - 1) // 2 * cnt[r3]
            elif r2 == r3:
                ans += cnt[r1] * cnt[r2] * (cnt[r2] - 1) // 2
            elif r1 == r3:
                ans += cnt[r1] * (cnt[r1] - 1) // 2 * cnt[r2]
            else:
                ans += cnt[r1] * cnt[r2] * cnt[r3]
    return ans
class Solution {
    long getTripletCount(int[] arr, int d) {
        long[] cnt = new long[d];
        for (int x : arr) cnt[((x % d) + d) % d]++;
        long ans = 0;
        for (int r1 = 0; r1 < d; r1++) for (int r2 = r1; r2 < d; r2++) {
            int r3 = ((- (r1 + r2)) % d + d) % d;
            if (r3 < r2) continue;
            if (r1 == r2 && r2 == r3) ans += cnt[r1] * (cnt[r1] - 1) * (cnt[r1] - 2) / 6;
            else if (r1 == r2) ans += cnt[r1] * (cnt[r1] - 1) / 2 * cnt[r3];
            else if (r2 == r3) ans += cnt[r1] * cnt[r2] * (cnt[r2] - 1) / 2;
            else if (r1 == r3) ans += cnt[r1] * (cnt[r1] - 1) / 2 * cnt[r2];
            else ans += cnt[r1] * cnt[r2] * cnt[r3];
        }
        return ans;
    }
}
class Solution {
public:
    long long getTripletCount(vector<int>& arr, int d) {
        vector<long long> cnt(d, 0);
        for (int x : arr) cnt[((x % d) + d) % d]++;
        long long ans = 0;
        for (int r1 = 0; r1 < d; r1++) for (int r2 = r1; r2 < d; r2++) {
            int r3 = ((-(r1 + r2)) % d + d) % d;
            if (r3 < r2) continue;
            if (r1 == r2 && r2 == r3) ans += cnt[r1] * (cnt[r1] - 1) * (cnt[r1] - 2) / 6;
            else if (r1 == r2) ans += cnt[r1] * (cnt[r1] - 1) / 2 * cnt[r3];
            else if (r2 == r3) ans += cnt[r1] * cnt[r2] * (cnt[r2] - 1) / 2;
            else if (r1 == r3) ans += cnt[r1] * (cnt[r1] - 1) / 2 * cnt[r2];
            else ans += cnt[r1] * cnt[r2] * cnt[r3];
        }
        return ans;
    }
};

A company launches an initial public offering (IPO) where investors submit bids during a bidding window. Each bid is represented as [userId, numberOfShares, biddingPrice, timestamp]. After the bidding window closes, shares are allocated from the highest price downward until no shares remain. Allocation rules

  • If one bidder has the highest price, that bidder receives as many requested shares as possible.
  • If multiple bidders share the same highest price, allocate one share at a time in ascending timestamp order.
  • Once a bidder receives all requested shares, remove that bidder from the round-robin process.
  • Continue within the price group until either all bidders in that group are satisfied or no shares remain, then move to the next lower price. Return the user IDs of every bidder who receives no shares at all, sorted in ascending order. Function Description Complete getUnallottedUsers. getUnallottedUsers has the following parameters:
  • int[][] bids: each row is [userId, shares, price, timestamp]
  • int totalShares: the total number of shares available in the IPO Returns: int[] of user IDs that received no shares, sorted in ascending order.

Constraints

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ totalShares ≤ 10⁹
  • Each bid row contains exactly four integers: [userId, shares, price, timestamp].
  • timestamp values are strictly increasing in the original input order.
  • User IDs in the result must be sorted in ascending order.

Example 1

Input:

bids = [[1,5,7,0],[2,7,8,1],[3,7,7,2],[4,10,6,3]]
totalShares = 18

Output:

[4]

Explanation: User 2 has the highest bid price and receives 7 shares first. The remaining 11 shares go to the price-7 group containing users 1 and 3, allocated one share at a time by timestamp. User 1 receives all 5 requested shares, user 3 receives the remaining 6, and user 4 receives no shares.

Example 2

Input:

bids = [[1,2,5,0],[2,2,5,1],[3,1,4,2]]
totalShares = 2

Output:

[3]

Explanation: Users 1 and 2 tie for the highest price. The two available shares are distributed round-robin by timestamp, so each receives one share. The lower-priced bid from user 3 is never reached and that user is returned.

解法

按价格降序分组(同价按 timestamp 升序)。每组内：若组总需求 ≤ 剩余股，全部分配并扣除；否则按 round-robin(升序 timestamp)逐股分配直到耗尽。统计未获得任何股的用户。时间复杂度 O(N log N + totalShares)，可优化为 O(N log N)。

from typing import List
from collections import defaultdict

def getUnallottedUsers(bids: List[List[int]], totalShares: int) -> List[int]:
    groups = defaultdict(list)
    for uid, sh, pr, ts in bids:
        groups[pr].append([uid, sh, ts])
    allotted = set()
    for pr in sorted(groups.keys(), reverse=True):
        if totalShares == 0:
            break
        g = sorted(groups[pr], key=lambda x: x[2])
        total_need = sum(s for _, s, _ in g)
        if total_need <= totalShares:
            for u, _, _ in g:
                allotted.add(u)
            totalShares -= total_need
        else:
            active = list(range(len(g)))
            while totalShares > 0 and active:
                next_active = []
                for i in active:
                    if totalShares == 0: break
                    g[i][1] -= 1
                    totalShares -= 1
                    allotted.add(g[i][0])
                    if g[i][1] > 0:
                        next_active.append(i)
                active = next_active
    res = sorted(set(b[0] for b in bids) - allotted)
    return res
class Solution {
    int[] getUnallottedUsers(int[][] bids, int totalShares) {
        TreeMap<Integer, List<int[]>> groups = new TreeMap<>(Collections.reverseOrder());
        Set<Integer> allUsers = new HashSet<>();
        for (int[] b : bids) {
            groups.computeIfAbsent(b[2], k -> new ArrayList<>()).add(new int[]{b[0], b[1], b[3]});
            allUsers.add(b[0]);
        }
        Set<Integer> allotted = new HashSet<>();
        for (Map.Entry<Integer, List<int[]>> e : groups.entrySet()) {
            if (totalShares == 0) break;
            List<int[]> g = e.getValue();
            g.sort((a, b) -> a[2] - b[2]);
            long need = 0;
            for (int[] x : g) need += x[1];
            if (need <= totalShares) {
                for (int[] x : g) allotted.add(x[0]);
                totalShares -= need;
            } else {
                int[] rem = new int[g.size()];
                for (int i = 0; i < g.size(); i++) rem[i] = g.get(i)[1];
                while (totalShares > 0) {
                    boolean any = false;
                    for (int i = 0; i < g.size() && totalShares > 0; i++) {
                        if (rem[i] > 0) {
                            rem[i]--; totalShares--;
                            allotted.add(g.get(i)[0]);
                            any = true;
                        }
                    }
                    if (!any) break;
                }
            }
        }
        List<Integer> out = new ArrayList<>();
        for (int u : allUsers) if (!allotted.contains(u)) out.add(u);
        Collections.sort(out);
        int[] arr = new int[out.size()];
        for (int i = 0; i < out.size(); i++) arr[i] = out.get(i);
        return arr;
    }
}
class Solution {
public:
    vector<int> getUnallottedUsers(vector<vector<int>>& bids, int totalShares) {
        map<int, vector<vector<int>>, greater<int>> groups;
        set<int> allUsers;
        for (auto& b : bids) {
            groups[b[2]].push_back({b[0], b[1], b[3]});
            allUsers.insert(b[0]);
        }
        set<int> allotted;
        for (auto& [pr, g] : groups) {
            if (totalShares == 0) break;
            sort(g.begin(), g.end(), [](auto& a, auto& b) { return a[2] < b[2]; });
            long long need = 0;
            for (auto& x : g) need += x[1];
            if (need <= totalShares) {
                for (auto& x : g) allotted.insert(x[0]);
                totalShares -= (int) need;
            } else {
                vector<int> rem;
                for (auto& x : g) rem.push_back(x[1]);
                while (totalShares > 0) {
                    bool any = false;
                    for (size_t i = 0; i < g.size() && totalShares > 0; i++) {
                        if (rem[i] > 0) {
                            rem[i]--; totalShares--;
                            allotted.insert(g[i][0]);
                            any = true;
                        }
                    }
                    if (!any) break;
                }
            }
        }
        vector<int> out;
        for (int u : allUsers) if (!allotted.count(u)) out.push_back(u);
        sort(out.begin(), out.end());
        return out;
    }
};

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. You are given a string s consisting of lowercase English letters. You must choose a non-empty substring and perform the following operation on each character in that substring exactly once: replace it with the previous letter in the alphabet (e.g., b -> a, c -> b). Note that the previous letter of a is z. Return the lexicographically smallest string you can obtain after performing the operation once. I/O Input: one line string s Output: one line string, the lexicographically smallest result Constraints 1 ≤ len(s) ≤ 1e5 s contains only a to z Examples Input: cbabc Output: baabc Input: aaaa Output: zzzz Input: leetcode Output: kddsbncd Function Description Complete solveLexicographicallySmallestSubstringOperation. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Use the limits and requirements stated in the prompt.

Example 1

Input:

input = "cbabc"

Output:

["baabc"]

Explanation: The returned string must match the expected standard output for the sample input.

解法

贪心：找到第一个不是 'a' 的字符开始减 1，直到遇到 'a' 停止；若整串都是 'a'，则将最后一个字符变为 'z'。时间复杂度 O(n)。

from typing import List

def solveLexicographicallySmallestSubstringOperation(input: str) -> List[str]:
    s = input.strip()
    chars = list(s)
    if all(c == 'a' for c in chars):
        chars[-1] = 'z'
        return [''.join(chars)]
    started = False
    for i in range(len(chars)):
        if chars[i] != 'a':
            chars[i] = chr(ord(chars[i]) - 1)
            started = True
        elif started:
            break
    return [''.join(chars)]
class Solution {
    String[] solveLexicographicallySmallestSubstringOperation(String input) {
        char[] chars = input.trim().toCharArray();
        boolean allA = true;
        for (char c : chars) if (c != 'a') { allA = false; break; }
        if (allA) {
            chars[chars.length - 1] = 'z';
            return new String[]{new String(chars)};
        }
        boolean started = false;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != 'a') {
                chars[i] = (char) (chars[i] - 1);
                started = true;
            } else if (started) break;
        }
        return new String[]{new String(chars)};
    }
}
class Solution {
public:
    vector<string> solveLexicographicallySmallestSubstringOperation(string input) {
        string s = input;
        while (!s.empty() && isspace(s.back())) s.pop_back();
        bool allA = true;
        for (char c : s) if (c != 'a') { allA = false; break; }
        if (allA) {
            if (!s.empty()) s.back() = 'z';
            return {s};
        }
        bool started = false;
        for (char& c : s) {
            if (c != 'a') { c--; started = true; }
            else if (started) break;
        }
        return {s};
    }
};

The D. E. Shaw Group

The D. E. Shaw Group OA 真题，三语题解(Python / Java / C++)。

Akuna Capital

Akuna Capital 真实 OA 题库，编程 + Sequences + Probability。