vlambda博客
学习文章列表

程序员面试金典01.01_go_判定字符是否唯一

程序员面试金典01.01_判定字符是否唯一


01

题目

实现一个算法,确定一个字符串 s 的所有字符是否全都不同。

示例 1:输入: s = "leetcode" 输出: false

示例 2:输入: s = "abc" 输出: true

限制:

0 <= len(s) <= 100

如果你不使用额外的数据结构,会很加分。



02


解题思路分析


1、哈希辅助;时间复杂度O(n),空间复杂度O(1)

func isUnique(astr string) bool { m := make(map[byte]bool) for i := 0; i < len(astr); i++ { if m[astr[i]] == true { return false } m[astr[i]] = true } return true}

2、位运算;时间复杂度O(n),空间复杂度O(1)

func isUnique(astr string) bool { value := uint32(0) for i := 0; i < len(astr); i++ { index := astr[i] - 'a' if value&(1<<index) == (1 << index) { return false } value = value ^ (1 << index) } return true}

3、遍历;时间复杂度O(n^2),空间复杂度O(1)

func isUnique(astr string) bool { for i := 0; i < len(astr); i++ { for j := i + 1; j < len(astr); j++ { if astr[i] == astr[j] { return false } } } return true}

4、排序遍历;时间复杂度O(nlog(n)),空间复杂度O(n)

func isUnique(astr string) bool { arr := []byte(astr) sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j] }) for i := 1; i < len(arr); i++ { if arr[i] == arr[i-1] { return false } } return true}

5、数组辅助;时间复杂度O(n),空间复杂度O(1)

func isUnique(astr string) bool { arr := make([]int, 256) for i := 0; i < len(astr); i++ { if arr[astr[i]] > 0 { return false } arr[astr[i]] = 1 } return true}

03


总结

Easy题目,比较简单,多种解答方法