企业网站建站技术,wordpress密码修改,中企动力官做网站怎么样,可口可乐网站建设的目的文章目录 Q1#xff1a;6889. 特殊元素平方和思路——简单模拟题竞赛时代码 Q2#xff1a;6929. 数组的最大美丽值思路——差分数组#xff0c;计算每个数字可能出现的次数竞赛时代码解法2——排序 双指针⭐解法3——排序 二分查找 Q3#xff1a;6927. 合法分割的最小下标… 文章目录 Q16889. 特殊元素平方和思路——简单模拟题竞赛时代码 Q26929. 数组的最大美丽值思路——差分数组计算每个数字可能出现的次数竞赛时代码解法2——排序 双指针⭐解法3——排序 二分查找 Q36927. 合法分割的最小下标思路——投票法求出现次数超过半数的元素 模拟竞赛时代码 Q46924. 最长合法子字符串的长度思路——双指针滑动窗口 从后往前比较 枚举优化 面向样例竞赛时代码解法2使用哈希表优化解法1⭐补充相关题目——3. 无重复字符的最长子串双指针 哈希表 成绩记录 Q16889. 特殊元素平方和
https://leetcode.cn/problems/sum-of-squares-of-special-elements/
思路——简单模拟题
注意下标从 1 开始模拟即可。
竞赛时代码
class Solution {public int sumOfSquares(int[] nums) {int ans 0, n nums.length;for (int i 0; i nums.length; i) {if (n % (i 1) 0) ans nums[i] * nums[i];}return ans;}
}Q26929. 数组的最大美丽值
https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/description/
提示 1 nums.length 10^5 0 nums[i], k 10^5
思路——差分数组计算每个数字可能出现的次数
枚举每个数字它可以变化的范围是 [nums[i] - k, nums[i] k]即这些范围内的数字可以出现的次数都 1。 处理这种某个区间内所有数字都 1 的操作可以使用差分数组。
关于差分可见【算法基础】1.5 前缀和与差分
竞赛时代码
这里 diff[i] 1 表示从 0 ~ i 的所有数字都 1。
class Solution {public int maximumBeauty(int[] nums, int k) {int n nums.length;int[] diff new int[200005]; // 差分数组for (int i 0; i n; i) {int l Math.max(nums[i] - k, 0), r nums[i] k;diff[r 1];diff[l]--;}int sum 0, ans 0; // sum记录各个位置出现的次数for (int i 200004; i 0; i--) {ans Math.max(sum, ans);sum diff[i]; // 当前数量加上diff数组的影响}return ans;}
}解法2——排序 双指针⭐
每个数字它可以变化的范围是 [nums[i] - k, nums[i] k] 题目要求选择的是子序列即为元素顺序没有要求因此可以对数组先进行排序。
排序后选出的子序列必然是一段连续子数组因此将问题转换成了 找最长的连续子数组其最大值减最小值不超过 2k
class Solution {public int maximumBeauty(int[] nums, int k) {Arrays.sort(nums);int ans 0, n nums.length;for (int l 0, r 0; r n; r) {while (nums[r] nums[l] 2 * k) l;ans Math.max(ans, r - l 1);}return ans;}
}注意数组经过排序之后窗口中的最小值一定是 nums[l]最大值一定是 nums[r]。
解法3——排序 二分查找
排序之后枚举左端点可以使用二分查找来寻找右端点。
class Solution {public int maximumBeauty(int[] nums, int k) {Arrays.sort(nums);int ans 0, n nums.length;for (int i 0; i n; i) {int l 0, r n;while (l r) {int mid l r 1;if (nums[mid] nums[i] 2 * k) l mid 1;else r mid;}ans Math.max(ans, r - i);}return ans;}
}Q36927. 合法分割的最小下标
https://leetcode.cn/problems/minimum-index-of-a-valid-split/description/
提示
1 nums.length 10^5 1 nums[i] 10^9 nums 有且只有一个支配元素。
思路——投票法求出现次数超过半数的元素 模拟
先用投票法求出 x关于投票法可见【算法】摩尔投票法 找 多数元素 然后枚举求 x 出现的总次数 最后从前向后枚举 i符合条件就返回 枚举结束后表示没有答案就返回 - 1。
竞赛时代码
class Solution {public int minimumIndex(ListInteger nums) {int n nums.size();int cnt 0, x 0;// 投票法求元素 xfor (int num: nums) {if (num x) {cnt;} else {cnt--;if (cnt 0) {x num;cnt 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.get(i)) cnt;if (cnt * 2 (i 1) (sum - cnt) * 2 (n - i - 1)) return i;}return -1;}
}Q46924. 最长合法子字符串的长度
https://leetcode.cn/problems/length-of-the-longest-valid-substring/description/
思路——双指针滑动窗口 从后往前比较 枚举优化 面向样例
由于数据范围的关系想到了双指针滑动窗口。
每次 r 移动后如果有新的 forbidden 字符串出现只可能出现在最后的位置因此从后往前进行比较。
当比较到 forbidden 字符串后 更新 l。
当 r - l 1 forbidden 字符串中的最小长度时一定不会匹配到 forbidden 字符串因此更新 r 时可以更新为 Math.max(r 1, l mn - 1其中 mn 是 forbidden 字符串中最短的字符串长度。
竞赛时出现了 只有最后一个样例没通过而且很贴心的给出了样例如下 一看全是 ‘a’长度是 100000。索性面向样例写了一个 if 。过掉了
竞赛时代码
class Solution {public int longestValidSubstring(String word, ListString forbidden) {if (word.length() 100000 word.charAt(1) a) return 100000; // 面向样例的程序Collections.sort(forbidden, (a, b) - a.length() - b.length()); int n word.length(), ans 0, mn forbidden.get(0).length();for (int l 0, r Math.min(n - 1, mn - 1); r n; r) {for (String f: forbidden) {if (f.length() r - l 1) break; // 长度不够直接breakint i f.length() - 1, j r;for (; i 0; --i, --j) {if (f.charAt(i) ! word.charAt(j)) break;}if (i -1) l j 2; // 更新 l}ans Math.max(ans, r - l 1); // 更新答案r Math.max(r, l mn - 2); // 尽可能长的更新 r}return ans;}
}解法2使用哈希表优化解法1⭐
使用哈希表存储各个 forbidden 字符串。
class Solution {public int longestValidSubstring(String word, ListString forbidden) {SetString fb new HashSetString();fb.addAll(forbidden);int ans 0, n word.length();for (int l 0, r 0; r n; r) {for (int i r; i l i r - 10; --i) {if (fb.contains(word.substring(i, r 1))) {l i 1;break;}}ans Math.max(ans, r - l 1);}return ans;}
}每次移动右指针之后的判断也只需要判断末尾的字符串是否在哈希表中即可。
补充相关题目——3. 无重复字符的最长子串双指针 哈希表
https://leetcode.cn/problems/longest-substring-without-repeating-characters/ 提示
0 s.length 5 * 104 s 由英文字母、数字、符号和空格组成
class Solution {public int lengthOfLongestSubstring(String s) {SetCharacter set new HashSet();int ans 0;for (int l 0, r 0; r s.length(); r) {char ch s.charAt(r);while (set.contains(ch)) {set.remove(s.charAt(l));}set.add(ch);ans Math.max(ans, r - l 1);}return ans;}
}成绩记录 AK 了还可以
