給定兩個字符串 s 和 t璃谨，它們只包含小寫字母。
字符串 t 由字符串 s 隨機(jī)重排，然后在隨機(jī)位置添加一個字母喉前。
請找出在 t 中被添加的字母没酣。
例如
輸入：s = "abcd", t = "abcde"
輸出："e"
解釋：'e' 是那個被添加的字母。
輸入：s = "ae", t = "aea"
輸出："a"
1.循環(huán)判斷
比較好想到的一種方法, 對于新手還來說比較好理解, 缺點(diǎn)就是時間, 空間復(fù)雜度都比較高
將s, t轉(zhuǎn)換為正序數(shù)組
循環(huán)判斷, 出現(xiàn)不一樣的就是被添加字母
func findTheDifference(_ s: String, _ t: String) -> Character {
var arr_s = s.sorted(), arr_t = t.sorted()
for i in 0..<s.count {
if arr_s[i] != arr_t[i]{
return arr_t[i]
}
}
return arr_t.last!
}
2.和運(yùn)算
通過ascii值之和來判斷處理新增加哪個字母
循環(huán)把s, t里面字母 ascii求和
因?yàn)閠增加了1個字母, t - s 就是增加字母的ascii值, 再編碼換算一下找出增加哪個字母
func findTheDifference(_ s: String, _ t: String) -> Character {
var ssum: Int = 0,tsum: Int = 0
for sc in s {
ssum += Int(sc.asciiValue!)
}
for tc in t {
tsum += Int(tc.asciiValue!)
}
return Character(Unicode.Scalar(tsum - ssum)!)
}
3.異或
其實(shí)用異或處理這道題是比較好的方式
因?yàn)閠只比s多了一個字符, 那么我們其實(shí)把 t, s合并會發(fā)現(xiàn) 同樣字符出現(xiàn)偶數(shù)次, 只有新增字符出現(xiàn)奇數(shù)次
舉個栗子:
t = abcd s = abc 合并針對于a, b, c都出現(xiàn)2次(偶數(shù)次), 而d出現(xiàn)1次(奇數(shù)次)
t = aaaab s = aaaa 合并針對于a 出現(xiàn)9次(奇數(shù)次), 也可以理解 8次a(偶數(shù)) 新加a 1次(奇數(shù))
那么我們用異或方式來處理, 先留意下異或的幾個特點(diǎn)
a^a=0; 任何數(shù)字和自己異或都是0
a^0=a; 任何數(shù)字和0異或還是他自己
a^b^a=a^a^b 異或運(yùn)算具有交換律
就拿上面的舉栗 a^b^c^d^a^b^c = a^a^b^b^c^c^d = 0^0^0^d = d, d其實(shí)就是我們要找的
轉(zhuǎn)成ascii (數(shù)字)進(jìn)行異或, 自己定義一套key(Character):value(Int)異或處理也行
func findTheDifference(_ s: String, _ t: String) -> Character {
var asciiValue: UInt8 = 0
for c in s { asciiValue ^= c.asciiValue! }
for c in t { asciiValue ^= c.asciiValue! }
return Character(UnicodeScalar(asciiValue))
}
題目來源：力扣（LeetCode） 感謝力扣爸爸 :)
IOS 算法合集地址
