电商网站建设要多少钱,网站轮播图片特效,能看建设动漫黄图的网站,淮安做微信网站Q1、检测相邻递增子数组 Ⅰ
1、题目描述
给你一个由 n 个整数组成的数组 nums 和一个整数 k#xff0c;请你确定是否存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说#xff0c;需要检查是否存在从下标 a 和 b (a b) 开始的 两个 子数组#xff0c;并满足下…Q1、检测相邻递增子数组 Ⅰ
1、题目描述
给你一个由 n 个整数组成的数组 nums 和一个整数 k请你确定是否存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说需要检查是否存在从下标 a 和 b (a b) 开始的 两个 子数组并满足下述全部条件
这两个子数组 nums[a..a k - 1] 和 nums[b..b k - 1] 都是 严格递增 的。这两个子数组必须是 相邻的即 b a k。
如果可以找到这样的 两个 子数组请返回 true否则返回 false。
子数组 是数组中的一个连续 非空 的元素序列。
2、解题思路
要解决这个问题我们需要检查数组 nums 中是否存在两个相邻的严格递增子数组且每个子数组的长度为 k。因此可以将问题分解为以下步骤
检查递增子数组我们先遍历 nums找出从每个索引 i 开始的长度为 k 的子数组是否为严格递增。相邻递增子数组检查如果在遍历过程中找到了满足条件的相邻严格递增子数组则返回 true。如果遍历结束没有找到返回 false。
3、解题过程
从数组的每个索引 i 开始检查 nums[i..ik-1] 是否严格递增。如果 nums[i..ik-1] 和 nums[ik..i2*k-1] 都是严格递增的且满足两个子数组是相邻的则返回 true。如果遍历完毕没有找到满足条件的子数组则返回 false。
4、代码实现
class Solution {
public:bool hasIncreasingSubarrays(vectorint nums, int k) {int n nums.size();// 边界情况检查if (n 2 * k) {return false;}// 遍历数组, 检查相邻的递增子数组for (int i 0; i n - 2 * k; i) {bool Increasing true;// 检查第一个长度为 k 的子数组是否严格递增for (int j i; j i k - 1; j) {if (nums[j] nums[j 1]) {Increasing false;break;}}// 剪枝if (!Increasing) {continue;}// 检查第二个长度为 k 的子数组是否严格递增for (int j i k; j i 2 * k - 1; j) {if (nums[j] nums[j 1]) {Increasing false;break;}}// 如果相邻的两个子数组都是严格递增的, 则返回 trueif (Increasing) {return true;}}// 遍历完后任未找到符合条件的子数组, 返回 falsereturn false;}
};Q2、检测相邻递增子数组 Ⅱ
1、题目描述
给你一个由 n 个整数组成的数组 nums 请你找出 k 的 最大值使得存在 两个 相邻 且长度为 k 的 严格递增
子数组。具体来说需要检查是否存在从下标 a 和 b (a b) 开始的 两个 子数组并满足下述全部条件
这两个子数组 nums[a..a k - 1] 和 nums[b..b k - 1] 都是 严格递增 的。这两个子数组必须是 相邻的即 b a k。
返回 k 的 最大可能 值。
子数组 是数组中的一个连续 非空 的元素序列。
2、解题思路
在给定问题中我们的目标是寻找两个相邻且严格递增的子数组并且最大化长度 。当前的超时可能由于在每个候选长度 k 上都逐一检查数组所致。为此我们可以对每个元素的递增情况进行一次遍历预处理连续的递增段信息然后利用这些信息来快速验证长度为 k 的相邻递增子数组是否存在。 递增段预处理 预先处理 nums 中每个位置 i 的最长递增序列长度 increasing_lengths[i]表示从位置 i 开始的最长递增序列的长度。 通过一次遍历即可获取此信息。 二分查找确定最大 使用二分查找寻找最大的 k 值。对于每个候选长度 k快速判断是否存在相邻且严格递增的子数组。在判断过程中利用 increasing_lengths 数组来验证如果位置 i 的递增序列长度 increasing_lengths[i] ≥ k 且位置 i k 的递增序列长度 increasing_lengths[i k] ≥ k则位置 i 和 i k 可以构成所需的相邻递增子数组。
3、代码实现
class Solution {
public:int maxIncreasingSubarrays(vectorint nums) {int n nums.size();// 预处理递增长度vectorint increasing_lengths(n, 1);for (int i n - 2; i 0; --i) {if (nums[i] nums[i 1]) {increasing_lengths[i] increasing_lengths[i 1] 1;}}// 二分查找确定最大 k 值int low 1, high n / 2;int maxK 0;while (low high) {int mid low (high - low) / 2;bool found false;// 检查是否存在两个长度为 mid 的相邻递增子数组for (int i 0; i 2 * mid - 1 n; i) {if (increasing_lengths[i] mid increasing_lengths[i mid] mid) {found true;break;}}if (found) {maxK mid;low mid 1;} else {high mid - 1;}}return maxK;}
};4、复杂度分析 时间复杂度: 预处理 increasing_lengths 数组的复杂度为 O(n)。二分查找过程的复杂度为 O(logn)对于每个候选长度 k只需 O(n) 的时间验证是否存在符合条件的相邻子数组。因此总复杂度为 O(nlogn)。 空间复杂度: O(n)用于存储 increasing_lengths 数组。 Q3、好子序列的元素之和
1、题目描述
给你一个整数数组 nums。好子序列 的定义是子序列中任意 两个 连续元素的绝对差 恰好 为 1。
子序列 是指可以通过删除某个数组的部分元素或不删除得到的数组并且不改变剩余元素的顺序。
返回 nums 中所有 可能存在的 好子序列的 元素之和。
因为答案可能非常大返回结果需要对 109 7 取余。
注意长度为 1 的子序列默认为好子序列。
2、解题思路
1. 子问题拆解
我们要处理的是所有满足条件的子序列并求它们元素的总和。 这涉及
统计每个元素能够生成多少种好子序列。计算这些子序列的和。
2. 动态规划
设
cnt[x] 表示以元素 x 结尾的好子序列的个数。f[x] 表示以元素 x 结尾的所有好子序列的元素总和。
3. 转移公式 遍历数组中的每个元素 x 对于每个 x好子序列可以从以下几种情况构成 独立的好子序列长度为 1计数为 1元素和为 x。连接到 x-1 的好子序列可以接在所有以 x-1 结尾的好子序列后。连接到 x1 的好子序列可以接在所有以 x1 结尾的好子序列后。 更新公式 c n t [ x ] c n t [ x − 1 ] c n t [ x 1 ] 1 cnt[x] cnt[x-1] cnt[x1] 1 cnt[x]cnt[x−1]cnt[x1]1 f [ x ] f [ x − 1 ] f [ x 1 ] x × c n t [ x ] f[x] f[x-1] f[x1] x \times cnt[x] f[x]f[x−1]f[x1]x×cnt[x] 遍历完成后所有好子序列的总和为 sum ( f [ x ] ) \text{sum}(f[x]) sum(f[x])。
4. 使用哈希表
由于元素可能不是连续的我们使用哈希表 f 和 cnt 记录每个元素对应的状态避免无意义的内存浪费。
3、代码实现
class Solution {
public:int sumOfGoodSubsequences(vectorint nums) {// 定义模数const int MOD 1000000007;// 定义哈希表: f 用于记录元素和, cnt 用于记录以某元素为结尾的子序列个数unordered_mapint, int f, cnt;// 遍历数组for (int x : nums) {// c 是当前元素 x 能够构成的好子序列个数long long c (cnt[x - 1] cnt[x 1] 1) % MOD;// 更新以 x 结尾的子序列的总和 f[x]f[x] (x * c f[x] f[x - 1] f[x 1]) % MOD;// 更新以 x 结尾的子序列个数 cnt[x]cnt[x] (cnt[x] c) % MOD;}// 最终结果为所有元素的 f 值之和long long ret 0;for (const auto [_, s] : f) {ret s;}return ret % MOD; // 返回结果取模}
};4、复杂度分析
时间复杂度
遍历数组每个元素更新状态 时间复杂度O(n)其中 n 是数组长度。
空间复杂度
使用哈希表记录 cnt 和 f存储最多 O(n) 个元素 空间复杂度O(n)。 Q4、统计小于 N 的 K 可约简整数
1、题目描述
给你一个 二进制 字符串 s它表示数字 n 的二进制形式。
同时另给你一个整数 k。
如果整数 x 可以通过最多 k 次下述操作约简到 1 则将整数 x 称为 k-可约简 整数
将 x 替换为其二进制表示中的置位数即值为 1 的位。
例如数字 6 的二进制表示是 110。一次操作后它变为 2因为 110 中有两个置位。再对 2二进制为 10进行操作后它变为 1因为 10 中有一个置位。
返回小于 n 的正整数中有多少个是 k-可约简 整数。
由于答案可能很大返回结果需要对 109 7 取余。
二进制中的置位是指二进制表示中值为 1 的位。
2、解题思路 二进制分位处理 每个小于 s 的数字可以看作是一个二进制字符串类似数位 DP 的思想我们逐位构造合法的数字。 在构造过程中记录数字的置位数量并确保这些数字小于 s。 预计算 k-可约简性 对于每个可能的置位数 ones_count我们计算数字是否能在 k 次操作内归约到 1。 使用函数 reduction_steps[x] 表示数字 x 需要的操作次数 reduction_steps[x] reduction_steps[popcount(x)] 1其中 popcount(x) 表示 x 的置位数。 动态规划 定义 dfs(pos, remaining_ones, is_limit) pos 表示当前处理的位。remaining_ones 表示需要匹配的置位数量。is_limit 表示当前是否受限于数字 s。 每次枚举当前位是否为 1并递归处理剩余的位。 合并结果 遍历所有可能的 ones_count检查 reduction_steps[ones_count] 是否小于等于 k。 如果满足条件使用 dfs 统计符合条件的数字个数并累加。
3、代码实现
class Solution {
public:int countKReducibleNumbers(string s, int k) {const int MOD 1000000007;int n s.length();// 用于记忆化搜索, memo[i][remaining_ones] 表示从第 i 位开始, 剩余 remaining_ones 个置位的合法二进制字符串数目vectorvectorint memo(n, vectorint(n, -1));// 深度优先搜索函数, 返回满足条件的数字个数auto dfs [](auto self, int pos, int remaining_ones, bool is_limit) - int {// 如果已经处理完所有位, 检查剩余置位是否为 0if (pos n) {return !is_limit remaining_ones 0;}// 如果未受限且已经计算过当前状态, 直接返回记忆化结果if (!is_limit memo[pos][remaining_ones] ! -1) {return memo[pos][remaining_ones];}// 当前位的最大值int upper_bound is_limit ? s[pos] - 0 : 1;int result 0;// 枚举当前位可能取的值for (int digit 0; digit min(upper_bound, remaining_ones); digit) {result (result self(self, pos 1, remaining_ones - digit, is_limit digit upper_bound)) % MOD;}// 如果未受限, 则记录当前结果if (!is_limit) {memo[pos][remaining_ones] result;}return result;};long long total_count 0;// 预计算每个数字需要多少次操作可以归约到 1vectorint reduction_steps(n);for (int i 1; i n; i) {reduction_steps[i] reduction_steps[__builtin_popcount(i)] 1;}// 遍历所有可能的置位数, 计算合法的数字个数for (int ones_count 1; ones_count n; ones_count) {if (reduction_steps[ones_count] k) {// 计算二进制中恰好有 ones_count 个 1 的合法数字个数total_count dfs(dfs, 0, ones_count, true);total_count % MOD;}}return total_count;}
};4、复杂度分析
时间复杂度
预计算 reduction_steps 复杂度为 O ( n 2 ) O(n^2) O(n2)由于需要对所有可能的数字计算置位数。每次 dfs 的复杂度为 O ( n 2 ) O(n^2) O(n2)共进行 O ( n ) O(n) O(n) 次整体为 O ( n 3 ) O(n^3) O(n3)。
空间复杂度
记忆化数组 memo 占用 O ( n 2 ) O(n^2) O(n2) 空间。
