21 字符串专题：第一个只出现一次的字符

0 引言

本专题专门针对字符串处理问题，解答了一系列问题。用到了C++中的string类，下面将对string类的方法进行介绍。

#include <string> // 头文件

using std::string;

（1）利用迭代器对字符串元素进行访问

void visitCharInString(string str){
  for(std::string::iterator it = str.begin(); it != str.end(); ++ it){
      cout << *it << "	";    
  }  
}

（2）访问字符串中的元素

　　1. 操作符operator[]

  for (int i=0; i<str.length(); ++i)
  {
    std::cout << str[i];
  }

　　2. at方法

  for (unsigned i=0; i<str.length(); ++i)
  {
    std::cout << str.at(i);
  }

　　3. back方法访问字符串的最后一个字符

  std::string str ("hello world.");
  str.back() = '!';
  std::cout << str << '
';

　　4. front方法访问字符串的第一个字符

  std::string str ("test string");
  str.front() = 'T';
  std::cout << str << '
';

（3）字符串问题之第一个只出现一次的字符

题目：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

1 抽象问题具体化

举例：返回字符串 “google”中第一个只出现一次的字符，如果没有则返回-1.

解答：1. 遍历字符串，访问g，++ myStr['g' - 'A'] ，保存第一个g出现的位置， position['g' - 'A'];

　　　2. 继续访问其他字符， ++ myStr[str[i] - 'A']，保存第一个str[i]出现的位置, position[str[i] - 'A'];

　　　3. 遍历myStr和position，找到mystr[i] == 1的最小的position的值，即为google中第一个只出现一次的字符，为 'l' .

2 具体问题抽象分析

（1）定义两个整型数组, myStr, positon, 并resize 为 size = 'z' - 'A' + 1 这么大

（2）遍历字符串，保存每个字符出现的次数至myStr, 保存每个字符初次出现的位置到 position

（3）遍历myStr 和position，寻找myStr[i] == 1 的位置最靠前的字符，即position[i]最小，保存在firstOnlyPosition中

（4）如果firstOnlyPosition == 初始值，则返回-1；否则，返回firstOnlyPosition作为结果输出.

3 demo

/* FirstNotRepeatingChar： 寻找字符串中第一个不重复出现的字符

* 输入参数：字符串
* 输出参数：该字符在字符串中的位置
* 采用的算法核心思想： 两次遍历找到结果
　　　　1. 第一次遍历字符串时，保存每个相同字符出现的次数和首次出现的位置；
　　　　2. 第二次遍历字符串时，寻找只出现过一次的字符中，出现位置最早的字符，返回结果即可
* 算法的复杂度：O（n + k），k为不重复字符出现的次数
*/
int FirstNotRepeatingChar(string str) {
    vector<int> myStr, position;
    const int size = 'z' - 'A' + 1;
    myStr.resize(size), position.resize(size);
    for(int i=0; i<str.size(); i++){
        ++ myStr[str[i]-'A'];
        if(myStr[str[i]-'A'] == 1)
            position[str[i]-'A'] = i;
    }
    int firstOnlyPosition = str.size();
    for(int i=0;i<size;i++){
        if(myStr[i] == 1 && position[i] < firstOnlyPosition)
            firstOnlyPosition = position[i];
    }
    if(firstOnlyPosition == str.size())
        return -1;
    else
        return firstOnlyPosition;
}

4 代码优化

暂时还没有找到更好的算法，以后再说吧