Given an array pref of length n, where each pref[i] is the sum of all arr[j] such that j != i. Reconstruct and return the original array arr.

Examples:

• pref = [2, 6, 4] -> arr = [4, 0, 2] (total = 6, arr[i] = 6 - pref[i])
• pref = [11, 9, 8] -> arr = [3, 5, 6] (total = (11+9+8)/(3-1) = 14)

解法

设 T = sum(arr)，则 sum(pref) = (n-1) · T，所以 T = sum(pref) / (n-1)，arr[i] = T - pref[i]。复杂度 O(n)。

def reconstruct(pref):
    n = len(pref)
    S = sum(pref) // (n - 1)
    return [S - p for p in pref]

class Solution {
    static long[] reconstruct(long[] pref) {
        int n = pref.length;
        long S = 0;
        for (long p : pref) S += p;
        S /= (n - 1);
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) arr[i] = S - pref[i];
        return arr;
    }
}

vector<long long> reconstruct(vector<long long>& pref) {
 int n = pref.size();
 long long S = 0;
 for (long long p : pref) S += p;
 S /= (n - 1);
 vector<long long> arr(n);
 for (int i = 0; i < n; i++) arr[i] = S - pref[i];
 return arr;
}

Given an array of integers arr and an integer k, find the maximum sum of a contiguous subarray of length at least k.

Examples:

• arr = [10, -2, 5], k = 2 -> 13
• arr = [-3, -2, 1, -6, -30], k = 2 -> -5

解法

前缀和加滞后最小值：在下标 ≤ r - k 上维护 minPref，对每个 r 候选答案 = pref[r] - minPref。复杂度 O(n)。

def max_subarray_at_least_k(arr, k):
    n = len(arr)
    pref = [0] * (n + 1)
    for i in range(n):
        pref[i+1] = pref[i] + arr[i]
    ans = float('-inf')
    min_pref = pref[0]
    for r in range(k, n + 1):
        ans = max(ans, pref[r] - min_pref)
        min_pref = min(min_pref, pref[r - k + 1])
    return ans

class Solution {
    static long maxSubarrayAtLeastK(int[] arr, int k) {
        int n = arr.length;
        long[] pref = new long[n + 1];
        for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
        long ans = Long.MIN_VALUE, minPref = pref[0];
        for (int r = k; r <= n; r++) {
            ans = Math.max(ans, pref[r] - minPref);
            minPref = Math.min(minPref, pref[r - k + 1]);
        }
        return ans;
    }
}

long long maxSubarrayAtLeastK(vector<int>& arr, int k) {
 int n = arr.size();
 vector<long long> pref(n + 1, 0);
 for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
 long long ans = LLONG_MIN, minPref = pref[0];
 for (int r = k; r <= n; r++) {
 ans = max(ans, pref[r] - minPref);
 minPref = min(minPref, pref[r - k + 1]);
 }
 return ans;
}

For an array of non-negative integers arr[], the prefix XOR at position i is pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]. Given the prefix XOR array pref, reconstruct and return the original array arr.

Example

pref = [2, 2, 5, 6]
arr[0] = pref[0] = 2
arr[1] = pref[0] ^ pref[1] = 2 ^ 2 = 0
arr[2] = pref[1] ^ pref[2] = 2 ^ 5 = 7
arr[3] = pref[2] ^ pref[3] = 5 ^ 6 = 3
Answer: [2, 0, 7, 3]

Constraints

• 1 <= n <= 10⁵
• 0 <= pref[i] <= 10⁹

解法

XOR 自反：由 pref[i] = pref[i-1] ^ arr[i] 得 arr[i] = pref[i-1] ^ pref[i](i ≥ 1)，arr[0] = pref[0]。复杂度 O(n)。

def get_original_array(pref):
    n = len(pref)
    arr = [pref[0]]
    for i in range(1, n):
        arr.append(pref[i - 1] ^ pref[i])
    return arr

class Solution {
    static int[] getOriginalArray(int[] pref) {
        int n = pref.length;
        int[] arr = new int[n];
        arr[0] = pref[0];
        for (int i = 1; i < n; i++) arr[i] = pref[i - 1] ^ pref[i];
        return arr;
    }
}

#include <vector>
using namespace std;

vector<int> getOriginalArray(vector<int>& pref) {
 int n = pref.size();
 vector<int> arr(n);
 arr[0] = pref[0];
 for (int i = 1; i < n; i++) arr[i] = pref[i - 1] ^ pref[i];
 return arr;
}

Given an array of integers arr, find the number of ways to split the entire array into two non-empty contiguous subarrays left and right such that the sum of elements in the left subarray is greater than the sum of elements in the right subarray.

Example

arr = [10, -5, 6]
Split 1: [10] | [-5, 6] -> left=10, right=1. left > right.
Split 2: [10, -5] | [6] -> left=5, right=6. left <= right.
Answer: 1

Constraints

• 2 <= n <= 10⁵
• -10⁴ <= arr[i] <= 10⁴

A palindrome reads the same forwards and backwards, like "mom". Modify a palindrome by changing exactly one character to another character within the ASCII range [a-z]. The goal is to ensure the new string fulfills the following criteria: It is not a palindrome. It is alphabetically lower than the original palindrome. It is the smallest possible string alphabetically that can be obtained by changing just one character. Return the new string, or "IMPOSSIBLE" if it is not feasible to create such a string. Function Description Complete the function breakPalindrome in the editor with the following parameter(s):

• string palindromeStr: the input string Returns string: the resulting string, or IMPOSSIBLE if one cannot be formed

Constraints

• 1 ≤ length of palindromeStr ≤ 1000
• palindromeStr is a palindrome
• palindromeStr contains only lowercase English letters

Example 1

Input:

palindromeStr = "aaabbaaa"

Output:

"aaaabaaa"

Explanation: Possible strings lower alphabetically than 'aaabbaaa' after one change are ['aaaabaaa', 'aaabaaaa'] 'aaaabaaa' is not a palindrome and is the lowest string that can be created from palindromeStr.

A string is a palindrome if the reverse of the string is the same as the original string. An analyst at HackerRank is tasked to analyze an array of n strings that consist of lowercase English characters. In one operation, the analyst chooses 4 integers, namely x, y, i, j such that 1 ≤ x, y ≤ n, 1 ≤ i ≤ length(arr[x]), 1 ≤ j ≤ length(arr[y]) and then swaps arr[x][i] and arr[y][j] using 1-based indexing. The analyst wishes to determine the maximum number of palindromic strings that can be obtained by performing the operation any number of times, possibly 0. Function Description Complete the function countPalindromes in the editor below. countPalindromes has the following parameter:

• string arr[n]: the strings to consider Returns int: the maximum number of palindromic strings possible

Implement a function called get_dict_value that takes two arguments: a dictionary called dict and a string called path. The path string represents the nested keys of the dictionary, separated by dots. The function should return the value at the specified path or None (the Python null value, not a string) if the path does not exist. Function Description Complete the function get_dict_value in the editor below. get_dict_value has the following parameters:

• obj: a Python dictionary
• string path: the path to the desired value if it exists Returns The value at the specified path, or None (the Python null value, not a string) if the path does not exist

Constraints

1 ≤ n(number of strings) ≤ 500

Example 1

Input:

obj = [["car"], [":"], ["wheels", ":", "2", "gears", ":", "5"]]
path = "car.gears"

Output:

5

Explanation: The function call get_dict_value(obj, "car.gears") should return 5.

Robots compete by score. While at least two robots remain, take the two

Constraints

The competition always uses the two currently highest scores.

Example 1

Input:

scores = [10,4,7,3]

Output:

2

Explanation: 10 and 7 leave 3, then 4 and 3 leave 1, then 3 and 1 leave 2. The last remaining robot has score 2.

Example 2

Input:

scores = [8,5,3]

Output:

0

Explanation: 8 and 5 leave 3, then the two 3s cancel.