C++版 - 剑指Offer 面试题35：第一个只出现一次的字符解题报告(华为OJ034-找出字符串中第一个只出现一次的字符)

Enjoy233

发布于 2019-03-05 14:31:19

8230

发布于 2019-03-05 14:31:19

文章被收录于专栏：大白技术控的技术自留地

面试题35：第一个只出现一次的字符

题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。(2006年google的一道笔试题。)

分析：

首先应向确认一下是ASCII字符串，而不是Unicode字符串。用hash表求解即可，由于需要先遍历一次，时间复杂度为O(n)，空间复杂度为O(1) (256个ASCII字符).

满足题意的代码如下：

#include<cstdio>
#include<string>
#include<unordered_map>
using namespace std;
class Solution {
public:
    char FirstNotRepeatingChar(string str) {
        if(str.size() == 0) return '\0';
        unordered_map<char, int> countMap; // 使用C++中的map的insert时，返回结果是自动按key排序(增序)后的结果
        for(int i = 0;i < str.size();i++){
            if(countMap.find(str[i]) == countMap.end())
                countMap[str[i]]=1;
                // countMap.insert({str[i], 1}); // 映射表中没找到相关记录，加到映射表，次数设置为1 
            else countMap[str[i]]++; // 映射表中找到了相关记录，将映射表中的次数+1 
        }
        // int pos = -1;
		char ch;
        for(int i = 0;i < str.size();i++){
            if(countMap[str[i]] == 1){
                // pos = i;
                ch=str[i];
                break;
            }
        }
        return ch;
    }
};
// 以下为测试 
int main()
{
	Solution sol;
	string str1="abaccdeff";
	string str2="cbacnba";	
	char res1 = sol.FirstNotRepeatingChar(str1);
	char res2 = sol.FirstNotRepeatingChar(str2);	
	printf("%c\n", res1);	
	printf("%c\n", res2);		
	return 0;
}

也可简化为：

#include<cstdio>
#include<string>
#include<unordered_map>
using namespace std;
class Solution {
public:
    char FirstNotRepeatingChar(string str) {  	
        int hash[256] = {0};
        for(auto c : str){  // 遍历一次，复杂度为O(n) 
            hash[c] ++;
        }
		char ch;         
        for(int i=0;i<str.size();i++){
            if(hash[str[i]] == 1){
                //return i;
                return str[i];
            }
        }
        return '\0'; // if(str.size() == 0) return '\0';
    }
};
// 以下为测试 
int main()
{
	Solution sol;
	string str1="ABACCDEFF";
	string str2="cbacnba";	
	char res1 = sol.FirstNotRepeatingChar(str1);
	char res2 = sol.FirstNotRepeatingChar(str2);	
	printf("%c\n", res1);	
	printf("%c\n", res2);			
	return 0;
}

相比而言，前一种方法更高效，256个字符可能只出现很少的一部分，后面这种方法在空间上消耗多一点...

九度OJ 提交网址 http://ac.jobdu.com/problem.php?pid=1283

牛客网OJ 改编：在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符的位置。若为空串，返回-1。位置索引从0开始。

提交网址： http://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=13&tqId=11187

输入：

一个字符串。

输出：

输出第一个只出现一次的字符下标，没有只出现一次的字符则输出-1。

样例输入：ABACCDEFF AA样例输出：1 -1 牛客网 AC代码：

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.size() == 0) return -1;
        unordered_map<char, int> countMap; // 使用C++中的map的insert时，返回结果是自动按key排序(增序)后的结果 
        for(int i = 0;i < str.size();i++){
            if(countMap.find(str[i]) == countMap.end())
            	countMap[str[i]]=1;  // 映射表中没找到相关记录，加到映射表，次数设置为1 
            else countMap[str[i]]++; // 映射表中找到了相关记录，将映射表中的次数+1 
        }
        int pos = -1;
        for(int i = 0;i < str.size();i++){
            if(countMap[str[i]] == 1){
                pos = i;
                break;
            }
        }
        return pos;
    }
};

精简之后：

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int hash[256] = {0};
        for(auto c : str){  // 遍历一次，复杂度为O(n) 
            hash[c] ++;
        }         
        for(int i=0;i<str.size();i++){
            if(hash[str[i]] == 1){
                return i;
            }
        }
        return -1; // if(str.size() == 0) return -1; 
    }
};

华为OJ034-找出字符串中第一个只出现一次的字符

提交网址： http://www.nowcoder.com/practice/e896d0f82f1246a3aa7b232ce38029d4?tpId=37&tqId=21282

时间限制：1秒空间限制：32768K 参与人数：157

本题知识点：字符串

题目描述 找出字符串中第一个只出现一次的字符

接口说明 原型： char FindChar(InputString); 输入参数：字符串InputString 输出参数：如果无此字符请输出该字符；如果无此字符，请输出'.'。

输入描述 输入一串字符 输出描述 输出一个字符输入例子 asdfasdfo 输出例子 o

AC代码(C++风格)：

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
char FirstNotRepeatingChar(string str)
{
    if(str.size() == 0) return '.';
    unordered_map<char, int> countMap;
    for(int i = 0;i < str.size();i++){
        if(countMap.find(str[i]) == countMap.end())
            countMap[str[i]]=1;
        else countMap[str[i]]++; // 映射表中找到了相关记录，将映射表中的次数+1 
    }
	char ch;
    for(int i = 0;i < str.size();i++){
        if(countMap[str[i]] == 1){
            ch=str[i];
            break;
        }
    }
    return ch;
}
int main() {
	string str;
	while(cin>>str) {
	char ch=FirstNotRepeatingChar(str);
        cout<<ch<<endl;
	}
	return 0;
}

或

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
char FindChar(string str)
{
	unordered_map<char,int> m;
        char ch;
	for(unsigned int i=0; i<str.size(); i++)
	m[str[i]]++;
        unsigned int i;
	for(i=0; i<str.size(); i++) {
		if(m[str[i]]==1) {
			ch=str[i]; break;
		}
	}
	if(i==str.size()) ch='.';
    return ch;
}
int main() {
	string str;
	while(cin>>str) {
	char ch=FindChar(str);
        cout<<ch<<endl;
	}
	return 0;
}

AC代码(使用指针)：

#include<iostream>
#include<string>
using namespace std;
char FindChar(char *input)
{
    char *p=input; 
    int hash[256];
    for(int i=0;i!=256;i++)
        hash[i]=0;
    
    while(*p!='\0')
    {
            hash[*p]++;
                  p++;
    }
    char *p1=input;
    
    while(*p1!='\0')
        {
             if(hash[*p1]==1)
             {
                 return *p1;
             }
             p1++;
         }  
     return '.';
}
int main()
{
    char str[1000];
    while(cin>>str)
    {
        char ch=FindChar(str);
        cout<<ch<<endl;
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016年05月07日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度