剑指Offer（三十四）：第一个只出现一次的字符

2018年1月9日10:24:08 4 4,926 °C
摘要

在一个字符串中找到第一个只出现一次的字符,并返回它的位置。

剑指Offer（三十四）：第一个只出现一次的字符

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置。

1、思路

建立一个哈希表，第一次扫描的时候，统计每个字符的出现次数。第二次扫描的时候，如果该字符出现的次数为1，则返回这个字符的位置。

2、代码

C++：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int length = str.size();
        if(length == 0){
            return -1;
        }
        map<char, int> item;
        for(int i = 0; i < length; i++){
            item[str[i]]++;
        }
        for(int i = 0; i < length; i++){
            if(item[str[i]] == 1){
                return i;
            }
        }
        return -1;
    }
};

Python：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        length = len(s)
        if length == 0:
            return -1
        item = {}
        for i in range(length):
            if s[i] not in item.keys():
                item[s[i]] = 1
            else:
                item[s[i]] += 1
        for i in range(length):
            if item[s[i]] == 1:
                return i
        return -1

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：4   其中：访客  2   博主  2

    • avatar 到底对不对 来自天朝的朋友 谷歌浏览器 Windows 10 上海市 上海理工大学 4
      回复 2018年4月24日 下午3:57  沙发

      您好 c++里面map的item初值为0吗？++后不是1吗？
      —统计只出现一次的。。。。看错了

      • avatar Ryan_Wang 来自天朝的朋友 QQ浏览器 Windows 10 中国 联通 2
        回复 2019年4月8日 下午11:19  板凳

        您好，map item;构建item后，新建 item[str[i]] 对应的int默认值为0吗？
        还有博主是在哪查找的STL里各种函数的用法啊，有没有像菜鸟教程查python这种，比较方便的查STL的网站推荐？谢谢了

          • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
            回复 2019年4月9日 上午10:11  1层

            @Ryan_Wang 是0，自加后变成1。菜鸟教程也有c++ stl的。