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: buy
• 0: hold
• 1: 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:

1. Choose a range of exactly k consecutive elements.
2. Set elements of the first half of the chosen range to 0.
3. 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 + best

class 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 out

class 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;
}

A spy agency has intercepted fragments of a secret code. Each fragment is represented as a positive integer in an array called fragments. Intelligence suggests that the complete access code is a specific number called accessCode.

Your mission is to determine how many different ways the fragments can be paired to form the complete access code. The agency's cryptography rules state that:

• When fragments are combined, they are simply placed next to each other (not added mathematically).
• Each specific pair of fragments (by position in the array) counts as a unique combination.
• The fragments can be used in any order, but each fragment position can only be used once in a combination.

Example: fragments=[1, 212, 12, 12], accessCode=1212 → 3.

You are given a memory array of 0s and 1s (length divisible by 8) representing bits of memory. Each 0 is a free unit and each 1 is occupied. You then process a list of queries. Each query is one of:

• [0, sz] — alloc sz: find the leftmost free contiguous block of length sz whose starting index is divisible by 8. If found, mark those units as 1, assign a new ID equal to (number of previous successful allocs), and return the starting index. Otherwise return -1.
• [1, id] — erase id: if a block with this ID exists, free its units and return its length. Otherwise return -1.

Return the array of results.

Example: memory=[0,1,0,0,0,1,1,0,0,0,0,1,1,1,1] (length 15 → assume 16 with trailing 0 per spec), queries=[[0,2],[0,1],[0,1],[1,1],[0,3],[1,4],[0,4]] → [8, 0, -1, 2, 8, -1, -1].

Constraints

8 ≤ memory.length ≤ 320, 2 ≤ queries.length ≤ 300.

You are moderating a newspaper page. Inputs:

• paragraphs: array of paragraphs, where each paragraph is an array of words.
• aligns: array of per-paragraph alignment flags, each either "LEFT" or "RIGHT".
• width: max characters allowed on one output line.

Produce the page as follows:

• For each paragraph, greedily pack as many words as fit into a line of length ≤ width, separated by single spaces; overflow words go to the next line.
• Pad each line to exactly width characters: when aligns[i] == "LEFT", extra spaces go to the end (trailing); when aligns[i] == "RIGHT", extra spaces go to the beginning (leading).
• Surround the entire output with a * border: a top and bottom row of width + 2 asterisks, and a single * at the start and end of every content line.

Example: paragraphs = [["hello", "world"], ["How", "areYou", "doing"], ["Please look", "and align", "to right"]], aligns = ["LEFT", "RIGHT", "RIGHT"], width = 16.

[
 "******************",
 "*hello world *",
 "*How areYou doing*",
 "* Please look*",
 "* and align*",
 "* to right*",
 "******************"
]

Constraints

• 1 ≤ paragraphs.length ≤ 50
• aligns.length == paragraphs.length
• 5 ≤ width ≤ 100

Q1. Spiders / Chickens / Cows — 520 Legs

You walk into a barn and see a collection of spiders, chickens, and cows. You notice that there are 520 legs in total. The number of chickens is twice the number of cows and the number of spiders is twice the number of chickens. Compute the number of spiders.

Answer: 52.