Duolingo

01Construct New Array

See the Image Source section at the very bottom of the page for the original problem statement Once upon a time, there was an array of numbers, waiting to be transformed. The first element eagerly stepped forward, claiming its place at the beginning of a new array. But before anyone else could join, the last element leaped to the second spot, not wanting to be left behind. Then, the second element followed suit, and right after, the second-to-last element took its turn. This dance continued, with each element from the front and back of the original array taking turns to form a beautifully intertwined new array, until every number had found its place.

Constraints

1 ≤ numbers.length ≤ 10⁵
-10⁹ ≤ numbers[i] ≤ 10⁹

Example 1

Input:

numbers = [0, 4, 3, 2, 1]

Output:

[0, 1, 4, 2, 3]

Explanation: Following the rules above, we get the following sequence numbers[0], numbers[4], numbers[1], numbers[3], numbers[2] which results in [0, 1, 4, 2, 3]

Example 2

Input:

numbers = [-5, 4, 0, 3, 2, 2]

Output:

[-5, 2, 4, 2, 0, 3]

Explanation:

解法

双指针：l = 0, r = n - 1，交替取 numbers[l++] 和 numbers[r--] 填入新数组，直到 l > r。复杂度 O(n)，空间 O(n)。

from typing import List

def construct_new_array(numbers: List[int]) -> List[int]:
    res = []
    l, r = 0, len(numbers) - 1
    take_left = True
    while l <= r:
        if take_left:
            res.append(numbers[l]); l += 1
        else:
            res.append(numbers[r]); r -= 1
        take_left = not take_left
    return res

class Solution {
    int[] constructNewArray(int[] numbers) {
        int[] res = new int[numbers.length];
        int l = 0, r = numbers.length - 1, k = 0;
        boolean takeLeft = true;
        while (l <= r) {
            res[k++] = takeLeft ? numbers[l++] : numbers[r--];
            takeLeft = !takeLeft;
        }
        return res;
    }
}

class Solution {
public:
    vector<int> constructNewArray(vector<int>& numbers) {
        vector<int> res(numbers.size());
        int l = 0, r = numbers.size() - 1, k = 0;
        bool takeLeft = true;
        while (l <= r) {
            res[k++] = takeLeft ? numbers[l++] : numbers[r--];
            takeLeft = !takeLeft;
        }
        return res;
    }
};

02Longest Stable Transaction Period

See the Image Source section at the very bottom of the page for the original problem statement In a bustling financial world, you are the guardian of stability, keeping a close eye on daily transactions. Each day’s net transaction value is recorded in an array, and your mission is to uncover the longest period of calm in this sea of numbers. But there’s a catch — a period is only considered stable if the sum of transactions over consecutive days can be evenly divided by a special number, the stability factor, k. Your goal is to write a function that searches through these records, finds the longest stretch of days where this condition holds true, and returns the length of that stable period.

Example 1

Input:

transactions = [2, 3, 1, 4, 1, 5, 9]
k = 3

Output:

Explanation: The longest stable period can be formed by the subarray [3, 1, 4, 1], where the sum 3 + 1 + 4 + 1 = 9 is divisible by 3.

Example 2

Input:

transactions = [3]
k = 2

Output:

Explanation: The array has only one element which is not divisible by 2, hence there are no stable periods and the result is 0.

解法

前缀和取模。维护 (prefix_sum % k) -> 第一次出现位置。对每个 i，若 prefix[i] % k 曾在位置 j 出现，则 [j+1..i] 是合法子段，长度 i - j。初始放 {0: -1}。复杂度 O(n)，空间 O(k)。

from typing import List

def longest_stable_period(transactions: List[int], k: int) -> int:
    first = {0: -1}
    cur = 0
    ans = 0
    for i, x in enumerate(transactions):
        cur = (cur + x) % k
        if cur in first:
            ans = max(ans, i - first[cur])
        else:
            first[cur] = i
    return ans

import java.util.*;

class Solution {
    int longestStablePeriod(int[] transactions, int k) {
        Map<Long, Integer> first = new HashMap<>();
        first.put(0L, -1);
        long cur = 0;
        int ans = 0;
        for (int i = 0; i < transactions.length; i++) {
            cur = ((cur + transactions[i]) % k + k) % k;
            if (first.containsKey(cur)) ans = Math.max(ans, i - first.get(cur));
            else first.put(cur, i);
        }
        return ans;
    }
}

class Solution {
public:
    int longestStablePeriod(vector<int>& transactions, int k) {
        unordered_map<long long, int> first;
        first[0] = -1;
        long long cur = 0;
        int ans = 0;
        for (int i = 0; i < (int) transactions.size(); i++) {
            cur = ((cur + transactions[i]) % k + k) % k;
            auto it = first.find(cur);
            if (it != first.end()) ans = max(ans, i - it->second);
            else first[cur] = i;
        }
        return ans;
    }
};

03Replace Nth Consonant

See the Image Source section at the very bottom of the page for the original problem statement In a world of letters, there’s a secret mission hidden within a string of text. Your task is to find every nth consonant in the message and transform it into the next consonant in the alphabet, while preserving its original case. The journey of the consonants continues as 'b' becomes 'c', 'x' transforms into 'y', and when you reach 'z', it wraps back around to 'b' (or 'Z' to 'B'). Your goal is to follow this pattern, subtly shifting every nth consonant while leaving the rest of the message untouched, returning the newly crafted string when the job is done.

Example 1

Input:

message = "Codesignal"
n = 3

Output:

"CodeTignam"

Explanation: The consonants in "Codesignal" are "C-d-s-g-n-l". The third consonant is "s" which is replaced by "t". The sixth consonant is "l" which is replaced by "m". Thus, the resulting string is "CodeTignam".

解法

扫描字符串，维护辅音计数器。每遇辅音 +1；若计数 % n == 0，则替换为下一个辅音(跳过元音)，保留大小写。"下一个辅音" 函数：循环 +1 直到不是 aeiou。复杂度 O(|message|)。

def replace_consonant(message: str, n: int) -> str:
    vowels = set("aeiouAEIOU")
    def next_consonant(c):
        is_upper = c.isupper()
        x = c.lower()
        while True:
            x = chr((ord(x) - ord('a') + 1) % 26 + ord('a'))
            if x not in "aeiou":
                break
        return x.upper() if is_upper else x
    out = []
    cnt = 0
    for c in message:
        if c.isalpha() and c not in vowels:
            cnt += 1
            if cnt % n == 0:
                out.append(next_consonant(c))
                continue
        out.append(c)
    return "".join(out)

class Solution {
    String replaceConsonant(String message, int n) {
        StringBuilder out = new StringBuilder();
        int cnt = 0;
        for (char c : message.toCharArray()) {
            if (Character.isLetter(c) && !isVowel(c)) {
                cnt++;
                if (cnt % n == 0) { out.append(nextConsonant(c)); continue; }
            }
            out.append(c);
        }
        return out.toString();
    }
    private boolean isVowel(char c) { return "aeiouAEIOU".indexOf(c) >= 0; }
    private char nextConsonant(char c) {
        boolean upper = Character.isUpperCase(c);
        char x = Character.toLowerCase(c);
        do { x = (char) ((x - 'a' + 1) % 26 + 'a'); } while (isVowel(x));
        return upper ? Character.toUpperCase(x) : x;
    }
}

class Solution {
public:
    string replaceConsonant(string message, int n) {
        string out;
        int cnt = 0;
        auto isVowel = [](char c) { return string("aeiouAEIOU").find(c) != string::npos; };
        auto nextC = [&](char c) {
            bool upper = isupper(c);
            char x = tolower(c);
            do { x = (x - 'a' + 1) % 26 + 'a'; } while (isVowel(x));
            return upper ? (char) toupper(x) : x;
        };
        for (char c : message) {
            if (isalpha((unsigned char) c) && !isVowel(c)) {
                ++cnt;
                if (cnt % n == 0) { out += nextC(c); continue; }
            }
            out += c;
        }
        return out;
    }
};