三段式数组 II 给你一个长度为 n 的整数数组 nums。 三段式子数组 是一个连续子数组 nums[l…r]（满足 0 <= l < r < n），并且存在下标 l < p < q < r，使得： nums[l…p] 严格 递增， nums[p…q] 严格 递减， nums[q…r] 严格 递增。 请你从数组 nums 的所有三段式子数组中找出和最大的那个，并返回其 最大 和。 提示: $4 <= n = nums.length <= 10^5$ $-10^9 <= nums[i] <= 10^9$ 保证至少存在一个三段式子数组。 思路 由于l < p < q < r, $p$ 是第一段的终点和第二段的起点，$q$ 是第二段的终点和第三段的起点，我们可以通过预处理和线性扫描来解决。 preSum[i]: 以 $i$ 结尾且满足“严格递增”的最大子数组和。 条件：必须包含 $nums[i]$ 和 $nums[i-1]$。 ...
将数组分成最小总代价的子数组 II 给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个 正 整数 k 和 dist 。 一个数组的 代价 是数组中的 第一个 元素。比方说，[1,2,3] 的代价为 1 ，[3,4,1] 的代价为 3 。 你需要将 nums 分割成 k 个 连续且互不相交 的子数组，满足 第二 个子数组与第 k 个子数组中第一个元素的下标距离 不超过 dist 。换句话说，如果你将 nums 分割成子数组 $nums[0..(i_1 - 1)], nums[i_1..(i_2 - 1)], ..., nums[i_{k-1}..(n - 1)] ，$ 那么它需要满足 $i_{k-1} - i_1 <= dist$ 请你返回这些子数组的 最小 总代价。 提示： 3 <= n <= 105 1 <= nums[i] <= 109 3 <= k <= n k - 2 <= dist <= n - 2 思路 从将 nums 分割成 k 个 连续且互不相交 的子数组得到 ...
翻转树上最少边 给你一棵包含 n 个节点的 无向树，节点编号从 0 到 n - 1。该树由长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。 另外给你两个长度为 n 的 二进制 字符串 start 和 target。对于每个节点 x，start[x] 是其初始颜色，而 target[x] 是其目标颜色。 在一次操作中，你可以选择下标为 i 的一条边并 翻转 它的两个端点。也就是说，如果这条边是 [u, v]，那么节点 u 和 v 的颜色 各自 从 ‘0’ 变为 ‘1’，或者从 ‘1’ 变为 ‘0’。 返回一个边下标数组，执行这些边对应的操作可以将 start 转换为 target。在所有有效序列中找出 长度最短 的序列，以 升序 返回边下标。 如果无法将 start 转换为 target，则返回一个仅包含单个元素 -1 的数组。 ...
3811.交替按位异或分割的数目 给你一个整数数组 nums 以及两个 互不相同 的整数 target1 和 target2。nums 的一个 分割 是指将其划分为一个或多个 连续且非空 的块，这些块在不重叠的情况下覆盖整个数组。 如果一个分割中各块元素的 按位异或 结果在 target1 和 target2 之间 交替 出现，且以 target1 开始，则称该分割是 有效的。 形式上，对于块 b1, b2, … ： XOR(b1) = target1 XOR(b2) = target2（如果存在） XOR(b3) = target1，以此类推。 返回 nums 的有效分割方案数，结果对 $10^9 $+ 7 取余。 注意： 如果单个块的 按位异或 结果等于 target1，则该分割也是有效的。 1 <= nums.length <= $10^5$ 0 <= nums[i], target1, target2 <= $10^5$ target1 != target2 思路 方法一：递归+记忆化搜索 点击展开/折叠代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { int mod = 1e9 + 7, t[2]; vector<vector<long long>> memo; long long dfs(int i, int state, vector<int> &nums) { if (i == nums.size()) { return 0; } if (memo[i][state] != -1) { return memo[i][state]; } long long res = 0; int cur = 0; for (int j = i; j < nums.size(); j++) { cur ^= nums[j]; if (cur == t[state]) { if (j == nums.size() - 1) { res = (res + 1) % mod; } else { res = (res + dfs(j + 1, state ^ 1, nums)) % mod; } } } return memo[i][state]=res; } public: int alternatingXOR(vector<int> &nums, int target1, int target2) { int n = nums.size(); t[0] = target1; t[1] = target2; memo.resize(n, vector<long long>(2, -1)); return dfs(0, 0, nums); } }; 时间复杂度：O(n)，其中n为数组nums的长度。 空间复杂度：O(n)，需要使用一个二维数组memo来存储中间结果。 不足以通过所有测试用例，超时。 ...
线段树是一种特殊的数据结构，它可以在 $O(\log n)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 最简单的线段树的构建： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 #include <iostream> #include <vector> using namespace std; // 定义线段树的节点 struct Node { int l, r; // 左右子节点的下标 int sum; // 区间和 }; vector<Node> tree; // 存储线段树的数组 // 构建线段树 void build(int l, int r, int index, vector<int>& nums) { tree[index].l = l; tree[index].r = r; if (l == r) { // 叶子节点 tree[index].sum = nums[l]; return; } int mid = (l + r) / 2; build(l, mid, index * 2, nums); // 构建左子树 build(mid + 1, r, index * 2 + 1, nums); // 构建右子树 tree[index].sum = tree[index * 2].sum + tree[index * 2 + 1].sum; // 计算区间和 } // 区间查询 int query(int l, int r, int index) { if (tree[index].l >= l && tree[index].r <= r) { // 当前区间完全包含在查询区间内 return tree[index].sum; } int mid = (tree[index].l + tree[index].r) / 2; int sum = 0; if (l <= mid) { // 查询区间和左子树有交集 sum += query(l, r, index * 2); } if (r > mid) { // 查询区间和右子树有交集 sum += query(l, r, index * 2 + 1); } return sum; } // 单点修改 void update(int pos, int val, int index) { if (tree[index].l == tree[index].r) { // 叶子节点 tree[index].sum = val; return; } int mid = (tree[index].l + tree[index].r) / 2; if (pos <= mid) { // 修改的位置在左子树 update(pos, val, index * 2); } else { // 修改的位置在右子树 update(pos, val, index * 2 + 1); } tree[index].sum = tree[index * 2].sum + tree[index * 2 + 1].sum; // 更新区间和 } int main() { vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 原始数组 int n = nums.size(); // 数组长度 tree.resize(n * 4); // 线段树的大小为 4n build(0, n - 1, 1, nums); // 构建线段树 cout << query(0, 4, 1) << endl; // 查询区间 [0, 4] 的和 update(2, 10, 1); // 将第 2 个元素修改为 10 cout << query(0, 4, 1) << endl; // 查询区间 [0, 4] 的和 return 0; } 构建解释： 递归地将数组分为左右两个子数组，直到子数组长度为 1，此时该子数组的区间和就是该子数组的元素值。 ...