LeetCode刷题-找不同

前言说明

算法学习，日常刷题记录。

题目连接

找不同

题目内容

给定两个字符串s和t，它们只包含小写字母。

字符串t由字符串s随机重排，然后在随机位置添加一个字母。

请找出在t中被添加的字母。

示例1:

输入：s = "abcd", t = "abcde"

输出："e"

解释：'e' 是那个被添加的字母。

示例2:

输入：s = "", t = "y"

输出："y"

示例3:

输入：s = "a", t = "aa"

输出："a"

示例4:

输入：s = "ae", t = "aea"

输出："a"

提示:

0 <= s.length <= 1000

t.length == s.length + 1

s和t只包含小写字母

分析过程

此题需要脑筋急转弯一下，使用位运算的方法，可以快速解决。

第一步

定义被添加的字母的ascii码为res，初始为0。

第二步

先遍历字符串s的的字符，每次都把字符和res进行异或运算，结果赋值给res。

第三步

再遍历字符串t的字符，每次都把字符和res进行异或运算，结果赋值给res。

第四步

最后把res转为字符类型返回结果，即为字符串t中被添加的字母，原因请看下面的推导过程。

推导过程

位运算有两个定律：

1、相同两数异或运算，得到0，例如：a ^ a = 0。

2、0和某数异或运算，得到某数本身，例如：a ^ 0 = a。

这里把字符串s和字符串t的所有字符进行了异或运算，刚好字符串t中包含所有字符串s中的字符，并且字符串t中多出一个额外字符，那么最终的结果就是额外字符本身，也就是t中被添加的字母。

例如：s = "abcd"，t = "abcde"

对于字符串s：res = 0 ^ a ^ b ^ c ^ d。

对于字符串t：res = res ^ 0 ^ a ^ b ^ c ^ d ^ e。

合起来就是：res = 0 ^ a ^ b ^ c ^ d ^ a ^ b ^ c ^ d ^ e，刚好两个a，两个b，两个c，两个d，一个0，一个e。

整理后就是：res = a ^ a ^ b ^ b ^ c ^ c ^ d ^ d ^ 0 ^ e。

根据上面的第1条定律，相同两数异或运算得到0，那么两个一起出现的都变成0，即：a ^ a = 0，b ^ b = 0，c ^ c = 0，d ^ d = 0，所以以上变成：res = 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ e，而0 ^ 0也是符合两数异或运算的，也是得到0，即：0 ^ 0 = 0，所以最后变成：res = 0 ^ e。

再根据上面的第2条定律，0和某数异或运算得到某数本身，即：0 ^ e = e，所以：res = 0 ^ e = e，即：res = e。

所以根据以上的推导过程，可以得出结论，最后的res就是e的ascii码，即为字符串t中被添加的字母。

解答代码

class Solution {
    public char findTheDifference(String s, String t) {
        // 用位运算方法找出字符串t中比字符串s中多出的字符
        int res = 0;

        // 先遍历字符串s的的字符，每次都进行异或运算
        for (int i = 0; i < s.length(); ++i) {
            res ^= s.charAt(i);
        }

        // 再遍历字符串t的字符，每次都进行异或运算
        for (int i = 0; i < t.length(); ++i) {
            res ^= t.charAt(i);
        }

        // 相同两数异或运算，得到0
        // 0和某数异或运算，得到某数本身
        // 这里把字符串s和字符串t的所有字符进行了异或运算，刚好字符串t中包含所有字符串s中的字符，并且字符串t中多出一个额外字符，那么最终的结果就是额外字符本身
        
        return (char) res;
    }
}

提交结果

执行用时2ms，时间击败79.52%的用户，内存消耗36.9MB，空间击败41.10%的用户。

运行结果

原文链接

原文链接：找不同