A box has a contents string (e.g. "pcm" = pie, cookie, muffin) and a template string. Count how many (box, template) pairs mismatch — characters must form the same multiset, order doesn't matter, repetitions count.
Example: [["cm","mc"], ["ccm","mc"], ["pm","mc"], ["c","mc"]] → 3.
Constraints
- Each box has at most 10 items.
- At most 1000 boxes per call.
解法
对两个字符串排序(或比较 26 字母频次)判等，统计不匹配数。时间 O(N · K log K)，K ≤ 10。
def bakery_quality(boxes):
return sum(1 for b, t in boxes if sorted(b) != sorted(t))class Solution {
static int bakeryQuality(String[][] boxes) {
int cnt = 0;
for (String[] b : boxes) {
char[] a = b[0].toCharArray(); Arrays.sort(a);
char[] c = b[1].toCharArray(); Arrays.sort(c);
if (!Arrays.equals(a, c)) cnt++;
}
return cnt;
}
}int bakeryQuality(vector<vector<string>>& boxes) {
int cnt = 0;
for (auto& b : boxes) {
string a = b[0], t = b[1];
sort(a.begin(), a.end()); sort(t.begin(), t.end());
if (a != t) ++cnt;
}
return cnt;
}Given short_s and long_s, return the maximum number of consecutive occurrences of short_s inside long_s. Empty string → 0.
Example: short_s = "AB", long_s = "ABCABCABAB" → 2.
Constraints
0 ≤ len(short_s) < 100 ≤ len(long_s) < 10⁶
解法
匹配成功时按 k = len(short_s) 步长跳(延长当前连续段)，否则步长 1 并清零。维护最大值。复杂度 O(n)。
def find_repetitions(short_s, long_s):
if not short_s: return 0
s = len(short_s)
best = cur = 0
i = 0
while i <= len(long_s) - s:
if long_s[i:i+s] == short_s:
cur += 1
best = max(best, cur)
i += s
else:
cur = 0
i += 1
return bestclass Solution {
static int findRepetitions(String shortS, String longS) {
if (shortS.isEmpty()) return 0;
int s = shortS.length(), best = 0, cur = 0;
int i = 0;
while (i <= longS.length() - s) {
if (longS.regionMatches(i, shortS, 0, s)) {
cur++;
best = Math.max(best, cur);
i += s;
} else {
cur = 0;
i++;
}
}
return best;
}
}int findRepetitions(string shortS, string longS) {
if (shortS.empty()) return 0;
int s = shortS.size(), best = 0, cur = 0;
int i = 0;
while (i <= (int)longS.size() - s) {
if (longS.compare(i, s, shortS) == 0) {
++cur;
best = max(best, cur);
i += s;
} else {
cur = 0;
++i;
}
}
return best;
}Given daily prices A[N], you start with one unit of the asset and may hold at most one at a time. You can sell whenever you hold one and rebuy whenever you don't. Compute the maximum income; return the last 9 digits (mod 10⁹).
Example: A = [1, 2, 3, 3, 2, 1, 5] → 7.
Constraints
1 ≤ N ≤ 2000000 ≤ A[i] ≤ 10⁹
解法
把所有正的相邻差 max(0, A[i] - A[i-1]) 累加 —— 等价于每个局部峰卖出、每个局部谷买入的总收益。模 10⁹。复杂度 O(N)。
def max_historical_income(A):
profit = sum(max(0, A[i] - A[i-1]) for i in range(1, len(A)))
return profit % 10**9class Solution {
static long maxHistoricalIncome(int[] A) {
long MOD = 1_000_000_000L;
long profit = 0;
for (int i = 1; i < A.length; i++)
if (A[i] > A[i - 1]) profit += A[i] - A[i - 1];
return profit % MOD;
}
}long long maxHistoricalIncome(vector<int>& A) {
const long long MOD = 1'000'000'000LL;
long long profit = 0;
for (int i = 1; i < (int)A.size(); ++i)
if (A[i] > A[i - 1]) profit += A[i] - A[i - 1];
return profit % MOD;
}