leetcode 每日一题：389. 找不同
leetcode 每日一题：389. 找不同
leetcode 每日一题：389. 找不同：https://leetcode-cn.com/problems/find-the-difference/
一起刷题吧
一、题目分析
输入：两个字符串，其中第二个字符串是第一个字符串重排后，随机在某个位置新加了一个别的字符 输出：新加入的字符 难度：简单 标签：哈希，位运算
示例 1： 输入：s = "abcd", t = "abcde" 输出："e" 解释：'e' 是那个被添加的字母。
示例 2： 输入：s = "", t = "y" 输出："y"
示例 3： 输入：s = "a", t = "aa" 输出："a"
示例 4： 输入：s = "ae", t = "aea" 输出："a"
二、参考代码
这个题目的解法很多，一个比较直观的想法是用哈希，当然这种解法很容易，这里就不给出实现代码。另外也可以通过计数的方式做寻找，在 python 中的 collections 包下有 Counter 数据结构，它可以直接获取到每个字符出现的次数，通过比较次数的不同，也可得到最终的值。参考代码如下：
from collections import Counter
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
count_s = Counter(s)
count_t = Counter(t)
for c in count_t:
if count_t[c]!=count_s[c]:
return c
这里主要想说的一种思路是通过位运算：异或。异或的运算规则为相同则为0，不同则为1，即：
1 ^ 0 = 1
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 1 = 0
而它还有一个特性，即相同的数字异或两次则等价于没有任何操作，即：
a ^ b ^ a = b
因此对于我们这个题目可直接利用这个特性，题目转换一个，给定一个字符串，只有一个字符出现一次，其他字符都会出现偶数次，找出这个字符。利用这个特性，直接将所有结果做一个异或运算最终的结果就是我们需要值。
当然这里我们还需要知道另外一个特性，即 0 与其他任意数值做异或都等于这个数值本身，即：
0 ^ a = a
因此我们代码的初始值就可以设置为 0，参考实现代码如下：
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
# 避免 None输入，同时解决输入为 s = "a", t = "" 这种特殊情况
s = s or ""
t = t or ""
result = 0
for c in s:
result ^= ord(c)
for c in t:
result ^= ord(c)
return chr(result)
测试用例：（注意：在很多面试时，面试官也会问你，你会写一些什么测试用例，一般是看你考虑问题的全面性，所以也要有能自己找准测试用例的能力）
s = Solution()
print(s.findTheDifference("abcd", "abcde"))
print(s.findTheDifference("abcd", "aebcd"))
print(s.findTheDifference("a", ""))
提交执行结果：
执行结果：通过 显示详情 执行用时：36 ms, 在所有 Python3 提交中击败了92.65%的用户
内存消耗：14.9 MB, 在所有 Python3 提交中击败了5.13%的用户
时间上位运算还是很高效的。