題目
原文:
Is Unique: Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?中文: 實作一個演算法，確定一個字串的所有字符是否全部不同，假設不允許使用額外的資料結構，又該如何處理？
解答
一開始，不妨先問問面試官，上面的字串是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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138110.html
標籤：其他
下一篇：順序堆疊實作數制的轉換