给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
例如
输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。
输入：s = "ae", t = "aea"
输出："a"
1.循环判断
比较好想到的一种方法, 对于新手还来说比较好理解, 缺点就是时间, 空间复杂度都比较高
将s, t转换为正序数组
循环判断, 出现不一样的就是被添加字母
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.和运算
通过ascii值之和来判断处理新增加哪个字母
循环把s, t里面字母 ascii求和
因为t增加了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.异或
其实用异或处理这道题是比较好的方式
因为t只比s多了一个字符, 那么我们其实把 t, s合并会发现 同样字符出现偶数次, 只有新增字符出现奇数次
举个栗子:
t = abcd s = abc 合并针对于a, b, c都出现2次(偶数次), 而d出现1次(奇数次)
t = aaaab s = aaaa 合并针对于a 出现9次(奇数次), 也可以理解 8次a(偶数) 新加a 1次(奇数)
那么我们用异或方式来处理, 先留意下异或的几个特点
a^a=0; 任何数字和自己异或都是0
a^0=a; 任何数字和0异或还是他自己
a^b^a=a^a^b 异或运算具有交换律
就拿上面的举栗 a^b^c^d^a^b^c = a^a^b^b^c^c^d = 0^0^0^d = d, d其实就是我们要找的
转成ascii (数字)进行异或, 自己定义一套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 算法合集地址
网友评论