登录
OAmaster

There are n bricks arranged in a row at positions numbered from 1 through n, inclusive. There is an array, newtons[n], that contains an integer indicating the number of newtons required to smash a brick. (A newton is a unit of force.) There are two hammers, one big and one small. The big hammer can smash any brick with one blow. The small hammer reduces the newtons required by 1 for each blow to a brick. For example, a brick requires 3 newtons of force. It will take 1 blow with the big hammer, or 3 blows with the small hammer to smash it. There is a limit to how many times the big hammer can be used. Determine 3 values: the minimum number of blows to smash all the bricks the 1-based indices of the bricks smashed by the big hammer, sorted ascending the 1-based indices of the bricks smashed by the small hammer, sorted ascending Return the values as a 2-dimensional integer array, [[total hits], [big hammer hits], [small hammer hits]]. If a hammer is not used, its index array should be [-1]. Function Description Complete the function breakTheBricks in the editor below. breakTheBricks has the following parameters: int bigHits: the maximum blows with the big hammer int newtons[n]: an array of distinct integers representing newtons required to smash each brick Returns long[[1], [p][q]]: IN THE FORM [[total hits], [sorted indices for big hammer hits], [sorted indices for small hammer hits]]

Constraints

  • 1 ≤ n ≤ 2x10⁵
  • 0 ≤ bigHits ≤ 2x10⁵
  • 1 ≤ newtons[n] ≤ 10⁹

Example 1

Input:

bigHits = 0
newtons = [2]

Output:

[[2], [-1], [1]]

Explanation: The big hammer cannot be used. The small hammer takes 2 blows to smash the single brick at index 1. The return array is [[2], [-1], [1]].

Example 2

Input:

bigHits = 4
newtons = [3, 2, 5, 4, 6, 7, 9]

Output:

[[13], [3, 5, 6, 7], [1, 2, 4]]

Explanation: In this case, it is best to use the big hammer on bricks at sorted indices [3, 5, 6, 7] using 4 hits to smash them all. The small hammer is used on sorted indices [1, 2, 4] which have newtons of 3, 2, and 4. It takes a total of 3 + 2 + 4 = 9 hits with the small hammer. The total blows required = 4 + 9 = 13. The return array is [[13], [3, 5, 6, 7], [1, 2, 4]].

Example 3

Input:

bigHits = 9
newtons = [7, 9, 3, 2, 5, 8, 4, 6]

Output:

[[8], [1, 2, 3, 4, 5, 6, 7, 8], [-1]]

Explanation: There are enough bigHits available to smash all of the bricks with the large hammer. The returned array is [[8], [1, 2, 3, 4, 5, 6, 7, 8], [-1]].

Example 4

Input:

bigHits = 0
newtons = [10000000, 100000000, 1000000000]

Output:

[[1110000000], [-1], [1, 2, 3]]

Explanation: Since bigHits = 0, the big hammer cannot be used. The total hits required is the sum of the newtons array, one hit with a small hammer for each newton. The returned arr is [[1110000000], [-1], [1, 2, 3]].

解法

大锤每用 1 次省下 (newtons[i] − 1) 次小锤，故优先把大锤用在最大 newtons 的砖上。按 newtons 降序排，取前 min(bigHits, n) 个用大锤，其余用小锤。最后按 1-based 原索引升序输出。时间 O(n log n)。

from typing import List

def break_the_bricks(big_hits: int, newtons: List[int]):
    n = len(newtons)
    order = sorted(range(n), key=lambda i: -newtons[i])
    use_big = sorted(order[:min(big_hits, n)])
    use_small = sorted(order[min(big_hits, n):])
    total = len(use_big) + sum(newtons[i] for i in use_small)
    big_idx = [i + 1 for i in use_big] if use_big else [-1]
    small_idx = [i + 1 for i in use_small] if use_small else [-1]
    return [[total], big_idx, small_idx]
import java.util.*;

class Solution {
    public List<List<Long>> breakTheBricks(int bigHits, int[] newtons) {
        int n = newtons.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> newtons[b] - newtons[a]);
        int kBig = Math.min(bigHits, n);
        List<Integer> big = new ArrayList<>(), small = new ArrayList<>();
        for (int i = 0; i < kBig; i++) big.add(order[i] + 1);
        for (int i = kBig; i < n; i++) small.add(order[i] + 1);
        Collections.sort(big); Collections.sort(small);
        long total = big.size();
        for (int idx : small) total += newtons[idx - 1];
        List<List<Long>> out = new ArrayList<>();
        out.add(List.of(total));
        out.add(big.isEmpty() ? List.of(-1L) : big.stream().map(Long::valueOf).toList());
        out.add(small.isEmpty() ? List.of(-1L) : small.stream().map(Long::valueOf).toList());
        return out;
    }
}
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<long long>> breakTheBricks(int bigHits, vector<int>& newtons) {
        int n = newtons.size();
        vector<int> order(n);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) { return newtons[a] > newtons[b]; });
        int kBig = min(bigHits, n);
        vector<long long> big, small;
        for (int i = 0; i < kBig; i++) big.push_back(order[i] + 1);
        for (int i = kBig; i < n; i++) small.push_back(order[i] + 1);
        sort(big.begin(), big.end()); sort(small.begin(), small.end());
        long long total = big.size();
        for (auto idx : small) total += newtons[idx - 1];
        vector<vector<long long>> out;
        out.push_back({total});
        out.push_back(big.empty() ? vector<long long>{-1} : big);
        out.push_back(small.empty() ? vector<long long>{-1} : small);
        return out;
    }
};

A clothing company wants to start a new line of clothing made from recycled clothes. The company wants this line to consist only of words formed from letters 'a' to 'z'. The creative team is facing challenges as they need to use a similar patch multiple times to achieve the desired design. To address this, the product team needs to find the sequence in which they should use the patch to get the desired words on the clothing. Input: The first line consists of a string patch, representing the patch. The second line consists of a string designerWords, representing the words to be printed on the clothing. Output: Print N space-separated integers indicating the sequence in which the patch should be used to obtain the desired words. If there is no possible way, then print -1. Note: If multiple possible sequences exist, print the smallest permutation. Function Description Complete the function getPatchSequence in the editor. getPatchSequence has the following parameters:

    1. String patch: a string representing the patch
    1. String designerWords: a string representing the words to be printed Returns int[]: an array of integers indicating the sequence in which the patch should be used, or an array with a single element -1 if it's not possible

Example 1

Input:

patch = "ab"
designerWords = "aab"

Output:

[0, 1]

Explanation: The patch needs to be used in the following way to create the desired word: Place the first patch at index 0 to get "ab". Place the second patch at index 1 to form "aab". The requirement states that the second patch 'b' of the first patch overlaps with 'a' of the second patch.

Example 2

Input:

patch = "yz"
designerWords = "yzzz"

Output:

[2, 1, 0]

Explanation: :)

解法

每次贴 patch 在某个 0-indexed 起点 i：patch 完整覆盖 [i, i+|patch|−1]，要求与 designerWords 在该区间字符匹配(视已经写入的字符为约束)。贪心从左到右扫 designerWords，找首个未被覆盖位置 j，必须有起点 i 使 i ≤ j ≤ i+|patch|−1 且 patch[j-i] == designerWords[j]，并且 patch 全段与 designerWords 完全相同(因为最终要求精确为 designerWords)。我们要求最小排列：把每个起点 i 按发现顺序加入序列，最后按 i 升序。"smallest permutation" 指方案中起点序列字典序最小——枚举可行起点集合，按字典序最小排列。简洁实现：穷举 patch 在 designerWords 中所有匹配起点 i(要求 designerWords[i:i+|patch|] == patch)，然后选一个最小覆盖集合(区间覆盖贪心)，按位置升序。若无法覆盖整个 designerWords 返回 [-1]。

from typing import List

def get_patch_sequence(patch: str, designer_words: str) -> List[int]:
    p, w = len(patch), len(designer_words)
    # collect all valid start positions
    starts = [i for i in range(w - p + 1) if designer_words[i:i + p] == patch]
    if not starts:
        return [-1]
    # greedy interval cover [0, w-1]
    chosen: List[int] = []
    covered = 0
    i = 0
    while covered < w:
        # pick farthest reach with start <= covered
        best = -1
        while i < len(starts) and starts[i] <= covered:
            best = starts[i]
            i += 1
        if best == -1:
            return [-1]
        chosen.append(best)
        covered = best + p
    return sorted(chosen)
import java.util.*;

class Solution {
    public int[] getPatchSequence(String patch, String designerWords) {
        int p = patch.length(), w = designerWords.length();
        List<Integer> starts = new ArrayList<>();
        for (int i = 0; i + p <= w; i++) if (designerWords.regionMatches(i, patch, 0, p)) starts.add(i);
        if (starts.isEmpty()) return new int[]{-1};
        List<Integer> chosen = new ArrayList<>();
        int covered = 0, idx = 0;
        while (covered < w) {
            int best = -1;
            while (idx < starts.size() && starts.get(idx) <= covered) { best = starts.get(idx); idx++; }
            if (best == -1) return new int[]{-1};
            chosen.add(best);
            covered = best + p;
        }
        Collections.sort(chosen);
        int[] out = new int[chosen.size()];
        for (int i = 0; i < chosen.size(); i++) out[i] = chosen.get(i);
        return out;
    }
}
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> getPatchSequence(string patch, string designerWords) {
        int p = patch.size(), w = designerWords.size();
        vector<int> starts;
        for (int i = 0; i + p <= w; i++) if (designerWords.compare(i, p, patch) == 0) starts.push_back(i);
        if (starts.empty()) return {-1};
        vector<int> chosen;
        int covered = 0, idx = 0;
        while (covered < w) {
            int best = -1;
            while (idx < (int)starts.size() && starts[idx] <= covered) { best = starts[idx]; idx++; }
            if (best == -1) return {-1};
            chosen.push_back(best);
            covered = best + p;
        }
        sort(chosen.begin(), chosen.end());
        return chosen;
    }
};

Given two strings, determine the number of times the first one appears as a subsequence in the second one. A subsequence is created by eliminating any number of characters from a string (possibly 0) without changing the order of the characters retained. Function Description Complete the function getSubsequenceCount in the editor below. getSubsequenceCount has the following parameters: string s1: the first string, which always has a length of 3 string s2: the second string Returns int: the number of times s1 appears as a subsequence in s2

Constraints

  • length of s1 = 3
  • 1 ≤ length of s2 ≤ 5*10⁵
  • s1 and s2 consist of uppercase English letters, A-Z.

Example 1

Input:

s1 = "HRW"
s2 = "HERHRWS"

Output:

3

Explanation: "HRW" appears as a subsequence in "HERHRWS" 3 times at positions (1, 3, 6), (1, 5, 6), and (4, 5, 6). Therefore, the answer is 3.

Example 2

Input:

s1 = "ELO"
s2 = "HELLOWORLD"

Output:

4

Explanation: "ELO" appears as a subsequence in "HELLOWORLD" 4 times at positions (2, 3, 5), (2, 3, 7), (2, 4, 5), and (2, 4, 7). Therefore, the answer is 4.

Example 3

Input:

s1 = "ABC"
s2 = "ABCBABC"

Output:

5

Explanation: The string s1 appears 5 times as a subsequence in s2 at 1-indexed positions of (1, 2, 3), (1, 2, 7), (1, 4, 7), (1, 6, 7) and (5, 6, 7). So, the answer turns out to be .

解法

经典 DP：dp[i][j] = s2 前 i 个字符里 s1 前 j 个字符作为子序列的出现次数。dp[i][j] = dp[i-1][j] + (s1[j-1]==s2[i-1] ? dp[i-1][j-1] : 0)。这里 |s1|=3，状态压成 3 个变量。时间 O(|s2|)。

def get_subsequence_count(s1: str, s2: str) -> int:
    a, b, c = 0, 0, 0  # dp for prefixes of length 1, 2, 3
    for ch in s2:
        if ch == s1[2]:
            c += b
        if ch == s1[1]:
            b += a
        if ch == s1[0]:
            a += 1
    return c
class Solution {
    public long getSubsequenceCount(String s1, String s2) {
        long a = 0, b = 0, c = 0;
        for (char ch : s2.toCharArray()) {
            if (ch == s1.charAt(2)) c += b;
            if (ch == s1.charAt(1)) b += a;
            if (ch == s1.charAt(0)) a += 1;
        }
        return c;
    }
}
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long getSubsequenceCount(string s1, string s2) {
        long long a = 0, b = 0, c = 0;
        for (char ch : s2) {
            if (ch == s1[2]) c += b;
            if (ch == s1[1]) b += a;
            if (ch == s1[0]) a += 1;
        }
        return c;
    }
};

JPMorgan Chase

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

Blackrock

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