力扣hot100:438.找到字符串中所有字母异位词

2024-03-05 10:04

本文主要是介绍力扣hot100:438.找到字符串中所有字母异位词,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

26个字符,我复制怎么了?26个字符我比较个数怎么了? 顶多时间复杂度*26

本题用固定窗口大小的滑动窗口+每次比较包含26个元素的数组次数,最容易写。

动态窗口大小+哈希表存数值(双指针差值)难想难写。

一、动态滑动窗口+哈希表(双指针)

        这个问题,刚开始想的是,维护一个滑动窗口,左指针left,右指针right,左指针往右走从集合中拿走这个字符,右指针往右走在集合中加入这个字符,但是由于p可能有多个重复字符,这使得我们不得不记录字符的个数了。那,我们记录个数的话,怎么记录呢?可以用哈希表存储该字符的个数,如果集合中加入一个字符,字符个数就减1,直至哈希表中没有元素则说明匹配成功,但是匹配了一次之后呢? 重新复制一次不得了,最多26个字符!

        不过这里需要注意的是,当匹配成功后,左右指针都只能往后移动一次,只有当右指针遇到的字符不在目标字符串中时,才复制一次,完全重开。

        这里的字符个数完全确定,最好使用vector<int>,查找更快。

class Solution {
public:vector<int> findAnagrams(string s, string p) {int left=0;int right=0;unordered_map<char,int> source;for(auto &i:p) source[i]+=1;//可以复制,就26个字母,我复制怎么了?vector<int> ans;unordered_map<char,int> hmap(source);while(right<s.size()){if(hmap.find(s[right])!=hmap.end()){//在里面hmap[s[right]]-=1;if(hmap[s[right]]==0) hmap.erase(s[right]);if(hmap.size()==0){ans.emplace_back(left);hmap[s[left++]]=1;}++right;}else{if(source.find(s[right])!=source.end()){//它在源头里面 可能有点用的hmap[s[left++]]+=1;}else {hmap=source;//注意这里! 这里得还原了left=++right;}}}return ans;}
};

vector实现:

class Solution {
public:vector<int> findAnagrams(string &s, string &p) {if(s.size()<p.size()) return {};vector<int> cnt_s(26);vector<int> cnt_p(26);vector<int> ans;vector<int> zero(26);for(char &i:p) ++cnt_p[i-'a'];cnt_s=cnt_p;int left=0,right=0;while(right<s.size()){if(cnt_s[s[right]-'a']>0){--cnt_s[s[right]-'a'];++right;}else{if(cnt_p[s[right]-'a']>0){cnt_s[s[left]-'a']++;++left;}else{cnt_s=cnt_p;left=right=right+1;}}if(cnt_s==zero) ans.push_back(left);}return ans;}
};

二、固定滑动窗口

这里实际上就是上述方法用vector实现的。由于是26个字符,直接比较就行了。

class Solution {
public:vector<int> findAnagrams(string &s, string &p) {if(s.size()<p.size()) return {};vector<int> source(26);vector<int> hmap(26);vector<int> ans;for(int i=0;i<p.size();++i){hmap[s[i]-'a']+=1;source[p[i]-'a']+=1;}int left=0,right=p.size();while(right<s.size()){if(hmap == source) ans.emplace_back(left);hmap[s[left++]-'a']-=1;hmap[s[right++]-'a']+=1;}if(hmap == source) ans.emplace_back(left);return ans;}
};

这篇关于力扣hot100:438.找到字符串中所有字母异位词的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/776149

相关文章

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

C和指针:字符串

字符串、字符和字节 字符串基础 字符串就是一串零个或多个字符,并且以一个位模式为全0的NUL字节结尾。 字符串长度就是字符串中字符数。 size_t strlen( char const *string ); string为指针常量(const修饰string),指向的string是常量不能修改。size_t是无符号数,定义在stddef.h。 #include <stddef.h>

PHP字符串全排列

方法一: $str = 'abc';$a =str_split($str);perm($a, 0, count($a)-1);function perm(&$ar, $k, $m) {if($k == $m){ echo join('',$ar), PHP_EOL;}else {for($i=$k; $i<=$m; $i++) {swap($ar[$k], $ar[$i]);perm($ar

PHP7扩展开发之字符串处理

前言 这次,我们来看看字符串在PHP扩展里面如何处理。 示例代码如下: <?phpfunction str_concat($prefix, $string) {$len = strlen($prefix);$substr = substr($string, 0, $len);if ($substr != $prefix) {return $prefix." ".$string;} else

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

十一、C语言:字符串函数

目录 一、strlen 二、strcpy 三、strcat  四、strcmp 五、strstr 六、strtok 七、strerror 一、strlen 注意:strlen()函数的返回值是size_t,两个size_t相减仍为无符号数 int main(){char arr[10] = "abc";char brr[10] = "abc123";if (strl

Collection的所有的方法演示

import java.util.ArrayList;import java.util.Collection;import java.util.Iterator;public class TestCollection {/*** @param args* Collection的所有的方法演示* 此程序没有使用泛型,所以可以添加任意类型* 以后如果写到泛型会补充这一方面的内容*/public s

Temu官方宣导务必将所有的点位材料进行检测-RSL资质检测

关于饰品类产品合规问题宣导: 产品法规RSL要求 RSL测试是根据REACH法规及附录17的要求进行测试。REACH法规是欧洲一项重要的法规,其中包含许多对化学物质进行限制的规定和高度关注物质。 为了确保珠宝首饰的安全性,欧盟REACH法规规定,珠宝首饰上架各大电商平台前必须进行RSLReport(欧盟禁限用化学物质检测报告)资质认证,以确保产品不含对人体有害的化学物质。 RSL-铅,