1.1确定一个字符串的所有字符是否全部不同
题目
全书题解目录: Cracking the coding interview-问题与解答
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄
原文:
Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?中文: 实现一个算法,确定一个字符串的所有字符是否全部不同。假设不允许使用额外的数据结构,又该如何处理?
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。解答
一开始,不妨先问问面试官,上面的字符串是ASCII字符串,还是只有26个字母?还是有更大的字符集,对于不同的情况,我们可能会有不同的解决方案。
如果我们假设字符集是ASCII字符,那么开一个大小为256的bool数组来表征每个字符的出现。数组初始化为false,遍历一遍字符串中的字符,当bool数组对应位置的值为真,表明该字符在之前已经出现过了,即可得出该字符串中有重复字符。
否者将该位置的bool数组值置为true。
代码如下:
func isUnique(s string ) bool { var a [ 256 ] bool for i := 0 ; i < len (s); i ++ { if a[s[i]] { // 这个字符已在字符串中出现过 return false } a[s[i]] = true } return true }
该算法的时间复杂度为O(n)。还可以通过位运算来减少空间的使用量。用每一位表征相应位置字符的出现。
对于ASCII字符,我们需要256位,即一个长度为8的int数组a即可。这里的关键是要把字符对应的数字,映射到正确的位上去。
比如字符'b’对应的代码是98,那么我们应该将数组中的哪一个位置为1呢?用98除以32,得到对应数组a的下标:3。98对32取模得到相应的位:2。
相应代码如下:
func isUnique(s string ) bool { var a [ 8 ] int for i := 0 ; i < len (s); i ++ { idx, shift := s[i] / 32 , s[i] % 32 if a[idx] & ( 1 << shift) > 0 { return false } a[idx] |= ( 1 << shift) } return true }
两个算法的本质是一样的,只不过一个用bool单元来表征字符出现,一个用位来表征。 如果字符集只是a-z(或是A-Z),那就更加好办了,用位运算只需要一个整数型即可。
func isUnique(s string ) bool { check := 0 for i := 0 ; i < len (s); i ++ { v := s[i] - 'a' if (check & ( 1 << v)) > 0 { return false } check |= ( 1 << v) } return true }
全书题解目录: Cracking the coding interview-问题与解答
全书的Go代码托管在Github上: github.com/custergo/study_algo
更多精彩