Skip to content

Commit 6567aad

Browse files
author
Longerhaha
authored
Merge pull request gzc426#12 from Longerhaha/Longerhaha-patch-7
添加乔戈里leetcode每日一题描述
2 parents cb9d83b + 59699cf commit 6567aad

File tree

2 files changed

+57
-1
lines changed

2 files changed

+57
-1
lines changed

2018.12.1-leetcode387/1.md

Lines changed: 0 additions & 1 deletion
This file was deleted.
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
## 387_(字符串中的第一个唯一字符)First Unique Character in a String
2+
## 1 问题描述、输入输出与样例
3+
### 1.1 问题描述
4+
给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
5+
### 1.2 输入与输出
6+
输入:
7+
* string s:输入的字符串s
8+
9+
输出:
10+
* int:它的第一个不重复的字符的索引
11+
### 1.3 样例
12+
#### 1.3.1 样例1
13+
输入:s = "leetcode"<br>
14+
输出:返回 0<br>
15+
16+
#### 1.3.2 样例2
17+
输入: s = "loveleetcode"<br>
18+
输出: 2<br>
19+
## 2 思路描述与代码
20+
### 2.1 思路描述(字典法)
21+
dict[c] 记录字符 c 的数目,一遍扫描记录字符串 s 中的所有字符的数目<br>
22+
然后再一遍扫描 s,当 s 中字符 c 只出现一次即dict[c] = 1时返回下标,如果没有这样的字符则返回-1<br>
23+
24+
比如输入s = "leetcode",一遍扫描后有:<br>
25+
dict['c'] = 1, dict['d'] = 1, dict['e'] = 3, dict['l'] = 1, dict['o'] = 1, dict['t'] = 1<br>
26+
然后再次一遍扫描s,发现dict['l'] = 1,返回此时遍历的索引 0<br>
27+
28+
### 2.2 代码
29+
```cpp
30+
int firstUniqChar(string s) {
31+
vector<int> dict(26, 0);
32+
int len = s.size();
33+
for( int i = 0; i < len; i++ ) dict[s[i] - 'a'] += 1;
34+
for( int i = 0; i < len; i++ ){
35+
if(dict[s[i] - 'a'] == 1) return i;
36+
}
37+
return -1;
38+
}
39+
```
40+
## 3 思考与拓展
41+
### 3.1 思考
42+
#### 3.1.1 其他方法
43+
##### 3.1.1.1 字典+队列法
44+
dict[c] 记录字符 c 的数目,队列 q 保存的是在遍历过程中在 s 中按前后顺序出现出现过的字符极其下标,相同字符只记录一次<br>
45+
46+
然后遍历队列里面的元素,当 s 中字符 c 只出现一次即dict[c] = 1时返回下标。
47+
48+
#### 3.1.2 复杂度分析
49+
方法|空间复杂度|时间复杂度
50+
--- | --- | ---
51+
字典法|O(1)|O(n)
52+
字典+队列法|O(n)|O(n),平均复杂度更低,应该运行更快
53+
#### 3.1.3 难点分析
54+
1. 如何查重即多个相同的字符
55+
2. 如何按先后顺序记录只出现一次的字符
56+
### 3.2 拓展
57+
如果给你的是链表数据或者数组数据呢?

0 commit comments

Comments
 (0)