登录
OAmaster

Two definitions follow: A binary string consists of 0s and/or 1s. For example, 01011, 1111, and 00 are binary strings. The prefix of a string is any of its substrings that include the beginning of the string. For example, the prefixes of 11010 are 1, 11, 110, 1101, and 11010. A non-empty binary string is good if the following two conditions are true: The number of 0s is equal to the number of 1s. For every prefix of the binary string, the number of 1s is not less than the number of 0s. For example, 11010 is not good because it does not have an equal number of 0s and 1s, but 110010 is good because it satisfies both conditions. A good string can contain multiple good substrings. If two consecutive substrings are good, then they can be swapped as long as the resulting string is still a good string. Given a good binary string, binString, perform zero or more swap operations on its adjacent good substrings such that the resulting string is the largest possible numeric value. Two substrings are adjacent if the last character of the first substring occurs exactly one index before the first character of the second substring. Function Description Complete the function largestGood in the editor. largestGood has the following parameter(s):

  • String binString: a binary string Returns String: the largest possible good binary string

解法

把字符串切成最小的"好子串"序列(前缀 1 计数 - 0 计数从 0 走到 0 的位置切)，然后对相邻可交换的子串按字典序降序排列即可。Greedy：sort 所有"原子"好子串 desc，concat。时间复杂度 O(n²) 切分 + O(k log k) 排序。

def largestGood(binString: str) -> str:
    pieces = []
    cur, bal = [], 0
    for c in binString:
        cur.append(c)
        bal += 1 if c == '1' else -1
        if bal == 0:
            pieces.append(''.join(cur))
            cur = []
    pieces.sort(reverse=True)
    return ''.join(pieces)
class Solution {
    String largestGood(String binString) {
        List<String> pieces = new ArrayList<>();
        StringBuilder cur = new StringBuilder();
        int bal = 0;
        for (char c : binString.toCharArray()) {
            cur.append(c);
            bal += c == '1' ? 1 : -1;
            if (bal == 0) { pieces.add(cur.toString()); cur.setLength(0); }
        }
        pieces.sort(Comparator.reverseOrder());
        return String.join("", pieces);
    }
}
class Solution {
public:
    string largestGood(string binString) {
        vector<string> pieces;
        string cur;
        int bal = 0;
        for (char c : binString) {
            cur += c;
            bal += c == '1' ? 1 : -1;
            if (bal == 0) { pieces.push_back(cur); cur.clear(); }
        }
        sort(pieces.rbegin(), pieces.rend());
        string res;
        for (auto& p : pieces) res += p;
        return res;
    }
};

Alex is given n piles of boxes of equal or unequal heights. In one step, Alex can remove any number of boxes from the pile which has the maximum height and try to make it equal to the one which is just lower than the maximum height of the stack. Determine the minimum number of steps required to make all of the piles equal in height. Function Description Complete the function pilesOfBoxes in the editor. pilesOfBoxes has the following parameter(s):

  • int boxesInPiles[n]: each boxesInPiles[i] represents the initial height of one pile Returns long: the minimum number of steps required

Example 1

Input:

boxesInPiles = [5, 2, 1]

Output:

3

Explanation: Initial State Step 1 Step 2 Step 3 In the first step, remove 3 boxes from boxesInPiles[0], and the new array is boxesInPiles' = [2, 2, 1]. Now reduce the two taller piles by 1 box each to match the height of the shortest pile. This takes 2 steps because each step is performed on only one pile. The final number of steps required is 3.

解法

排序后从大到小：每个不同的高度需要把所有比 min 高的桩降到这个高度，但题目每一步只能修一桩，且每步降到"下一个更低"的高度。所以总步数 = 排序后比最小值大的元素个数(即 n - count(min))。其实更精确：每个不同值的桩都要降一次到下一个更低，所以答案 = distinct heights count - 1 乘上... 实际正确做法：排序后，每个 i 处比最小值高的位置贡献 1 步。即答案 = n - count(min)。

from typing import List

def pilesOfBoxes(boxesInPiles: List[int]) -> int:
    m = min(boxesInPiles)
    return sum(1 for x in boxesInPiles if x > m)
class Solution {
    long pilesOfBoxes(int[] boxesInPiles) {
        int m = Integer.MAX_VALUE;
        for (int x : boxesInPiles) m = Math.min(m, x);
        long cnt = 0;
        for (int x : boxesInPiles) if (x > m) cnt++;
        return cnt;
    }
}
class Solution {
public:
    long long pilesOfBoxes(vector<int>& boxesInPiles) {
        int m = *min_element(boxesInPiles.begin(), boxesInPiles.end());
        long long cnt = 0;
        for (int x : boxesInPiles) if (x > m) cnt++;
        return cnt;
    }
};

The table below contains some reference values from coverting between integers (i.e. Arabic numerals) and Roman numerals: Given an integer, convert it to its Roman numeral equivalent. s Function Description Complete the function romanizer in the editor below. The function must return an array of strings that represent the integers as their Roman numeral equivalents. romanizer has the following parameter(s):

  • int numbers[n]: an array of integers Returns string[n]: an array of strings that represent the integers as their Roman numeral equivalents.

Example 1

Input:

numbers = [1, 49, 23]

Output:

["I", "XLIX", "XXIII"]

Explanation: Looking at the conversions above, 1 is represented as I (Capital I), 49 is 40 + 9, so XLIX, and 23 is XXIII. The return array is ['I', 'XLIX', 'XXIII'].

解法

LC 12 标准映射。按从大到小排列罗马数字对 (1000=M, 900=CM, ..., 1=I)，循环减去当前最大可减值并追加对应符号。时间复杂度 O(len)。

from typing import List

def romanizer(numbers: List[int]) -> List[str]:
    table = [(1000,'M'),(900,'CM'),(500,'D'),(400,'CD'),(100,'C'),(90,'XC'),
             (50,'L'),(40,'XL'),(10,'X'),(9,'IX'),(5,'V'),(4,'IV'),(1,'I')]
    res = []
    for n in numbers:
        s = []
        for v, sym in table:
            while n >= v:
                s.append(sym); n -= v
        res.append(''.join(s))
    return res
class Solution {
    String[] romanizer(int[] numbers) {
        int[] vals = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] syms = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        String[] res = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            int n = numbers[i];
            StringBuilder sb = new StringBuilder();
            for (int k = 0; k < vals.length; k++) {
                while (n >= vals[k]) { sb.append(syms[k]); n -= vals[k]; }
            }
            res[i] = sb.toString();
        }
        return res;
    }
}
class Solution {
public:
    vector<string> romanizer(vector<int>& numbers) {
        vector<pair<int, string>> table = {{1000,"M"},{900,"CM"},{500,"D"},{400,"CD"},{100,"C"},{90,"XC"},
                                          {50,"L"},{40,"XL"},{10,"X"},{9,"IX"},{5,"V"},{4,"IV"},{1,"I"}};
        vector<string> res;
        for (int n : numbers) {
            string s;
            for (auto& [v, sym] : table) while (n >= v) { s += sym; n -= v; }
            res.push_back(s);
        }
        return res;
    }
};

BNY Mellon

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

DTCC

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