leetcode - 字符串中的第一个唯一字符 - 入门算法
还是老老实实 的 从基础的 算法开始练习吧
基础不牢 地动山摇 。。
所以 。。开始刷LeetCode 上的 基础算法 并且学习大佬的做法
字符串中的第一个唯一字符 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = “leetcode” 返回 0.
s = “loveleetcode”, 返回 2.
注意事项：您可以假定该字符串只包含小写字母。
有个坑呐 这个题目没有提及的是 。。 如果没找到返回 - 1
大体上的思路是 用 2*27 的辅助数组空间来记录每个字符的index 以及出现的次数
第一次 遍历完成统计 第二次 遍历输出结果
为什么用27个辅助数组空间呢
因为可以通过(int)‘a’ 这种方式 得到 char 类型的 asc码
来作为数组的索引
就自然的得到了一个字典
key值为string里的字符 value 是 该字符出现的次数
测试 结果一般还是。。
吼 上代码
class Solution {
public:
int firstUniqChar(string s) {
if(s.size()==0)
return -1;
//判空
int later[27] = {};// = {} 就默认都初始化 为 0 了
int laterIndex[27] = {};
int key = 0;
//完成各个字符的出现次数的统计
for(int i = 0;i < s.size();i++){
key = (int)s[i]-(int)'a';
if(later[key] == 0)
laterIndex[key] = i+1;
later[key]++;
}
//输出第一个 共出现 一次的字符
for(int i = 0;i < s.size();i++){
key = (int)s[i]-(int)'a';
if(later[key] == 1)
return laterIndex[key]-1;
}
//因为上文有return 所以如果到了这一步说明整个string 都是一样的 那就返回 -1了
return -1;
}
};
不难的 注意一下 int 数组 ={} 的方式 来 全初始化为 0
以及 (int)char 的方式来将char的asc码输出
接下来 膜拜一下大佬的代码 8ms的代码
class Solution {
public:
int firstUniqChar(string s) {
int hashTable[26];
memset(hashTable, -1, sizeof(hashTable));
for(int i=0; i<s.length(); i++) {
if (hashTable[s[i] - 'a'] > -1) {
hashTable[s[i] - 'a'] = -2;
} else if (hashTable[s[i] - 'a'] == -1) {
hashTable[s[i] - 'a'] = i;
}
}
int ret = -1;
for(int i=0; i<26; i++) {
if(hashTable[i] >= 0) {
if(ret<0 || ret>hashTable[i]) {
ret = hashTable[i];
}
}
}
return ret;
}
};
啊 果然是大佬 就是清晰明了
一点点学习
首先是大佬只用了一个数组 叫做 hashTable 命名就体现大佬的 精确
为什么只用一个数组就可以呢
因为我们这个题目不要求输出每个字符的出现的次数
所以呢 只需要记录 三种状态
一 是 == -1 即 这个字符没有在string里出现
二 是 > -1 即 这个字符出现了一次 而且这个值代表的是 这个字符的在string 里的 index
三 是 -2 即 这个字符出现了二次以上
最后 用一个ret来代表输出的结果
整体上值得学习的有两点
一是 hashTable 的命名
二是 只用了一个大小为27的数组
最最最值得学习的是大佬的时间复杂度小了一点 为 0（n）
应为最后输出结果的时候 我们既然存储了index 那么只要遍历26个index 输出 最小的那个index就好
