当前位置: 首页> 科技> 名企 > 重庆大渝网最新消息_公众号文章怎么写_百度指数下载app_安卓优化大师下载

重庆大渝网最新消息_公众号文章怎么写_百度指数下载app_安卓优化大师下载

时间:2025/7/11 11:10:24来源:https://blog.csdn.net/qq_45371462/article/details/147578883 浏览次数:0次
重庆大渝网最新消息_公众号文章怎么写_百度指数下载app_安卓优化大师下载

【LeetCode 438】找到字符串中所有字母异位词

题面:

在这里插入图片描述

思路:

哈希表+滑动窗口:也可用于 567
哈希表记录滑动窗口内字符个数,easy不详细赘述,俺代码可以继续优化,这里用了两个哈希表去做对比,可以优化成一个哈希表上的加减,当 h a s h [ c ] = = 0 hash[c]==0 hash[c]==0 时,说明当前字符 c c c 在字符串 p p p 和滑动窗口内出现的次数相同。

代码:

vector<int> findAnagrams(string s, string p) {int n= (int)p.size();vector<int> hashP(26);vector<int> hash(26);vector<int> res;for(const auto& c : p) ++ hashP[c - 'a'];for(int i = 0, j = 0; j < (int)s.size(); ++j) {while(j - i + 1 > n) --hash[s[i++] - 'a'];hash[s[j] - 'a'] ++;if(j - i + 1 == n) {bool flag = true;for(size_t k = 0; k < 26; ++ k)if(hash[k] != hashP[k]) {flag = false;break;}if(flag) res.push_back(i);}}return res;
}

【LeetCode 567】字符串的排列

题面:

在这里插入图片描述

思路:

统计相同字符+滑动窗口:也可用于 438,微调一下就行

umm看了一下和官方题解差不多,就直接copy它的思路和代码了。

c n t 1 cnt1 cnt1 数组统计字符串 s 1 s1 s1 中各个字符的个数, c n t 2 cnt2 cnt2 数组统计当前字串(滑动窗口内)各个字符的个数。
用变量 d i f f diff diff 统计 c n t 1 cnt1 cnt1 c n t 2 cnt2 cnt2 内不同值的个数。若 d i f f = = 0 diff==0 diff==0 则说明 c n t 1 = = c n t 2 cnt1 == cnt2 cnt1==cnt2,合法;否则说明 c n t 1 ≠ c n t 2 cnt1 \ne cnt2 cnt1=cnt2,当前字串不是 s 1 s1 s1 的排列。

每次滑动窗口一进一出两个字符 x x x y y y
x = y x=y x=y,则 c n t 2 cnt2 cnt2 无变化;
x ≠ y x\ne y x=y,对于字符 x x x,若加入 x x x 之前 c n t 1 [ x ] = c n t 2 [ x ] cnt1[x]=cnt2[x] cnt1[x]=cnt2[x],则说明加入 x x x 之后失衡 d i f f + 1 diff+1 diff+1;若加入 x x x 之后 c n t 1 [ x ] = c n t 2 [ x ] cnt1[x]=cnt2[x] cnt1[x]=cnt2[x],说明加入 x x x 之后 x x x 在字串和 s 1 s1 s1出现的次数相同 d i f f − 1 diff-1 diff1
注意: 可用 c n t [ x ] = c n t 2 [ x ] − c n t 1 [ x ] cnt[x] = cnt2[x] - cnt1[x] cnt[x]=cnt2[x]cnt1[x] 以简化上述流程,将 c n t 1 [ x ] cnt1[x] cnt1[x] c n t 2 [ x ] cnt2[x] cnt2[x] 的比较替换成 c n t [ x ] cnt[x] cnt[x] 0 0 0 的比较。

代码:

bool checkInclusion(string s1, string s2) {int n = (int)s1.size(), m = (int)s2.size();if(n > m) return false;vector<int> cnt(26);int diff = 0;for(int i = 0; i < n; ++i) {-- cnt[s1[i] - 'a'];++ cnt[s2[i] - 'a'];}for(int c : cnt)if(c) ++ diff;if(!diff) return true;for(int i = n; i < m; ++i) {int x = s2[i] - 'a', y = s2[i - n] - 'a';if(x == y) continue;if(!cnt[x]) ++ diff;if(++ cnt[x] == 0) --diff;if(!cnt[y]) ++ diff;if(-- cnt[y] == 0) --diff;if(!diff) return true;}return false;
}

俺原本的代码:

bool checkInclusion(string s1, string s2) {if(s1.size() > s2.size()) return false;int n = (int)s1.size();unordered_map<int, int> mp;for(const auto& c : s1) ++ mp[c - 'a'];for(int i = 0, j = 0; j < (int)s2.size(); ++j) {while(j - i + 1 > n) {if(mp.find(s2[i] - 'a') != mp.end())mp[s2[i] - 'a'] ++;++i;}// 滑动窗口(字串)只统计在 s1 出现过的字符// 若当前字符 s2[j] 没在 s1 出现过,则继续遍历(因为加入 s2[j] 对结果无贡献)if(mp.find(s2[j] - 'a') != mp.end()) mp[s2[j] - 'a'] --;else continue;if(j - i + 1 == n) {bool flag = true;for(const auto& it : mp)if(it.second != 0) {flag = false;break;}if(flag) return true;}}return false;
}
关键字:重庆大渝网最新消息_公众号文章怎么写_百度指数下载app_安卓优化大师下载

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: