0387. First Unique Character in a String

387. First Unique Character in a String #

题目 #

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

题目大意 #

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

解题思路 #

  • 简单题,要求输出第一个没有重复的字符。
  • 解法二这个思路只超过 81% 的用户,但是如果测试样例中 s 的字符串很长,但是满足条件的字符都在靠后的位置的话,这个思路应该会更有优势。通过记录每个字符的第一次出现的位置和最后一次出现的位置。第一次对 s 进行一次遍历。第二次仅仅对数组进行遍历就可以了。

代码 #


package leetcode

// 解法 一
func firstUniqChar(s string) int {
	result := make([]int, 26)
	for i := 0; i < len(s); i++ {
		result[s[i]-'a']++
	}
	for i := 0; i < len(s); i++ {
		if result[s[i]-'a'] == 1 {
			return i
		}
	}
	return -1
}

// 解法 二
// 执行用时: 8 ms
// 内存消耗: 5.2 MB
func firstUniqChar1(s string) int {
	charMap := make([][2]int, 26)
	for i := 0; i < 26; i++ {
		charMap[i][0] = -1
		charMap[i][1] = -1
	}
	for i := 0; i < len(s); i++ {
		if charMap[s[i]-'a'][0] == -1 {
			charMap[s[i]-'a'][0] = i
		} else { //已经出现过
			charMap[s[i]-'a'][1] = i
		}
	}
	res := len(s)
	for i := 0; i < 26; i++ {
		//只出现了一次
		if charMap[i][0] >= 0 && charMap[i][1] == -1 {
			if charMap[i][0] < res {
				res = charMap[i][0]
			}
		}
	}
	if res == len(s) {
		return -1
	}
	return res
}


⬅️上一页

下一页➡️

Calendar Jul 16, 2021
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者