Algorithm Programming Problem

3290. 最高乘法得分 给你一个大小为 4 的整数数组 a 和一个大小 至少为 4 的整数数组 b。 你需要从数组 b 中选择四个下标 i0, i1, i2, 和 i3，并满足 i0 < i1 < i2 < i3。你的得分将是 a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3] 的值。 返回你能够获得的 最大 得分。 提示： $a.length == 4$ $4 <= b.length <= 10^5$ $-10^5 <= a[i], b[i] <= 10^5$ 思路 用dp来做，从后往前选取a[i]、b[j]相乘，考虑2种状态： 选当前a[i]、b[j]相乘，继续考虑a[i-1]、b[j-1] 不选选当前a[i]、b[j]相乘，继续考虑a[i]、b[j-1] 状态转换： dfs(i,j)=max(dfs(i-1,j-1)+a[i]*b[j],dfs(i,j-1)) 点击展开/折叠 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: long long maxScore(vector<int>& a, vector<int>& b) { int n=b.size(); vector<array<long long,4>>memo(n); for(auto&row:memo){ ranges::fill(row,LLONG_MIN); } auto dfs=[&](auto&&dfs,int i,int j)->long long{ if(j<0)return 0; if(i<0){ return LLONG_MIN/2; } auto &res=memo[i][j]; if(res==LLONG_MIN){ res=max(dfs(dfs,i-1,j),dfs(dfs,i-1,j-1)+(long long)a[j]*b[i]); } return res; }; return dfs(dfs,n-1,3); } }; 参考 ...

474. 一和零 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。 提示： 1 <= strs.length <= 600 1 <= strs[i].length <= 100 strs[i] 仅由 '0' 和 '1' 组成 1 <= m, n <= 100 思路 首先，这是一个二维0-1背包问题，可以使用三维数组解决。 f[i][j][k]:i代表0~i的选取结果,j代表不超过j个零,k同理。 f[i][j][k]=max(dp[i−1][j][k],dp[i−1][j−当前字符串使用0的个数][k−当前字符串使用1的个数]+1) dp[i−1][j][k] 不选择当前考虑的字符串i dp[i−1][j−当前字符串使用0的个数][k−当前字符串使用1的个数]+1 选择当前考虑的字符串​ 初始化：为了避免分类讨论，通常多设置一行。这里可以认为，第 0 个字符串是空串。 点击展开/折叠 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 class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { int len = strs.size(); vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0))); for (int i = 1; i <= len; i++) { int x1 = cnum(strs[i - 1]); int x0 = strs[i - 1].size() - x1; for (int j = 0; j <= m; j++) { for (int k = 0; k <= n; k++) { dp[i][j][k] = dp[i - 1][j][k]; if (j >= x0 && k >= x1) { dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - x0][k - x1] + 1); } } } } return dp[len][m][n]; } int cnum(string s) { int cnt = 0; for (auto c : s) { if (c == '1') cnt++; } return cnt; } }; 参考 ...

1415. 长度为 n 的开心字符串中字典序第 k 小的字符串 一个 「开心字符串」定义为： 仅包含小写字母 ['a', 'b', 'c']. 对所有在 1 到 s.length - 1 之间的 i ，满足 s[i] != s[i + 1] （字符串的下标从 1 开始）。 比方说，字符串 “abc”，“ac”，“b” 和 “abcbabcbcb” 都是开心字符串，但是 “aa”，“baa” 和 “ababbc” 都不是开心字符串。 给你两个整数 n 和 k ，你需要将长度为 n 的所有开心字符串按字典序排序。 请你返回排序后的第 k 个开心字符串，如果长度为 n 的开心字符串少于 k 个，那么请你返回 空字符串 。 提示： 1 <= n <= 10 1 <= k <= 100 思路 首先，长度为 n 的开心字符串个数为(1<<(n-1))*3，若小于k，则返回空字符串 。 设置一个字符作为已经添加的前一个字符，保证得到开心字符串。 令count_per_choice=1<<(n-i-1)为每添加一个字符所代表的可能性，每次从a到c遍历，若count_per_choice>=k,则取当前字符，跳出循环，否则k-count_per_choice,继续遍历。 ...

3129. 找出所有稳定的二进制数组 I 给你 3 个正整数 zero ，one 和 limit 。 一个 二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ： 0 在 arr 中出现次数 恰好 为 zero 。 1 在 arr 中出现次数 恰好 为 one 。 arr 中每个长度超过 limit 的 子数组 都 同时 包含 0 和 1 。 请你返回 稳定 二进制数组的 总 数目。 由于答案可能很大，将它对 $10^9 + 7$ 取余 后返回。 提示： 1 <= zero, one, limit <= 200 思路 首先，这个问题是每个位有两个选择0/1，再加上限制limit,感觉就可以用dp做。 定义： f[i][j][0] 为使用 i 个 0，j 个 1，且末尾为 0 的稳定数组个数； ...

1594. 矩阵的最大非负积 给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。 在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。 返回 最大非负积 对 $10^9 + 7$ 取余 的结果。如果最大积为 负数 ，则返回 -1 。 注意取余是在得到最大积之后执行的。 提示： m == grid.length n == grid[i].length 1 <= m, n <= 15 -4 <= grid[i][j] <= 4 思路 首先，这是一个典型的dp问题，要求从左上角到右下角的路径乘积和最大非负积 取余 的结果。 可以使用两个和gird大小一致的数组big,sml分别存放到某个位置（i,j）的最大和最小乘积。 计算时注意，最上一行没有来自上的计算，最左一行没有来自左的计算，所以计算时先初始化（0，0）位置的big[0][0]=sml[0][0]=grid[0][0],然后计算最上一行、最左一行，最后计算剩下的。 点击展开/折叠 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 class Solution { public: int maxProductPath(vector<vector<int>>& grid) { const int MOD = 1e9 + 7; int m = grid.size(), n = grid[0].size(); vector<vector<long long>> big(m, vector<long long>(n)); vector<vector<long long>> sml(m, vector<long long>(n)); big[0][0] = grid[0][0]; sml[0][0] = grid[0][0]; for (int i = 1; i < m; ++i) { big[i][0] = sml[i][0] = (long long)big[i-1][0] * grid[i][0]; } for (int j = 1; j < n; ++j) { big[0][j] = sml[0][j] = (long long)big[0][j-1] * grid[0][j]; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { vector<long long> candidates = { (long long)big[i-1][j] * grid[i][j], (long long)sml[i-1][j] * grid[i][j], (long long)big[i][j-1] * grid[i][j], (long long)sml[i][j-1] * grid[i][j] }; big[i][j] = *max_element(candidates.begin(), candidates.end()); sml[i][j] = *min_element(candidates.begin(), candidates.end()); } } return big[m-1][n-1] >= 0 ? (big[m-1][n-1] % MOD) : -1; } };

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]$。 ...

将数组分成最小总代价的子数组 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 的数组。 ...