【golang】leetcode初级-字符串中的第一个唯一字符&有效的字母异位词
第一题 字符串中的第一个唯一字符
题目信息
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
示例：
【【golang】leetcode初级-字符串中的第一个唯一字符&
有效的字母异位词】s = "leetcode"
返回 0
s = "loveleetcode"
返回 2
提示：你可以假定该字符串只包含小写字母。
解题思路
对于这道题，最暴力的方法自然是：
对于字符串的每个字符，都查找一遍字符串，若找到相同的字符，则开始查找下一个字符；若找不到相同的字符，则返回该字符的索引。
暴力解法简单易懂的同时，也进行了大量的无意义操作，若唯一字符位于字符串尾部，则该算法的计算量将异常庞大。算法的时间复杂度为O（n^2）
对此，我们考虑引入新的数据结构辅助完成对字符串的查询，即哈希表
哈希表是一种巧妙并且实用的数据结构。它是一个无序的key/value对的集合，其中所有的key都是不同的，然后通过给定的key可以在常数时间复杂度内检索、更新或删除对应的value。
引用
在Go语言中，一个map就是一个哈希表的引用，map类型可以写为map[K]V，其中K和V分别对应key和value。map中所有的key都有相同的类型，所有的value也有着相同的类型，但是key和value之间可以是不同的数据类型。其中K对应的key必须是支持==比较运算符的数据类型，所以map可以通过测试key是否相等来判断是否已经存在。
文章图片
详见
https://haicoder.net/golang/g...
代码
func firstUniqChar(s string) int {
m:= make(map[rune]int, 26)
for _, ch := range s {
m[ch]++
}
for i, ch := range s {
if m[ch] == 1 {
return i
}
}
return -1
}复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。我们需要进行两次遍历。
空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此 ∣Σ∣≤26。我们需要 O(∣Σ∣) 的空间存储哈希映射。
文章图片
小优化
阅读官方代码
func firstUniqChar(s string) int {
cnt := [26]int{}
for _, ch := range s {
cnt[ch-'a']++
}
for i, ch := range s {
if cnt[ch-'a'] == 1 {
return i
}
}
return -1
}作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。我们可以看到，官方在使用哈希表时，将读到的字符减去字符a的码值再进行查表
经过对比尝试，发现这样可以大幅度减少执行时间
文章图片
第二题 有效的字母异位词 题目信息
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
相关标签
哈希表
字符串
排序
解题思路
将两个字符串各自存入哈希表记录每个字符出现的次数，再通过查表一一取得出现次数对比
代码
func isAnagram(s string, t string) bool {
m1:= make(map[rune]int, 26)
m2:= make(map[rune]int, 26)
for _, ch := range s {
m1[ch-'a']++
}
for _, ch := range t {
m2[ch-'a']++
}
if len(s)官方解析
对于使用哈希表的方法，由于是两个字符串的比较，在将第二个字符串记入第二个哈希表的时候可以选择以第一个哈希表的清除替代，在节省了空间的同时，也省去了将两个哈希表比较的时间
func isAnagram(s, t string) bool {
if len(s) != len(t) {
return false
}
cnt := map[rune]int{}
for _, ch := range s {
cnt[ch]++
}
for _, ch := range t {
cnt[ch]--
if cnt[ch] < 0 {
return false
}
}
return true
}作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/valid-anagram/solution/you-xiao-de-zi-mu-yi-wei-ci-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。另外，官方还接受了另一种思路 排序法
将两个字符串进行排序之后再进行对比
由于复杂度较高，暂不予以论述
复杂度分析
时间复杂度：O(n)，其中 n 为 s 的长度。
空间复杂度：O(S)，其中 S 为字符集大小，此处S=26。
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长