题解 第三章排序与查找| #找位置#

找位置

http://www.nowcoder.com/practice/e3b2cc44aa9b4851bdca89dd79c53150

法1:

使用了哈希表

参考这一篇文章:https://blog.nowcoder.net/n/9bdf2f93480045b6810453b39196260b

哈希表不一定要是链表形式,也可能是用一个数组结构存放

#include <stdio.h>

//ASCII码一共128位
//0-9是48-57
//A-Z是65-90
//a-z是97-122

typedef struct CharTable
{
    int Num;
    int Place[15];
}CharTable;
//哈希表的结构,其中Place中装入有各个字符的位置

//哈希表也不一定要用链表的形式
//比如此处Table中的每一块内
//只用存放该字母首次出现的位置
int main()
{
    CharTable myCharTable[128];
    
    //定义了这样一个哈希表后,需要将其清零
    //使用memset函数
    //void *memset(void* s,int ch,size);
    //memset(myCharTable,0,128*sizeof(CharTable));
    memset(myCharTable,0,sizeof(myCharTable));
    //使用sizeof可以返回该数组的内存占有长度
    
    
    //将现有数据输入
    char C;
    int order=0,tmp;
    while(scanf("%c",&C)!=EOF)
    {
        tmp=myCharTable[C].Num++;
        myCharTable[C].Place[tmp]=order;
        order++;
    }
    
    //得到输出的顺序,得到有几个数字
    char Rank[order];
    memset(Rank,0,sizeof(Rank));
    for(int i=0;i<128;i++)
    {
        if(myCharTable[i].Num!=0)
            Rank[myCharTable[i].Place[0]]=(char)i;
    }//在Rank中存入了每一个字符的出现先后次序
    //有的多余的地方是存了0,这些都是要舍去的
    
    //按顺序,将hash表中的所有的结果输出
    int presChar;
    for(int i=0;i<sizeof(Rank);i++)
    {
        presChar=Rank[i];
        if(myCharTable[presChar].Num>1)
        {
            for(int j=0;j<myCharTable[presChar].Num-1;j++)
            {
                printf("%c:%d,",(char)presChar,myCharTable[presChar].Place[j]);
            }
            printf("%c:%d\n",(char)presChar,myCharTable[presChar].Place[myCharTable[presChar].Num-1]);
            //这里是防止最后多打了一个逗号
        }
    }
    
    return 0;
}
王道机试指南刷题 文章被收录于专栏

计划刷完这本书

全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
Yki_:你要算时间成本呀,研究生两三年,博士三四年,加起来就五六年了,如果你本科去腾讯干五年,多领五年的年薪,加上公司内涨薪,可能到时候十五年总薪资也跟博士差不多
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
找个工作&nbsp;学历是要卡的&nbsp;要求是高的&nbsp;技能不足是真的&nbsp;实习经验是0的&nbsp;简历无处可写是事实的&nbsp;钱不好赚是真的&nbsp;想躺平又不敢躺&nbsp;也不甘心躺&nbsp;怕自己的灵感和才华被掩埋甚至从未被自己发现&nbsp;又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务