Algorithm Programming Problem

1888. 使二进制字符串字符交替的最少反转次数 给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次： 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。 请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。 我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。 比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是。 提示： $1 <= s.length <= 10^5$ s[i] 要么是 '0' ，要么是 '1' 。 思路 首先，目的是得到0101..或1010..样式的字符串。 类型1可以操作任意次，也就是说可以使用s+s的长度为 n 的子串和目标字符串进行比较。 使用cnt记录达到0101..需要进行的类型2操作数，n-cnt 就是达到0101..需要进行的类型2操作数。 每次向右滑动一位，出滑动窗口的字符与目标字符串对应位进行比较，若不同，则cnt–，因为之前记录时加入了修改用的操作数；进滑动窗口的字符与目标字符串对应位进行比较，若不同，同理，cnt++。 每滑一次，更新ans=min({ans,n-cnt,cnt})。 点击展开/折叠 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public: int minFlips(string s) { int n = s.size(); string tar = "01"; int cnt = 0; for (int i = 0; i < n; i++) { cnt += (s[i] != tar[i % 2]); } int ans = min({cnt, n - cnt}); for (int i = 0; i < n; i++) { cnt -= (s[i] != tar[i % 2]); cnt += (s[i] != tar[(i + n) % 2]); ans = min({ans, cnt, n - cnt}); } return ans; } };

2266. 统计打字方案数 Alice 在给 Bob 用手机打字。数字到字母的 对应 如下图所示。 为了 打出 一个字母，Alice 需要 按 对应字母 i 次，i 是该字母在这个按键上所处的位置。 比方说，为了按出字母 's' ，Alice 需要按 '7' 四次。类似的， Alice 需要按 '5' 两次得到字母 'k' 。 注意，数字 '0' 和 '1' 不映射到任何字母，所以 Alice 不 使用它们。 但是，由于传输的错误，Bob 没有收到 Alice 打字的字母信息，反而收到了 按键的字符串信息 。 比方说，Alice 发出的信息为 "bob" ，Bob 将收到字符串 "2266622" 。 给你一个字符串 pressedKeys ，表示 Bob 收到的字符串，请你返回 Alice 总共可能发出多少种文字信息 。 由于答案可能很大，将它对 $10^9 + 7$ 取余 后返回。 提示： $1 <= pressedKeys.length <= 10^5$ pressedKeys 只包含数字 '2' 到 '9' 。 题解 首先，这是一个动态规划问题，接收的字符串 pressedKeys 可以被分割成多个子问题，每个子问题都是一个子字符串，子字符串为同样字符。 ...

三段式数组 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]$。 公式：如果 $nums[i] > nums[i-1]$，$preSum[i] = \max(nums[i] + nums[i-1], preSum[i-1] + nums[i])$。 sufSum[i]: 以 $i$ 开头且满足“严格递增”的最大子数组和。 条件：必须包含 $nums[i]$ 和 $nums[i+1]$。 公式：如果 $nums[i] < nums[i+1]$，$sufSum[i] = \max(nums[i] + nums[i+1], sufSum[i+1] + nums[i])$。 ...

将数组分成最小总代价的子数组 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，此时该子数组的区间和就是该子数组的元素值。 ...