LeetCode刷题——找到字符串中所有字母异位词

标签: LeetCode  hash

大家好,继续刷题,已经刷到了哈希表的部分,感觉这道题还是学到了很多,记录一下。

题目要求:

思路:1.我自己想的办法很笨,最终超时了,就是把s分成一个一个子字符串,然后跟p一起sort一下,然后看一不一样。代码如下:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        int len = s.size();
        int len_p = p.size();
        if(len == 0)
            return result;
        string temp;
        map<int,string> hash;
        for(int i = 0;i <= len - len_p;i++){
            temp = s.substr(i,len_p);
            hash.insert(pair<int,string> (i,temp));
            temp.clear();
        }
        map<int,string> :: iterator it = hash.begin();
        while(it != hash.end()){
            string t = it -> second;
            sort(t.begin(),t.end());
            sort(p.begin(),p.end());
            if(t == p){
                result.push_back(it -> first);
            }
            it++;
        }
        return result;
    }
};

2.然后去看了其他大大们写的代码,学习了很多,其中一种思想是获取s的子字符串然后计算里面字母的个数,比较跟p的字母个数是否一样就可以了,很巧妙,但这种思想也分两种办法,一种是用map来存放子字符串和p的字母及其个数,但是后续查看是否一样还需要遍历查找啊什么的就很麻烦,还有一种是用vector来存放子字符串和p的字母及其个数,vector相比map,使用起来就很灵活,速度也更快。代码如下。

map版:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int plen=p.size(),slen=s.size();
        vector<int> res;
        if(slen < plen) {return res;}
        map<char,int> mp;
        for(auto c:p) {
            mp[c]++;
        }
        for(int i=0;i<slen-plen+1;i++){
            map<char,int> temp;
            string substri=s.substr(i,plen);
            for(auto c:substri) temp[c]++;
            if(mapequal(temp,mp)) 
                res.push_back(i);
        }
        return res;
    }

    bool mapequal(map<char,int>& a,map<char,int>& b){
        if(a.size()!=b.size()) return false;
        map<char,int>::iterator iter;
        for(iter=a.begin(); iter!=a.end(); iter++){
            if(b.count(iter->first)==0||b[iter->first]!=iter->second)
                return false;
        }
        return true;
    }
};

vector版:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> pv(26,0), sv(26,0), res;
        if(s.size() < p.size())
           return res;
        for(int i = 0; i < p.size(); ++i)
        {
            ++pv[p[i]-'a'];
            ++sv[s[i]-'a'];
        }
        if(pv == sv)
           res.push_back(0);

        for(int i = p.size(); i < s.size(); ++i) 
        {
            ++sv[s[i]-'a'];
            --sv[s[i-p.size()]-'a']; 
            if(pv == sv)  
               res.push_back(i-p.size()+1);
        }
        return res;
    }
};

学到的东西有:

1.map的遍历:

for(iter=a.begin(); iter!=a.end(); iter++){
    if(b.count(iter->first)==0||b[iter->first]!=iter->second)
        return false;
    }

这里string::count()只是统计是否有字符,有就是返回1,无就是返回0。

2.for循环的用法:

for(auto c:s)//对于s中的每个字符

此处表示对s进行循环,c表示从0开始到len-1。

3.并不要盲目使用容器,最合适的才是最好的。

 

我们下期见。

版权声明:本文为Miss_yuki原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Miss_yuki/article/details/81458022

智能推荐

java乐观锁和悲观锁最底层的实现

1. CAS实现的乐观锁 CAS(Compare And Swap 比较并且替换)是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的,也可以理解为自旋锁 JUC是指import java.util.concurrent下面的包, 比如:import java.util.concurrent.atomic.AtomicInteger; 最终实现是汇编指令:lock...

Python 中各种imread函数的区别与联系

  原博客:https://blog.csdn.net/renelian1572/article/details/78761278 最近一直在用python做图像处理相关的东西,被各种imread函数搞得很头疼,因此今天决定将这些imread总结一下,以免以后因此犯些愚蠢的错误。如果你正好也对此感到困惑可以看下这篇总结。当然,要了解具体的细节,还是应该 read the fuc...

用栈判断一个字符串是否平衡

注: (1)本文定义:左符号:‘(’、‘[’、‘{’…… 右符号:‘)’、‘]’、‘}’……. (2)所谓的字符串的符号平衡,是指字符串中的左符号与右符号对应且相等,如字符串中的如‘(&r...

JAVA环境变量配置

位置 计算机->属性->高级系统设置->环境变量 方式一 用户变量新建path 系统变量新建classpath 方式二 系统变量 新建JAVA_HOME,值为JDK路径 编辑path,前加 方式三 用户变量新建JAVA_HOME 此路径含lib、bin、jre等文件夹。后运行tomcat,eclipse等需此变量,故最好设。 用户变量编辑Path,前加 系统可在任何路径识别jav...

常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器,其它的相对用的就不会那么多了,当然属性选择器和为类选择器用的也会比较多,这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器? CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签(链接)上的为类选择器。 当我们使用它们的时候,需要遵循一定的顺序问题,否则将可能出现bug 注意...

猜你喜欢

ButterKnife的使用介绍及原理探究(六)

前面分析了ButterKnife的源码,了解其实现原理,那么就将原理运用于实践吧。 github地址:       点击打开链接 一、自定义注解 这里为了便于理解,只提供BindView注解。 二、添加注解处理器 添加ViewInjectProcessor注解处理器,看代码, 这里分别实现了init、getSupportedAnnotationTypes、g...

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。考试复习题库1|要求:只能使用单字符比较操作。

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。 要求只能使用单字符比较操作。 参考代码: 实验结果截图:...

小demo:slideDown()实现二级菜单栏下拉效果

效果如下,鼠标经过显示隐藏的二级菜单栏 但是这样的时候会存在一个问题,就是鼠标快速不停移入移出会导致二级菜单栏闪屏现象,一般需要使用stop()来清除事件  ...

基于docker环境的mysql主从复制

1、安装docker 可以参考之前的博客,之前写过了~ 2、拉取mysql镜像 3、创建mysql01和mysql02实例 主: 从: 4、进入容器修改配置 1)修改主数据库配置 进入主数据库容器 切换到 etc/mysql/目录下 查看可以看到my.cnf文件,使用vim编辑器打开,但是需要提前安装 安装vim命令: 安装成功后,修改my.cnf文件 新增配置后的my.cnf: binlog 日...

机器学习算法之决策树

原文:http://www.jianshu.com/p/6eecdeee5012 决策树是一种简单高效并且具有强解释性的模型,广泛应用于数据分析领域。其本质是一颗由多个判断节点组成的树,如: 决策树 在使用模型进行预测时,根据输入参数依次在各个判断节点进行判断游走,最后到叶子节点即为预测结果。 如何构造决策树 决策树算法的核心是通过对数据的学习,选定判断节点,构造一颗合适的决策树。 假设我们从用户...