Imagine you are creating an algorithm for currency trading. Now you have a prototype which handles trading of a single currency. Each day, it can sell or buy exactly one unit of the currency or do nothing.
You are given rates, an array of positive integers where rates[i] represents the currency price on the i-th day. You're also given strategy, an array of -1, 0s, and 1s, where strategy[i] represents what operation the algorithm should perform on the i-th day:
-1: buy0: hold1: sell
You're also given an integer k, which is guaranteed to be even.
In order to improve the algorithm's performance, you may change the strategy in the following way:
- Choose a range of exactly
kconsecutive elements. - Set elements of the first half of the chosen range to
0. - Set elements of the second half of the chosen range to
1.
Your task is to choose the range optimally to maximize the algorithm's total profit.
Example: rates=[3,2,1,4,2,8,3], strategy=[1,-1,-1,0,-1,1,0], k=4 → choose the window where the second half overlaps the highest prices.
解法
收益 = Σ rates[i] · strategy[i]。选长度 k 的窗口、前半改 0 后半改 1 后，贡献变化为 +Σ rates[r+half..r+k-1] − Σ rates[r..r+k-1] · strategy[r..r+k-1]。用两个前缀和让每个窗口 O(1) 计算。复杂度 O(n)。
def solution(rates, strategy, k):
n, half = len(rates), k // 2
base = sum(r * s for r, s in zip(rates, strategy))
pre_rs = [0] * (n + 1)
pre_r = [0] * (n + 1)
for i in range(n):
pre_rs[i+1] = pre_rs[i] + rates[i] * strategy[i]
pre_r[i+1] = pre_r[i] + rates[i]
best = float('-inf')
for l in range(n - k + 1):
best = max(best, -(pre_rs[l+k] - pre_rs[l]) + (pre_r[l+k] - pre_r[l+half]))
return base + bestclass Solution {
public long solution(int[] rates, int[] strategy, int k) {
int n = rates.length, half = k / 2;
long base = 0;
long[] preRs = new long[n + 1], preR = new long[n + 1];
for (int i = 0; i < n; i++) {
long rs = (long) rates[i] * strategy[i];
base += rs;
preRs[i + 1] = preRs[i] + rs;
preR[i + 1] = preR[i] + rates[i];
}
long best = Long.MIN_VALUE;
for (int l = 0; l + k <= n; l++) {
long sumRs = preRs[l + k] - preRs[l];
long sumR = preR[l + k] - preR[l + half];
best = Math.max(best, -sumRs + sumR);
}
return base + best;
}
}long long solution(vector<int>& rates, vector<int>& strategy, int k) {
int n = rates.size(), half = k / 2;
long long base = 0;
vector<long long> preRs(n + 1, 0), preR(n + 1, 0);
for (int i = 0; i < n; ++i) {
long long rs = (long long)rates[i] * strategy[i];
base += rs;
preRs[i + 1] = preRs[i] + rs;
preR[i + 1] = preR[i] + rates[i];
}
long long best = LLONG_MIN;
for (int l = 0; l + k <= n; ++l) {
long long sumRs = preRs[l + k] - preRs[l];
long long sumR = preR[l + k] - preR[l + half];
best = max(best, -sumRs + sumR);
}
return base + best;
}A robot responds to two commands, U or D, that tells it to move one step up (U) or one step down (D) on a vertical line.
You're given a string commands representing a series of U and D commands. After responding to all the commands in order, the robot will stop. Your task is to determine whether the robot will stop above or below its starting position:
- If the robot will stop above its starting position, return
"U". - If the robot will stop at its starting position, return an empty string
"". - If the robot will stop below its starting position, return
"D".
Example: commands="UUDDUU" → "U" (net = +2).
解法
数 U 和 D 比较即可，单次遍历。复杂度 O(n)。
def solution(commands):
net = commands.count('U') - commands.count('D')
return "U" if net > 0 else "D" if net < 0 else ""class Solution {
public String solution(String commands) {
int net = 0;
for (char c : commands.toCharArray()) net += (c == 'U' ? 1 : -1);
if (net > 0) return "U";
if (net < 0) return "D";
return "";
}
}string solution(string commands) {
int net = count(commands.begin(), commands.end(), 'U')
- count(commands.begin(), commands.end(), 'D');
if (net > 0) return "U";
if (net < 0) return "D";
return "";
}You are given a string word consisting of lowercase English letters, and a list of strings skeletons consisting of '-' characters and lowercase English letters. Every skeleton will always be the same length as word.
Your task is to return a list of skeletons that can form the given word. A skeleton can form a word if all '-' characters can be replaced with other characters taken from the same skeleton to make the string equal to the word. If no strings within skeletons can form the given word by doing this, return an empty list. The matching skeletons should be returned in the same order they appear in skeletons and the list of skeletons may not all be unique.
Example: word="hello", skeletons=["he-lo","he--o","-ell-","hello"] → ["he-lo","hello"].
解法
对每个骨架：非 - 的字母即「供给集」。每个位置 i 要么与 word[i] 严格相等，要么为 - 且 word[i] 在供给集中。复杂度 O(N · L)，N 为骨架数、L = len(word)。
def solution(word, skeletons):
out = []
for sk in skeletons:
if len(sk) != len(word): continue
avail = {c for c in sk if c != '-'}
if all((s == w) or (s == '-' and w in avail) for w, s in zip(word, sk)):
out.append(sk)
return outclass Solution {
public List<String> solution(String word, List<String> skeletons) {
int n = word.length();
List<String> out = new ArrayList<>();
for (String sk : skeletons) {
if (sk.length() != n) continue;
Set<Character> avail = new HashSet<>();
for (char c : sk.toCharArray()) if (c != '-') avail.add(c);
boolean ok = true;
for (int i = 0; i < n; i++) {
char s = sk.charAt(i), w = word.charAt(i);
if (s == '-') { if (!avail.contains(w)) { ok = false; break; } }
else if (s != w) { ok = false; break; }
}
if (ok) out.add(sk);
}
return out;
}
}vector<string> solution(string word, vector<string>& skeletons) {
int n = word.size();
vector<string> out;
for (auto& sk : skeletons) {
if ((int)sk.size() != n) continue;
unordered_set<char> avail;
for (char c : sk) if (c != '-') avail.insert(c);
bool ok = true;
for (int i = 0; i < n; ++i) {
if (sk[i] == '-') { if (!avail.count(word[i])) { ok = false; break; } }
else if (sk[i] != word[i]) { ok = false; break; }
}
if (ok) out.push_back(sk);
}
return out;
}