题解 | #查找兄弟单词#

查找兄弟单词

http://www.nowcoder.com/practice/03ba8aeeef73400ca7a37a5f3370fe68

题目的主要信息:

  • 兄弟单词为只通过交换该单词字母顺序就可以变为待查找单词相同。同时,兄弟单词要求和原来的单词不同。
  • 输入n个单词,从中找出所有的兄弟单词,输出兄弟单词的数量,以及输出指定的兄弟单词。

方法一:

遍历一遍所有单词,逐个判断当前单词words[i]是否为str的兄弟单词,若为兄弟单词则把它加到bros数组中,最后判断bros的大小,若为0,则表示没有兄弟单词,否则按照索引输出指定的兄弟单词。判断两个单词是否为兄弟单词,只需要对两个字符串的字符按照字母表排序,若排序后两个单词相同则为兄弟单词,前提是这两个单词不相同。同时需要注意的是,指定的兄弟单词索引是从1开始的,实际在bros中的索引应该为index-1。 alt

具体做法:

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

bool isBrother(string str1, string str2){//判断是否为兄弟单词
    if(str1!=str2){//首先这两个单词不能相同
        sort(str1.begin(),str1.end());
        sort(str2.begin(),str2.end());
        //比较排序后的两个单词,若相同则为兄弟单词
        return str1==str2;
    }else return false;
}

int main(){
    vector<string> words;//保存所有单词
    vector<string> bros;//保存兄弟单词
    int n;//单词个数
    cin>>n;
    while(n){//逐个储存单词
        string word;
        cin>>word;
        words.push_back(word);
        n--;
    }
    string str;//带查找单词
    int index;//兄弟单词的索引
    cin>>str>>index;
    for(int i=0;i<words.size();i++){//遍历一遍所有单词,将兄弟单词储存出来
        if(isBrother(str,words[i])){
            bros.push_back(words[i]);
        }
    }
    if(bros.size()==0){//没有兄弟单词
        cout<<'0'<<endl;
    }else{
        sort(bros.begin(),bros.end());//对兄弟单词按照字典排序
        cout<<bros.size()<<endl;
        cout<<bros[index-1]<<endl;//索引从1开始,因此需要减1
    }
    return 0;
}

复杂度分析:

  • 时间复杂度:O(nlog2n+nmlog2m)O(nlog_2n+nmlog_2m),对所有兄弟单词按字典排序时sort函数的时间复杂度为O(nlog2n)O(nlog_2n),每一个is_Brother的时间复杂度是O(mlong2m)O(mlong_2m),总共要做n次is_Brother的判断。
  • 空间复杂度:O(n)O(n),最坏情况下,所有单词都是兄弟单词。

方法二:

在判断是否为兄弟单词的时候还可以用计数法,即统计每个26个字母在单词中出现的频数,若两个单词的在26个字母上的频数分布完全相同,切这两个单词本身不相同,那么这两个单词就是兄弟单词。我们用count数组来记录单词在26个字母上的频数分布,用str[i]-'a'来记录相对位置。

具体做法:

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

bool isBrother(string str1, string str2){//判断是否为兄弟单词
    if(str1==str2) return false;//两单词相同不是兄弟单词
    int count1[26]={0};
    int count2[26]={0};
    for(int i=0;i<str1.size();i++){//统计str1中各字母出现的次数
        count1[str1[i]-'a']++;
    }
    for(int i=0;i<str2.size();i++){//统计str2中各字母出现的次数
        count2[str2[i]-'a']++;
    }
    for(int i=0;i<26;i++){//判断str1和str2中字母种类和个数是否完全相同
        if(count1[i]!=count2[i]) return false;
    }
    return true;
}

int main(){
    vector<string> words;//保存所有单词
    vector<string> bros;//保存兄弟单词
    int n;//单词个数
    cin>>n;
    while(n){//逐个储存单词
        string word;
        cin>>word;
        words.push_back(word);
        n--;
    }
    string str;//带查找单词
    int index;//兄弟单词的索引
    cin>>str>>index;
    for(int i=0;i<words.size();i++){//遍历一遍所有单词,将兄弟单词储存出来
        if(isBrother(str,words[i])){
            bros.push_back(words[i]);
        }
    }
    if(bros.size()==0){//没有兄弟单词
        cout<<'0'<<endl;
    }else{
        sort(bros.begin(),bros.end());//对兄弟单词按照字典排序
        cout<<bros.size()<<endl;
        cout<<bros[index-1]<<endl;//索引从1开始,因此需要减1
    }
    return 0;
}

复杂度分析:

  • 时间复杂度:O(nlog2n+nm)O(nlog_2n+nm),sort函数的时间复杂度为O(nlog2n)O(nlog_2n),isBrother函数需要遍历一遍当前字符串,时间复杂度为O(m)O(m),总共需要遍历n'次。
  • 空间复杂度:O(n)O(n),最坏情况下,所有单词都是兄弟单词。
全部评论

相关推荐

03-15 00:45
已编辑
中国科学院大学 Java
问的很简单都秒了,但是面试官没开摄像头,疑似kpi,无后续。--------------------3/14更新,3/12通知给了口头offer,3/13发了意向书,已拒。一面(35min)(25/3/6)(无后续)&nbsp;&nbsp;&nbsp;&nbsp;1、自我介绍&nbsp;&nbsp;&nbsp;&nbsp;2、介绍一下你的那个Python相关项目(本科毕设,web系统+算法模型提供部分接口)&nbsp;&nbsp;&nbsp;&nbsp;3、Java面向对象有哪些特点呢?详细说一下。&nbsp;&nbsp;&nbsp;&nbsp;4、介绍一下hashmap;为什么要把链表转换为红黑树呢?红黑树查找的时间复杂度?1.7和1.8的区别。&nbsp;&nbsp;&nbsp;&nbsp;5、介绍一下concurrentHashmap。&nbsp;&nbsp;&nbsp;&nbsp;6、synchronized锁和Lock锁有什么区别?&nbsp;&nbsp;&nbsp;&nbsp;7、公平锁的一个底层是怎么实现的呢?&nbsp;&nbsp;&nbsp;&nbsp;8、线程池的核心参数、拒绝策略、提交一个任务执行流程?&nbsp;&nbsp;&nbsp;&nbsp;9、spring有哪些特点?(ioc/aop)&nbsp;&nbsp;&nbsp;&nbsp;10、spring中对于循环依赖是怎么解决的?&nbsp;&nbsp;&nbsp;&nbsp;11、MySQL和redis的区别?&nbsp;&nbsp;&nbsp;&nbsp;12、MySQL的索引结构是什么?&nbsp;&nbsp;&nbsp;&nbsp;13、MySQL的事务有哪些特性?怎么保证?&nbsp;&nbsp;&nbsp;&nbsp;14、MySQL的默认隔离级别?可重复读是怎么做到的呢?&nbsp;&nbsp;&nbsp;&nbsp;15、介绍一下MVCC和快照读readview。&nbsp;&nbsp;&nbsp;&nbsp;16、一般在什么场景下会使用redis?&nbsp;&nbsp;&nbsp;&nbsp;17、对于大量的请求,如果此时缓存中还没有写入数据怎么办?&nbsp;&nbsp;&nbsp;&nbsp;18、介绍一下redis实现的分布式锁。&nbsp;&nbsp;&nbsp;&nbsp;19、有用过es和mongo&nbsp;DB吗?(知道,没用过)&nbsp;&nbsp;&nbsp;&nbsp;20、消息中间件用过吗?说一下你的使用场景?&nbsp;&nbsp;&nbsp;&nbsp;21、一个场景,如果说有一个接口响应的比较慢,如果说让你排查,你会怎么去排查?(上下游接口、大key问题,只答了两,后面试官补充)&nbsp;&nbsp;&nbsp;&nbsp;无手撕,反问业务。
胖墩墩的查理在学c语言:哥们我是五号面的 流程差不多
查看21道真题和解析
点赞 评论 收藏
分享
数学转码崽:一直给我推,投了又不理,理了又秒挂
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务