Consider a string, S, that is a series of characters, each followed by its frequency as an integer. The string is not compressed correctly, so there may be multiple occurrences of the same character. A properly compressed string will consist of one instance of each character in alphabetical order followed by the total count of that character within the string. Example The string 'a3c9b2c1' has two instances where 'c' is followed by a count: once with 9 occurrences, and again with 1. It should be compressed to 'a3b2c10'. Function Description Complete the function betterCompression in the editor below. betterCompression has the following parameter:

• S: string: a compressed string Returns string: the properly compressed string

Constraints

• 1 ≤ size of S ≤ 100000
• 'a' ≤ characters in S ≤ 'z'
• 1 ≤ frequency of each character in S ≤ 1000

Example 1

Input:

S = "a3c9b2c1"

Output:

"a3b2c10"

Explanation: The string 'a3c9b2c1' has two instances where 'c' is followed by a count: once with 9 occurrences, and again with 1. It should be compressed to 'a3b2c10'.

解法

扫描字符串：识别 (字母, 数字串)，把数字累加到 26 桶里。最后按 'a'..'z' 顺序输出每个有计数的桶。时间 O(|S|)。

def better_compression(S: str) -> str:
    cnt = [0] * 26
    i = 0
    while i < len(S):
        c = S[i]
        i += 1
        num = 0
        while i < len(S) and S[i].isdigit():
            num = num * 10 + int(S[i])
            i += 1
        cnt[ord(c) - ord('a')] += num
    return "".join(f"{chr(ord('a') + i)}{cnt[i]}" for i in range(26) if cnt[i] > 0)

class Solution {
    public String betterCompression(String S) {
        long[] cnt = new long[26];
        int i = 0;
        while (i < S.length()) {
            char c = S.charAt(i++);
            long num = 0;
            while (i < S.length() && Character.isDigit(S.charAt(i))) { num = num * 10 + (S.charAt(i) - '0'); i++; }
            cnt[c - 'a'] += num;
        }
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < 26; j++) if (cnt[j] > 0) sb.append((char)('a' + j)).append(cnt[j]);
        return sb.toString();
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string betterCompression(string S) {
        vector<long long> cnt(26, 0);
        int i = 0;
        while (i < (int)S.size()) {
            char c = S[i++];
            long long num = 0;
            while (i < (int)S.size() && isdigit((unsigned char)S[i])) { num = num * 10 + (S[i] - '0'); i++; }
            cnt[c - 'a'] += num;
        }
        string out;
        for (int j = 0; j < 26; j++) if (cnt[j] > 0) out += char('a' + j) + to_string(cnt[j]);
        return out;
    }
};

A flower shop has only two types of flower bouquets: Type 1: This contains three roses and costs p dollars. Type 2: This contains one cosmos and one rose and costs q dollars. The flowers are grown in a single row. Consider the row as a one-dimensional array where each cell either contains a rose or a cosmos. For example, the image is based on the array 001101011, here 0 indicates rose, and 1 indicates cosmos. Any bouquet must be formed from consecutive flowers. For example, in a bouquet, the flower from consecutive indices (i, i+1, and i+2) in the array can be present, but not from non-consecutive indices (i and i+2). In the array shown, there are no bouquets of type 1, but 3 bouquets of type 2 can be created. Given a binary string representing the garden row, determine the maximum revenue possible. It is not necessary to use every flower. Function Description Complete the function flowerBouquets in the editor. flowerBouquets has three parameters:

• int p: the cost of a type 1 bouquet
• int q: the cost of a type 2 bouquet
• string s: the garden pattern as a binary string where 0 indicates rose and 1 indicates cosmos Returns int: the maximum value of flower bouquets

Constraints

• 1 ≤ p, q ≤ 1000
• 1 ≤ |s| ≤ 100000

Example 1

Input:

p = 2
q = 3
s = "0001000"

Output:

5

Explanation: There are two bouquets of three roses (Type 1) at indices (0, 1, 2), and (4, 5, 6) that sell for 2+2 = 4. There is one Type 1 bouquet (0, 1, 2) and one Type 2 bouquet at (3, 4). They sell for 2+3 = 5.

解法

DP dp[i] = 前 i 个花的最大收入。转移：dp[i] = dp[i-1] 不用此花；若 s[i-1]=='0' 且 i ≥ 3 且 s[i-3..i-1] 全 '0' → 用 type1 dp[i-3] + p；若 i ≥ 2 且 (s[i-2], s[i-1]) 包含一个 0 一个 1(即 "01" 或 "10")→ 用 type2 dp[i-2] + q。时间 O(n)。

def flower_bouquets(p: int, q: int, s: str) -> int:
    n = len(s)
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i - 1]
        if i >= 3 and s[i - 1] == '0' and s[i - 2] == '0' and s[i - 3] == '0':
            dp[i] = max(dp[i], dp[i - 3] + p)
        if i >= 2 and ((s[i - 1] == '0' and s[i - 2] == '1') or (s[i - 1] == '1' and s[i - 2] == '0')):
            dp[i] = max(dp[i], dp[i - 2] + q)
    return dp[n]

class Solution {
    public int flowerBouquets(int p, int q, String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            if (i >= 3 && s.charAt(i - 1) == '0' && s.charAt(i - 2) == '0' && s.charAt(i - 3) == '0')
                dp[i] = Math.max(dp[i], dp[i - 3] + p);
            if (i >= 2 && ((s.charAt(i - 1) == '0' && s.charAt(i - 2) == '1') || (s.charAt(i - 1) == '1' && s.charAt(i - 2) == '0')))
                dp[i] = Math.max(dp[i], dp[i - 2] + q);
        }
        return dp[n];
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int flowerBouquets(int p, int q, string s) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            if (i >= 3 && s[i - 1] == '0' && s[i - 2] == '0' && s[i - 3] == '0')
                dp[i] = max(dp[i], dp[i - 3] + p);
            if (i >= 2 && ((s[i - 1] == '0' && s[i - 2] == '1') || (s[i - 1] == '1' && s[i - 2] == '0')))
                dp[i] = max(dp[i], dp[i - 2] + q);
        }
        return dp[n];
    }
};

Source image will be included in next update :) Acme Corp has a number of products that need to be manufactured. However, careful planning must take place before production begins. For each product there is a worst-case cost and an expected cost. Before starting a project, Acme must have at least enough cash on hand to pay the worst-case cost for each product. If every product is produced at expected cost, determine the minimum beginning cash requirement to get all products produced. Products can be produced in any order. Function Description Complete the function planProduction in the editor. planProduction has the following parameter(s):

• worstCase[worstCase[0],...worstCase[n-1]]: an array of n integers representing the minimum cash-on-hand to produce the ith product
• expected[expected[0],...expected[n-1]]: an array of n integers, representing the expected cost to produce the ith product. Returns int: the minimum beginning cash requirement to get all products produced

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ worstCase[i] ≤ 10⁵
• 1 ≤ expected[i] ≤ 10⁵
• It is guaranteed that expected[i] ≤ worstCase[i] for every i (0 ≤ i

解法

按 worstCase − expected 升序排(差额小的先做，预算压力最大但能立刻补差额回到位)。初始 X = max_i(worstCase[i] + 累计 expected before i)。时间 O(n log n)。

from typing import List

def plan_production(worst_case: List[int], expected: List[int]) -> int:
    n = len(worst_case)
    order = sorted(range(n), key=lambda i: worst_case[i] - expected[i])
    cum = 0
    best = 0
    for i in order:
        best = max(best, worst_case[i] + cum)
        cum += expected[i]
    return best

import java.util.*;

class Solution {
    public long planProduction(int[] worstCase, int[] expected) {
        int n = worstCase.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> (worstCase[a] - expected[a]) - (worstCase[b] - expected[b]));
        long cum = 0, best = 0;
        for (int i : order) {
            best = Math.max(best, (long) worstCase[i] + cum);
            cum += expected[i];
        }
        return best;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long planProduction(vector<int>& worstCase, vector<int>& expected) {
        int n = worstCase.size();
        vector<int> order(n);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) { return (worstCase[a] - expected[a]) < (worstCase[b] - expected[b]); });
        long long cum = 0, best = 0;
        for (int i : order) {
            best = max(best, (long long) worstCase[i] + cum);
            cum += expected[i];
        }
        return best;
    }
};

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

Constraints

• 1 ≤ numbers.length ≤ 10⁴
• 1 ≤ numbers[i] ≤ 3999

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'].

Source image will be included in next update :) In a k-means clustering problem, a dataset contains n data points, where nth data point is represented by the feature vector location[i]. The goal is to create k clusters, where the cluster centers or the cluster centroids can be placed at any point in the feature space. The overall quality of the clustering is measured by the maximum distance between any data point and its nearest cluster center. The best possible quality is achieved by optimally placing the cluster centers to minimize this maximum distance. Determine this maximum distance between any data point and its nearest cluster center. Note: The distance between two feature points x and y is defined as |x-y|, where |x| denotes the absolute value of x. Function Description Complete the function getMaximumDistance in the editor below. getMaximumDistance takes the following parameters:

• int location[n]: the feature locations of all the data points
• int k: the number of clusters Returns int: the maximum distance between any data point and its nearest cluster center by optimally placing the k clusters

Constraints

• 1 ≤ n ≤ 10⁵ <

Example 1

Input:

location = [4, 1, 6, 7, 2]
k = 2

Output:

2

Explanation: The maximum of all distances is 2.