每日算法刷题Day21 6.3:leetcode二分答案2道题，用时1h20min(有点慢)
3. 2982.找出出现至少三次的最长特殊子字符串II(中等,学习)
https://leetcode.cn/problems/find-longest-special-substring-that-occurs-thrice-ii/
思想
1.给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
2.单调性检验:长度越大，越不可能出现至少三次，而一旦满足条件，长度更小的一定满足条件
3.我的思想:用长度mid提取子串t，然后把用个函数判断是不是特殊字符串，函数逻辑是用unordered_set来判断，如果子串是特殊字符串，再用unordered_map来记录次数，判断是否大于3，但会超时
4.学习别人的思想:因为要判断某个字符的特殊子字符串出现次数，所以可以用unordered_map<char, vector<int>> mp; 先存储字符-长度数组，从而得到每种字符各自连续的子串长度，然后先遍历每种字符，此时的子串长度为x,如果x大于等于mid,那么就能得到x-mid+1个特殊字符串了，从而判断与3的大小，但因为每种字符是独立的，所以更新答案是res=max(res,mid)
5.学习分类讨论思想:
因为题目说明特殊字符串出现至少三次，那么就当三次来算，那么有哪些方法能够提取出三个特殊子串呢？可以考虑该字符子串的最长三个长度l0,l1,l2(满足l0>=l1>=l2)即可:
- 从最长的l0取三个长度l0-2的子串
- 从l0和l1取三个
- l0=l1,取三个长度l0-1的子串(此时l0-1<l1)
- l0>l1,取三个长度l1的子串(此时l0-1>=l1)
- 所以合起来就是取长度min(l0-1,l1)的子串
- 从l0,l1,l2取三个长度为l2的子串
上面三种情况取最大的，即max(l0-2,min(l0-1,l1),l2),如果答案为0则说明不存在，返回-1
代码
c++:
学习
class Solution {
public:bool check(int mid, vector<int>& vec) {int cnt = 0;for (const int x : vec) {if (x >= mid) {cnt +=x - mid +1; // 字符串长度为k，最后一个开始位置x-mid,开始位置范围[0,x-mid]共x-mid+1个子串if (cnt >= 3)return true;}}return false;}int maximumLength(string s) {int n = s.size();int res = -1;unordered_map<char, vector<int>> mp; // 字符-长度for (int i = 0, j = 0; i < n; i = j) {while (j < n && s[i] == s[j])++j;mp[s[i]].emplace_back(j - i); //[i,j)}// 遍历每种字符for (const auto x : mp) {char c = x.first;auto vec = x.second;int left = 1, right = n - 2;while (left <= right) {int mid = left + ((right - left) >> 1);int cnt = 0;for (const int v : vec) {if (v >= mid) {cnt +=v - mid +1; // 最后一个开始位置v-mid,开始位置范围[0,v-mid]共v-mid+1个子串}}if (check(mid, vec)) {res = max(res, mid); // 因为遍历每种字符left = mid + 1;} elseright = mid - 1;}}return res;}
};
学习分类讨论:
class Solution {
public:int maximumLength(string s) {int n = s.size();int res = -1;unordered_map<char, vector<int>> mp; // 字符-长度for (int i = 0, j = 0; i < n; i = j) {while (j < n && s[i] == s[j])++j;mp[s[i]].emplace_back(j - i); //[i,j)}// 遍历每种字符for (const auto x : mp) {char c = x.first;auto vec = x.second;// 假设还有两个空串，确保能取到三个vec.emplace_back(0);vec.emplace_back(0);sort(vec.begin(), vec.end(), greater<int>()); // 降序排序res = max({res, vec[0] - 2, min(vec[0] - 1, vec[1]), vec[2]});}if (res == 0)return -1;return res;}
};
学习:max({})的{}是初始化列表，可以比较多个值
4. 2576.求出最多标记下标(中等)
2576. 求出最多标记下标 - 力扣（LeetCode）
思想
1.给你一个下标从 0 开始的整数数组 nums 。
一开始，所有下标都没有被标记。你可以执行以下操作任意次：
- 选择两个 互不相同且未标记 的下标
i和j，满足2 * nums[i] <= nums[j]，标记下标i和j。
请你执行上述操作任意次，返回nums中最多可以标记的下标数目。
2.单调性检验:下标数目越多，越不可能满足条件，所以存在一个最多下标数目，而一旦一个下标数目满足，那么比它小的肯定成立
3.我的思想原来是排序完双指针(没写出来)，右指针找到第一个满足2*nums[0]<=nums[start]的位置，但是会出错，因为其实是贪心思想，让[0,mid)和[n-mid,n)(即最小的mid个和最大的mid个)配对，因为0和n-mid能配对，那么肯定能和大于n-mid的配对，但是是浪费
4.学习同向双指针思想:
还是右指针找到第一个满足2*nums[0]<=nums[start]的位置，但是此时匹配的时候左半部分只有满足2*nums[i]<=nums[j]的时候i才能自增，左边区间是连续的，为[0,i]，所以答案就是i*2,但是右半区间不是连续的(原来认为连续)，是for循环一直自增的
代码
c++:
class Solution {
public:bool check(vector<int>& nums, int mid) {int n = nums.size();//[0,mid)与[n-mid,n)配对for (int i = 0; i < mid; ++i) {if (2 * nums[i] > nums[n - mid + i])return false;}return true;}int maxNumOfMarkedIndices(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());int res = 0;int left = 0, right = n / 2;while (left <= right) {int mid = left + ((right - left) >> 1);if (check(nums, mid)) {res = 2 * mid;left = mid + 1;} elseright = mid - 1;}return res;}
};
学习同向双指针:
class Solution {
public:int maxNumOfMarkedIndices(vector<int>& nums) {sort(nums.begin(), nums.end());int n = nums.size();int res = 0;// 从一半位置开始for (int j = (n + 1) / 2; j < n; ++j) { // 不是n/2// 满足条件拓宽左半区间if (2 * nums[res] <= nums[j])++res;}return 2 * res;}
};