Nvidia

01Reconstruct Array from Prefix-Skip Sum

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

02Maximum Subarray of Size at Least K

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

03Reconstruct Array from Prefix XOR

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

Pro 会员

解锁剩余 5 道 OA 真题

开通后立即解锁完整题面 + Python / Java / C++ 三语题解。全站 165 家公司 · 1000+ 道 OA · 月度更新。

开通会员已是会员，去登录