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 Returnsstring: 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 bouquetint q: the cost of a type 2 bouquetstring s: the garden pattern as a binary string where0indicates rose and1indicates cosmos Returnsint: the maximum value of flower bouquets
Constraints
1 ≤ p, q ≤ 10001 ≤ |s| ≤ 100000
Example 1
Input:
p = 2
q = 3
s = "0001000"Output:
5Explanation: 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 ofnintegers representing the minimum cash-on-hand to produce theith productexpected[expected[0],...expected[n-1]]: an array ofnintegers, representing the expected cost to produce theith 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 everyi(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 bestimport 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;
}
};