A data analyst is given an array representing data for n days. The analyst performs k updates on the data, where each update is of the form [l, r]. This indicates that the elements of the array from index l to index r (inclusive) are negated.
Given the initial data array and k updates, return the final data array after all updates. Note: 1-based indexing is used.
Example
data = [1, 2, 3, 4, 5], updates = [[1, 3], [2, 4]]
After [1,3]: [-1, -2, -3, 4, 5]
After [2,4]: [-1, 2, 3, -4, 5]
Answer: [-1, 2, 3, -4, 5]Constraints
1 <= n, k <= 10⁶|data[i]| <= 10⁹
解法
XOR 翻转的差分：每次更新 [l,r] 时翻转 l-1 与 r 处的奇偶位。一次扫描，按当前 XOR 奇偶决定是否取反。复杂度 O(n + k)。
def get_final_data(data: list[int], updates: list[list[int]]) -> list[int]:
n = len(data)
flip = [0] * (n + 1)
for l, r in updates:
flip[l - 1] ^= 1
flip[r] ^= 1
cur = 0
out = []
for i in range(n):
cur ^= flip[i]
out.append(-data[i] if cur else data[i])
return outclass Solution {
static long[] getFinalData(long[] data, int[][] updates) {
int n = data.length;
int[] flip = new int[n + 1];
for (int[] u : updates) {
flip[u[0] - 1] ^= 1;
flip[u[1]] ^= 1;
}
long[] out = new long[n];
int cur = 0;
for (int i = 0; i < n; i++) {
cur ^= flip[i];
out[i] = cur == 1 ? -data[i] : data[i];
}
return out;
}
}#include <vector>
using namespace std;
vector<long long> getFinalData(vector<long long>& data, vector<vector<int>>& updates) {
int n = data.size();
vector<int> flip(n + 1, 0);
for (auto& u : updates) {
flip[u[0] - 1] ^= 1;
flip[u[1]] ^= 1;
}
vector<long long> out(n);
int cur = 0;
for (int i = 0; i < n; i++) {
cur ^= flip[i];
out[i] = cur ? -data[i] : data[i];
}
return out;
}You are given a computer network with n servers numbered from 1. Each server has a security value sec[i] (positive or negative). A hacker starts at one of these servers and jumps through the network. From node x, the hacker can jump to node (x + k). If (x + k) exceeds n, the hacker's attack ends. The hacker's goal is to maximize the sum of the security values of the compromised servers (initially 0 with 0 servers).
Choose the optimal starting node and return the maximum security value sum.
Example
sec = [2, -3, 5, -1, 4], k = 2
Start 0: visit 0,2,4 -> running sums 2, 7, 11; best 11.
Start 1: visit 1,3 -> running sums -3, -4; best 0.
Answer: 11解法
数组按步长 k 分成 k 条独立链。对每个起始偏移，从 start 起按步长 k 跑 Kadane 风格的最大前缀和，整体取最大(全负则取 0)。复杂度 O(n)。
def gain_max_value(sec: list[int], k: int) -> int:
n = len(sec)
best = 0
for start in range(k):
cur = local_best = 0
i = start
while i < n:
cur += sec[i]
if cur > local_best: local_best = cur
i += k
if local_best > best: best = local_best
return bestclass Solution {
static long gainMaxValue(int[] sec, int k) {
int n = sec.length;
long best = 0;
for (int start = 0; start < k; start++) {
long cur = 0, localBest = 0;
for (int i = start; i < n; i += k) {
cur += sec[i];
if (cur > localBest) localBest = cur;
}
if (localBest > best) best = localBest;
}
return best;
}
}#include <vector>
using namespace std;
long long gainMaxValue(vector<int>& sec, int k) {
int n = sec.size();
long long best = 0;
for (int start = 0; start < k; start++) {
long long cur = 0, localBest = 0;
for (int i = start; i < n; i += k) {
cur += sec[i];
if (cur > localBest) localBest = cur;
}
if (localBest > best) best = localBest;
}
return best;
}Signal filtering based on frequency is essential to minimize noise outside the desired frequency range. Filters can be combined such that only frequencies within the permissible range of all filters can pass through.
Given n signal frequencies and a sequence of m filters with frequency ranges [x, y] (inclusive), determine how many signals will pass through all the filters. There will be a single common range where all filters overlap.
Example
frequencies = [1, 5, 7, 9, 12], filterRanges = [[2, 10], [4, 8]]
Common range = [max(2,4), min(10,8)] = [4, 8]
Pass: 5, 7. Answer: 2.解法
交集区间 = [max(左端), min(右端)]；若区间反转则返回 0，否则统计 [lo, hi] 范围内的频次。复杂度 O(n + m)。
def count_signals(frequencies: list[int], filterRanges: list[list[int]]) -> int:
lo = max(r[0] for r in filterRanges)
hi = min(r[1] for r in filterRanges)
if lo > hi: return 0
return sum(1 for f in frequencies if lo <= f <= hi)class Solution {
static int countSignals(int[] frequencies, int[][] filterRanges) {
int lo = Integer.MIN_VALUE, hi = Integer.MAX_VALUE;
for (int[] r : filterRanges) {
lo = Math.max(lo, r[0]);
hi = Math.min(hi, r[1]);
}
if (lo > hi) return 0;
int cnt = 0;
for (int f : frequencies) if (f >= lo && f <= hi) cnt++;
return cnt;
}
}#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int countSignals(vector<int>& frequencies, vector<vector<int>>& filterRanges) {
int lo = INT_MIN, hi = INT_MAX;
for (auto& r : filterRanges) {
lo = max(lo, r[0]);
hi = min(hi, r[1]);
}
if (lo > hi) return 0;
int cnt = 0;
for (int f : frequencies) if (f >= lo && f <= hi) cnt++;
return cnt;
}