题目与示例

  1. 389. 找不同
  2. 给定两个字符串 s 和 t，它们只包含小写字母。
  4. 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
  6. 请找出在 t 中被添加的字母。
  1. 示例 1：
  3. 输入：s = "abcd", t = "abcde"
  4. 输出："e"
  5. 解释：'e' 是那个被添加的字母。
  6. 示例 2：
  8. 输入：s = "", t = "y"
  9. 输出："y"
  10. 示例 3：
  12. 输入：s = "a", t = "aa"
  13. 输出："a"
  14. 示例 4：
  16. 输入：s = "ae", t = "aea"
  17. 输出："a"

代码

方案一

  1. class Solution {
  2.     public char findTheDifference(String s, String t) {
  3.         Map<Character, Integer> map = new HashMap<>();
  4.         // 存储s中的字母  及其出现次数
  5.         for (Character c : s.toCharArray()) {
  6.             if (map.containsKey(c)) {
  7.                 map.put(c, map.get(c) + 1);
  8.                 continue;
  9.             }
  10.             map.put(c, 1);
  11.         }
  13.         for (char tc : t.toCharArray()) {
  14.             // 在s中从未出现的字母
  15.             if (!map.containsKey(tc)) {
  16.                 return tc;
  17.             }
  19.             // 查找t中出现次数多了一次
  20.             if (map.get(tc) == 0) {
  21.                 return tc;
  22.             }
  23.             map.put(tc, map.get(tc) - 1);
  24.         }
  26.         return '-';
  27.     }
  28. }

方案二

遍历s中每个字母 将其在t中替换为空 t最后只剩一个字母 

class Solution {
    public char findTheDifference(String s, String t) {
        for (Character c : s.toCharArray()) {
            // 替换第一个出现的位置
            t = t.replaceFirst(c.toString(), "");
        }
        return t.toCharArray()[0];   
    }
}

方案三

根据ascii码表的特性：分别遍历s和t 将每个字母的值相加 所得结果相减 差值就是要找的值

a + b + c + d = 97 + 98 + 99 + 100 = 394

a + b + c + d + e = 97 + 98 + 99 + 100 + 101 = 495

class Solution {
     public static char findTheDifference2(String s, String t) {
        int sSum = 0, tSum = 0;
        for (Character c : s.toCharArray()) {
            sSum += c;
        }

        for (Character c : t.toCharArray()) {
            tSum += c;
        }
        return (char) (tSum - sSum);
    }
}

方案四

异或运算 

0 ^ 1  = 1 ^ 0 = 1  两者不同
0 ^ 0  = 1 ^ 1 = 0  两者相同  

a ^ b ^ c  ^ a ^ b  = (a ^ a) ^ (b ^ b) ^ c = c


s = "abcd", t = "abcde"

(a ^ b ^ c ^ d) ^ (a ^ b ^ c ^ d ^ e) = e

class Solution {
    public char findTheDifference(String s, String t) {      
        int result = 0;
        for (Character c : s.toCharArray()) {
            result ^= c;
        }
        for (Character c : t.toCharArray()) {
            result ^= c;
        }
        return (char) result;
    }
}