关于c++:leetcodeJZ50第一个只出现一次的字符

题面

原题链接

代码

本题有很多做法

动静布局（本人想进去的，工夫性能要比哈希表优良很多）：

int变量dpIndex，记录整个字符串中第一次只呈现一次的字符下标

int数组present[123]，因为'z'的ascii码是122，初始化为全0

dp[i] = 前i个字符串中第一个只呈现一次的字符

动静布局过程

if s[i]!=dp[i-1]    dp[i] = dp[i-1] else    present[s[dpIndex]] = 1    dpIndex++ until present[s[dpIndex]] != 1        dp[dpIndex] = s[dpIndex]        j = dpIndex

源代码

class Solution {public:    char firstUniqChar(string s) {        char result = 'n';        int present[123];        for(int i=0; i<123;i++){            present[i] = 0;        }        int len = s.size();        if(len==0){            return ' ';        }        char dp[len];        for(char k:dp){            k=' ';        }        int dpIndex = 0;        dp[0] = s[0];        int j= 1;        for(j = 1;j<len;j++){            if(s[j] != dp[j-1]){                dp[j] = dp[j-1];            }             else{                present[s[j]] = 1;                while(dpIndex<len && present[s[dpIndex]] == 1){                     dpIndex++;                }                if(dpIndex>=len){                    return ' ';                }                dp[dpIndex] = s[dpIndex];                j = dpIndex;                // if(j==len-1){                //     return ' ';                // }                cout<<dpIndex<<endl;            }        }        return dp[len-1];    }};

哈希表（书上给的做法，能够通过所有测试用例）

class Solution {public:    char firstUniqChar(string s) {        if(s.size()==0){            return ' ';        }        map<char,int> sta;        for(char k:s){            if(sta.find(k) == sta.end()){                sta[k] = 1;            }            else{                sta[k]++;            }        }        for(char k:s){            if(sta[k]==1){                return k;            }        }        return ' ';    }};