【每日刷题】Day106
【每日刷题】Day106
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. LCR 015. 找到字符串中所有字母异位词 - 力扣（LeetCode）
2. 30. 串联所有单词的子串 - 力扣（LeetCode）
3. 69. x 的平方根 - 力扣（LeetCode）
1. LCR 015. 找到字符串中所有字母异位词 - 力扣（LeetCode）
//思路一：无优化版滑动窗口+哈希。非常慢。
class Solution {
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ans;
int hash[127] = {0};
int i = 0,j = 0,psize = p.size();//psize用于判断是否找到了异位词
//记录p中出现的字母及个数
for(int n = 0;n<p.size();n++)
{
hash[p[n]] += 1;
}
while(s.size()-i>=p.size()&&j<s.size())
{
//如果s中当前字母在p中出现，继续遍历
if(hash[s[j]])
{
hash[s[j]]--;
j++;
psize--;
}
//找到异位词的情况
else if(!hash[s[j]]&&!psize)
{
ans.push_back(i);
//重置哈希表
for(int n = 0;n<p.size();n++)
{
hash[p[n]] += 1;
}
psize = p.size();
i++;
while(i<s.size()&&!hash[s[i]]) i++;
j = i;
}
//没找到异位词的情况
else
{
for(int x = 0;x<127;x++)
{
if(hash[x]) hash[x] = 0;
}
for(int n = 0;n<p.size();n++) hash[p[n]] += 1;
//这里相当于O(N^2)的时间复杂度了
j = ++i;
psize = p.size();
}
}
if(!psize) ans.push_back(i);
return ans;
}
};
//思路二：优化版滑动窗口+哈希。非常快
//我们利用两个哈希表，hash1和hash2，来比较两个字串是否相同，再使用一个变量psize用于记录字符串p的长度。
//hash1初始记录p中出现的字母及个数，后续操作不需要改变hash1
//hash2初始记录s中前psize个字母及个数，后续需要不断改变hash2，具体如何改变，看图：
class Solution {
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ans;
int hash1[127] = {0};
int hash2[127] = {0};
//hash1记录p中所有字母及每个字母的个数
for(int n = 0;n<p.size();n++) hash1[p[n]]++;
int i = 0,j = p.size()-1;
//hash2初始记录s中前psize个字母及每个字母的个数，后续会不断改变
for(int m = 0;m<=j;m++) hash2[s[m]]++;
while(s.size()-i>=p.size())
{
//通过判断hash1内存是否与hash2相同来判断是否找到了异位词
if(memcmp(hash1,hash2,sizeof(int)*127)==0) ans.push_back(i);
//窗口滑动
hash2[s[i++]]--;
hash2[s[++j]]++;
}
return ans;
}
};
2. 30. 串联所有单词的子串 - 力扣（LeetCode）
//思路：滑动窗口+哈希表容器。
//本题还是很难的，不过思路并不是难点，难点在于细节的处理上，本题的思路与上面那一题是一样的，只不过滑动窗口维护的对象从单个字母变成多个字母。
//先来画图看一下本题的思路：
//但是如何将多个字母看作为一个字母呢？这里我们需要借助unordered_map这个容器，这个容器可以帮助我们计算字符串出现的频次
//当到这一步后，我们就可以着手开始写代码了
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> ans;
//借助容器，记录words中字符串出现的频次
unordered_map <string,int> hash1;
for(auto& s : words) hash1[s]++;
//获取words每个字符串的长度，以及words的长度，后面有用
int len = words[0].size(),size = words.size();
//这一步就是细节上的处理了，因为我们不一定是在字符串的开头就找到字串，因此我们需要遍历len次，就能确保每一个可能出现字串的位置都找一遍
for(int i = 0;i<len;i++)
{
//hash2用于记录s中当前字符串出现的频次
unordered_map <string,int> hash2;
for(int left = i,right = i,count = 0;right+len<=s.size();right+=len)
{
//in用于获取s中当前字符串，长度与len一致
string in = s.substr(right,len);
//记录出现次数
hash2[in]++;
//判断当前字符串出现次数是否合法，如果合法，则记录一个合法字符串
if(hash2[in]<=hash1[in]) count++;
//当right与left间的字符串长度长于wrods中所有字符串组成的长度后，我们就遍历完了一个可能是符合题意的异位词，将最前面的字符串弹出窗口，同时维护count。如果弹出的是合法的字符串，count--。
if(right-left+1>len*size)
{
string out = s.substr(left,len);
if(hash2[out]<=hash1[out]) count--;
hash2[out]--;
left+=len;
}
//当count==len说明找到了一个符合题意的异位词
if(count==size) ans.push_back(left);
}
}
return ans;
}
};
3. 69. x 的平方根 - 力扣（LeetCode）
//思路：二分查找+二段性。
//我们先从结果入手来分析本题：
//知道了二段性后，我们就可以直接套用非朴素二分查找的模板了
class Solution {
public:
int mySqrt(int x)
{
//处理边界情况
if(x<1) return 0;
int left = 1,right = x;
while(left<right)
{
//防止整形溢出
long long mid = left+(right-left+1)/2;
//定位区间
if(mid*mid<=x) left = mid;
else right = mid-1;
}
return left;
}
};