局域网网站建设需要什么条件,佛山seo网站排名,外贸网站有必要吗,北京公司注册地址查询文章目录 6889.特殊元素平方和思路完整版取模注意#xff1a;不能对0取余/取模解答错误#xff1a;本题的数组最后一个下标是nums[nums.size()] 6929.数组的最大美丽值#xff08;排序滑动窗口#xff09;思路1#xff1a;排序滑动窗口注意点 6927. 合法分割的最小下标不能对0取余/取模解答错误本题的数组最后一个下标是nums[nums.size()] 6929.数组的最大美丽值排序滑动窗口思路1排序滑动窗口注意点 6927. 合法分割的最小下标倒推的思路思路思路1哈希表统计元素频率思路2投票法找出出现频率最高的元素投票法介绍 补充投票法 6889.特殊元素平方和
主要注意点是本题的i并不是数组下标的i是按照数字顺序来的
给你一个下标从 1 开始、长度为 n 的整数数组 nums 。
对 nums 中的元素 nums[i] 而言如果 n 能够被 i 整除即 n % i 0 则认为 num[i] 是一个 特殊元素 。
返回 nums 中所有 特殊元素 的 平方和 。
示例 1
输入nums [1,2,3,4]
输出21
解释nums 中共有 3 个特殊元素nums[1] 因为 4 被 1 整除nums[2] 因为 4 被 2 整除以及 nums[4] 因为 4 被 4 整除。
因此nums 中所有元素的平方和等于 nums[1] * nums[1] nums[2] * nums[2] nums[4] * nums[4] 1 * 1 2 * 2 4 * 4 21 。 示例 2
输入nums [2,7,1,19,18,3]
输出63
解释nums 中共有 4 个特殊元素nums[1] 因为 6 被 1 整除nums[2] 因为 6 被 2 整除nums[3] 因为 6 被 3 整除以及 nums[6] 因为 6 被 6 整除。
因此nums 中所有元素的平方和等于 nums[1] * nums[1] nums[2] * nums[2] nums[3] * nums[3] nums[6] * nums[6] 2 * 2 7 * 7 1 * 1 3 * 3 63 。 提示
1 nums.length n 501 nums[i] 50
思路
本题属于比较简单的模拟题遍历再模拟是否整除即可。
完整版
class Solution {
public:int sumOfSquares(vectorint nums) {int sum0;int nnums.size();//本题的判断对象是n//for循环遍历里面是本题的自定义数组下标for(int i1;inums.size();i){if(n%i0){//此处是真实的数组下标sumnums[i-1]*nums[i-1];}}return sum;}
};取模注意不能对0取余/取模
因为数组的下标从0开始但是所有对0的取余/取模运算都是违法的。
最开始写成了
class Solution {
public:int sumOfSquares(vectorint nums) {int sum0;int nnums.size();//本题的判断对象是nfor(int i0;inums.size();i){if(n%i0){sumnums[i]*nums[i];}}return sum;}
};但是会出现执行错误不能对0取模 解答错误本题的数组最后一个下标是nums[nums.size()]
当我们直接改成初始值i1又会出现结果错误 原因是从示例中我们看出nums[4]是最后一个元素也就是说本题的下标并不是按照普通数组的形式而是与数字顺序一致题目里的数组下标特殊含义也要注意。 因此本题的for循环应该从i1开始遍历一直到inums.size()。内部求平方和的逻辑直接用nums[i-1]进行计算。
6929.数组的最大美丽值排序滑动窗口
本题主要是需要想到经过排序相等的元素会相邻在一起也就是说相等的元素成为了连续序列求序列最大长度就是滑动窗口类型题目了。本题关于元素顺序保持不变的要求可以忽略一是因为求最大长度和元素顺序无关二是因为所有解法都不能保证不改变元素顺序。需要排序
给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。
在一步操作中你可以执行下述指令
在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。将 nums[i] 替换为范围 [nums[i] - k, nums[i] k] 内的任一整数。
数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。
对数组 nums 执行上述操作任意次后返回数组可能取得的 最大 美丽值。
**注意**你 只 能对每个下标执行 一次 此操作。
数组的 子序列 定义是经由原数组删除一些元素也可能不删除得到的一个新数组且在此过程中剩余元素的顺序不发生改变。
示例 1
输入nums [4,6,1,2], k 2
输出3
解释在这个示例中我们执行下述操作
- 选择下标 1 将其替换为 4从范围 [4,8] 中选出此时 nums [4,4,1,2] 。
- 选择下标 3 将其替换为 4从范围 [0,4] 中选出此时 nums [4,4,1,4] 。
执行上述操作后数组的美丽值是 3子序列由下标 0 、1 、3 对应的元素组成。
可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。示例 2
输入nums [1,1,1,1], k 10
输出4
解释在这个示例中我们无需执行任何操作。
数组 nums 的美丽值是 4整个数组。提示
1 nums.length 1050 nums[i], k 105
思路1排序滑动窗口
因为美丽值的定义是数组中由相等元素组成的最长子序列的长度因此我们想要获得全部都是相等元素的序列并求最大长度。
虽然本题要求 子序列 定义是剩余元素的顺序不发生改变但是求的是相等元素组成的最长子序列长度因此元素的顺序并不影响结果。
实际上本题所有解法都不考虑元素顺序所以这个条件有点问题
因此我们可以先进行排序让相等的元素排在一起此时只需要判断窗口左端点最小值和右端点最大值是不是相等也就是只有nums[r]-knums[l]k的时候才作为有效窗口。
此时本题就转变成了求满足nums[r]-knums[l]k条件的最长子序列也就是找最长的连续子数组其最大值-最小值不超过2k。
也属于找最长子序列问题。最长子序列需要枚举右端点只有不满足条件的时候才更新左端点。
算法专题整理滑动窗口_大磕学家ZYX的博客-CSDN博客
class Solution {
public:int maximumBeauty(vectorint nums, int k) {sort(nums.begin(), nums.end());int res0;for (int l 0, r 0; r nums.size(); r) {while (nums[r]-k nums[l] k) {l;}res max(res, r - l 1);}return res;}
};注意点
由于选的是子序列且子序列的元素都相等所以元素顺序对答案没有影响可以先对数组排序。
且仔细看用例1可以看出并不要求最后的子数组在原数组也是连续的只是找替换后相等的数字组成的总长度并不是找原数组中就连续的子数组
参考题解 灵茶山艾府 力扣周赛总结
6927. 合法分割的最小下标倒推的思路
本题重点是想明白如果想要相等最后那个结果肯定是原数组的支配元素。因此可以根据支配元素的结果倒推已知支配元素一定是这个数值去求那两个子数组支配元素是不是这个。这种倒推的思路要注意。
如果元素 x 在长度为 m 的整数数组 arr 中满足 freq(x) * 2 m 那么我们称 x 是 支配元素 。其中 freq(x) 是 x 在数组 arr 中出现的次数。注意根据这个定义数组 arr 最多 只会有 一个 支配元素。
给你一个下标从 0 开始长度为 n 的整数数组 nums 数据保证它含有一个支配元素。
你需要在下标 i 处将 nums 分割成两个数组 nums[0, ..., i] 和 nums[i 1, ..., n - 1] 如果一个分割满足以下条件我们称它是 合法 的
0 i n - 1nums[0, ..., i] 和 nums[i 1, ..., n - 1] 的支配元素相同。
这里 nums[i, ..., j] 表示 nums 的一个子数组它开始于下标 i 结束于下标 j 两个端点都包含在子数组内。特别地如果 j i 那么 nums[i, ..., j] 表示一个空数组。
请你返回一个 合法分割 的 最小 下标。如果合法分割不存在返回 -1 。
示例 1
输入nums [1,2,2,2]
输出2
解释我们将数组在下标 2 处分割得到 [1,2,2] 和 [2] 。
数组 [1,2,2] 中元素 2 是支配元素因为它在数组中出现了 2 次且 2 * 2 3 。
数组 [2] 中元素 2 是支配元素因为它在数组中出现了 1 次且 1 * 2 1 。
两个数组 [1,2,2] 和 [2] 都有与 nums 一样的支配元素所以这是一个合法分割。
下标 2 是合法分割中的最小下标。示例 2
输入nums [2,1,3,1,1,1,7,1,2,1]
输出4
解释我们将数组在下标 4 处分割得到 [2,1,3,1,1] 和 [1,7,1,2,1] 。
数组 [2,1,3,1,1] 中元素 1 是支配元素因为它在数组中出现了 3 次且 3 * 2 5 。
数组 [1,7,1,2,1] 中元素 1 是支配元素因为它在数组中出现了 3 次且 3 * 2 5 。
两个数组 [2,1,3,1,1] 和 [1,7,1,2,1] 都有与 nums 一样的支配元素所以这是一个合法分割。
下标 4 是所有合法分割中的最小下标。示例 3
输入nums [3,3,3,3,7,2,2]
输出-1
解释没有合法分割。提示
1 nums.length 1051 nums[i] 109nums 有且只有一个支配元素。
思路
这道题的重要注意点在于如果想要两个子数组的支配元素相等那么这个支配元素肯定也是原数组的支配元素
所以就可以倒过来推导先求原数组支配元素然后再看这个支配元素是否在两个子数组里也是支配的
想明白这一点之后剩下的就是模拟了模拟的部分也可以练习一下。
思路1哈希表统计元素频率
首先要找到这个数组的支配元素。我们可以使用哈希表unordered_map来存储每个元素的频率。在这个过程中我们同时找出频率最高的元素即为我们的支配元素。
在找到支配元素后再次遍历数组。这一次遍历要找出合法的分割点。一个合法的分割点需要满足以下条件
[0, …, i] 的支配元素与整个数组的支配元素相同即 nums[i] dominator在当前分割点之前包括分割点支配元素的出现次数超过了数组的一半即 count (i 1) / 2在当前分割点之后剩余的支配元素出现次数仍超过后半部分数组的一半即 (maxFreq - count) (n - i - 1) / 2。如果当前分割点满足以上所有条件我们就找到了一个合法的分割点。我们需要找的是最小的分割点所以一旦找到我们就直接返回这个分割点的索引 i。
class Solution {
public:int minimumIndex(vectorint nums) {//先建立哈希表统计原数组的支配元素unordered_mapint,intumap;//遍历所有元素统计频率int maxFreq 0;int x0;for(int i0;inums.size();i){umap[nums[i]];//最大频率if(umap[nums[i]]maxFreq){maxFreq umap[nums[i]];xnums[i];//同时存储频率最高数值}}//遍历i对于i分割的两个子数组判断支配元素是不是xint count0;for(int i0;inums.size();i){if(nums[i]x){ //统计支配元素的频率count;}//统计完了可以直接判断i之前元素的count是不是长度/2,之后的频率是不是长度/2//注意边界条件的长度i1已经算了i本身了后面的nums.size()-i就不能算i了if(count(i1)/2(maxFreq-count)(nums.size()-i-1)/2){return i;}}return -1;}
};思路2投票法找出出现频率最高的元素
也可以用投票法求出占比最高的元素及其频率。
投票法介绍
投票法是一种用于找出数组中多数元素的算法这个算法的基本原理是
如果一个元素是数组的多数元素出现次数超过数组长度的一半那么即使我们把它和其他每个不同的元素一一抵消每次都从数组中删除两个不同的元素最后剩下的一定是这个多数元素。
由于题目保证了数组中最多只存在一个支配元素投票法最后找到的元素必然是这个支配元素。
class Solution {
public:int minimumIndex(vectorint nums) {int n nums.size();int cnt 0, x 0;// 投票法求元素 xfor (int num: nums) { // 遍历数组if (num x) { // 如果当前元素等于候选元素cnt; // 候选元素的票数加一} else { // 如果当前元素不等于候选元素cnt--; // 候选元素的票数减一相当于抵消掉了if (cnt 0) { // 如果票数小于0x num; // 将当前元素作为新的候选元素cnt 1; // 将新的候选元素的票数设为1}}}// 求 x 出现的总数int sum 0;for (int num: nums) { // 再次遍历数组if (x num) sum; // 如果当前元素等于支配元素将支配元素的总数加一}// 枚举求解 icnt 0;for (int i 0; i n; i) { // 再次遍历数组寻找分割点if (x nums[i]) cnt; // 如果当前元素等于支配元素将支配元素的出现次数加一if (cnt * 2 (i 1) (sum - cnt) * 2 (n - i - 1)) return i; // 检查是否满足分割条件如果满足返回当前索引}return -1; // 如果遍历完数组都没有找到合法的分割点返回-1}
};
补充投票法
投票法是找**数组中出现频率超过半数必须是超过不能是等于**的元素。数组中出现频率超过半数的元素一定只有一个
投票法Boyer-Moore Voting Algorithm是一种用于在数组中查找主要元素的算法主要元素定义为一个元素出现次数超过数组长度的一半。它并不一定能找到频率最高的元素例如在数组 [1, 2, 2, 3, 3, 3] 中频率最高的元素是 3但没有元素出现次数超过数组长度的一半因此投票法不会返回任何元素。如果数组 [1, 1, 2, 2, 3, 3, 3, 3] 中频率最高的元素也是主要元素这时投票法会返回元素 3。
示例
class Solution {
public:int majorityElement(vectorint nums) {int count 0;int candidate 0;for(int num : nums){if (count 0) {candidate num; // 当前候选主要元素}count (num candidate) ? 1 : -1; // 如果当前元素等于候选主要元素票数加1否则减1}return candidate; // 返回最后的候选主要元素}
};
