关于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 ' ';
    }
};