东台网站设计,网站的制作建站人,游戏app软件定制开发,注册商标查询网目录 100162.最大频率元素计数
原题链接
思路分析
AC代码
100165.找出数组中的美丽下标I
原题链接
思路分析
AC代码
100160. 价值和小于等于 K 的最大数字
原题链接
思路分析
位运算二分
AC代码
100207.找出数组中的美丽下标II
原题链接
思路分析
AC代码 10016…目录 100162.最大频率元素计数
原题链接
思路分析
AC代码
100165.找出数组中的美丽下标I
原题链接
思路分析
AC代码
100160. 价值和小于等于 K 的最大数字
原题链接
思路分析
位运算二分
AC代码
100207.找出数组中的美丽下标II
原题链接
思路分析
AC代码 100162.最大频率元素计数
原题链接
100162. 最大频率元素计数
思路分析
签到题没什么好说的统计频次最大频次为ma的话记录频次为ma的数字个数
AC代码
class Solution {
public:int maxFrequencyElements(vectorint nums) {int hash[101]{0} , ma 0 , ret 0;for(auto x : nums) ma max(ma , hash[x]);for(auto x : hash) if(x ma) ret ma;return ret;}
}; 100165.找出数组中的美丽下标I
原题链接
100165. 找出数组中的美丽下标 I
思路分析
和第四题一模一样只不过第四题数据范围大这道题为了省时间直接用python3跑的没用C敲KMP具体题解看第四题
这道题由于数据量小查一个i查一个j就行
AC代码
class Solution:def beautifulIndices(self, s: str, a: str, b: str, k: int) - List[int]:idx 0ret []while idx len(s):i s.find(a , idx)if i -1:breakj s.find(b , i - k if i k else 0)if j ! -1 and abs(j - i) k:ret.append(i)idx i 1return sorted(ret) 100160. 价值和小于等于 K 的最大数字
原题链接 100160. 价值和小于等于 K 的最大数字
思路分析
位运算二分
写题解的时候瞄了眼力扣题解区那边一堆数位DP二分的其实个人感觉用不上数位DP其实就是一个位运算的小tip。
比赛的时候看到题目首先能想到二分那么问题就落在了二分的可行性判断上。
对于给定一个数字num如何求出1 到 num的价值和
其实很容易算的如果给你一个数字x问你1到x有多少偶数想都不用想是x / 2向下取整
如果是奇数那就是x / 2 (x 1)
那么扩展为1到x有多少第i位i从低到高为1的数字呢
假设mask (1 (i - 1))注意1左移i - 1位得到的才是第i位为1
那么 sumi (x / (mask 1)) * mask ((mask x) ? ((x (mask - 1)) 1) : 0)
逐步分析下这个方程什么意思
加号右边如果第i位为0那就不说了第i位为1假设从最高位到第0位为:xxxxx1xxxxx那么
从xxxxx100000 ~ xxxxx1xxxxx都是第i位为1且都不超过x
加号左边0到x包含了 00000 1 00000~00000 1 11111、00001 1 00000 ~ 00001 1 11111……
其实就是算比第i位高的位的贡献一个位贡献了1 i
那么我们可以在O(1)内计算出给定范围内i位为1的数字数目继而能在O(C)内算出每一位为1的数字数目其中C为x的位数
那么二分的check函数就能写出来了二分跑一下即可
AC代码
class Solution {
public:typedef long long ll;const ll maxn 1e15;bool check(ll x, ll k, ll y){ll s 0, mask (1LL (y - 1));while (mask x) {s (x / (mask 1)) * mask ((mask x) ? ((x (mask - 1)) 1) : 0);mask y;}return s k;}long long findMaximumNumber(long long k, int x) {ll l 0, r maxn , ans 0;while (l r){ll mid (l r) 1;if (check(mid, k, x))ans mid , l mid 1;elser mid;}return ans;}
}; 100207.找出数组中的美丽下标II
原题链接
100207. 找出数组中的美丽下标 II
思路分析
我们通过KMP可以O(n)求出s中所有子串a的下标也可以求出所有子串b的下标
就是KMP常用操作把子串后面添加一个非法字符这样next数组就变成长度为模式串的了匹配到一个模式串模式串就回退就行
假如我们数组idxa存了子串a的下标idxb存了子串b的下标
对于idxa中每一个i我们都在idxb去二分查找一个在i上下浮动k范围内的j然后记录即可
这样甚至不用排序了还
整体而言这道题比上一道简单因为上一道check函数细节很容易错
就是KMP板子题
AC代码
void get_nextval(const string src, vectorint nextval)
{int j 0, k -1;nextval[0] -1;while (j (int)src.size() - 1){if (k -1 || src[j] src[k]){j; k;if (src[j] ! src[k])nextval[j] k;elsenextval[j] nextval[k];}else{k nextval[k];}}
}int index_KMP(vectorint idx , vectorint next, const string dst, const string src, int pos 0)
{int i pos, j 0;while (i (int)dst.size() j (int)src.size()){if (j -1 || dst[i] src[j]){i; j;if(j (int)src.size())idx.emplace_back(i - j) , j next[j];}else{j next[j];}}if (j (int)src.size())return i - j;elsereturn -1;
}
class Solution {
public:Solution(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);}vectorint beautifulIndices(const string s, const string a, const string b, int k) {int n s.size();vectorint ret, idxa, idxb;string aa(a #) , bb(b #);vectorint nxt1(a.size() 1), nxt2(b.size() 1);get_nextval(aa, nxt1), get_nextval(bb, nxt2);;index_KMP(idxa , nxt1, s, a, 0);index_KMP(idxb , nxt2, s, b, 0);if (idxa.empty() || idxb.empty()) return {};for (auto x : idxa){auto it lower_bound(idxb.begin(), idxb.end(), x k ? x - k : 0);if (it idxb.end()) continue;if (abs(x - *it) k) ret.emplace_back(x);}return ret;}
};
