关于LeetCode中Find the Difference一题的理解

78 阅读 0 评论 52 点赞

我是靠谱客的博主年轻小鸽子，最近开发中收集的这篇文章主要介绍关于LeetCode中Find the Difference一题的理解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目如下：

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"
Output:
e
Explanation:
'e' is the letter that was added.

题目的要求是给定一个字符串s，另给定一个字符串t。字符串t是怎么构成的呢？s中的所有字母首先进行乱序（即shuffle，这个单词有“洗牌”的意思），然后将一个额外的字母放入s已经shuffle后的一个随机位置，这样就产生了我们的新字符串t。举个例子，s=“abcd”，首先将s乱序变为“dcab”，然后将一个字母“k”加到“dcab”中的一个随机位置中，比如这里就先加到首位，即“kdcab”。题目要求我们做的是，给定这样的s和t后，将那个t中被插入的字母找出来。如果拿刚才的例子来说，程序最后就应该输出“k”。

我的思路一般比较Low，这次也不意外。我的想法是先将这两个字符串转化为char类型的数组，然后分别将这两个char类型的数组进行排序，最后再按位比较每个位置上的字符是否相等，如果不相等，就输出t对应的那个数组这个位置上的字符即可。当然，这里肯定要用到循环，循环次数也肯定是较短的s字符串的长度，如果在整个循环结束后还没有输出目标字符，则说明t中的最后一个字符肯定是目标字符，输出该字符即可。已Accepted的代码如下：

<span style="font-size:14px;">
public char findTheDifference(String s, String t) {
char[] s_array = s.toCharArray();
char[] t_array = t.toCharArray();
Arrays.sort(s_array);
Arrays.sort(t_array);
for (int i=0;i<s_array.length;i++){
if (s_array[i] != t_array[i]){
return t_array[i];
}
}
return t_array[t_array.length-1];
}</span>

评论区的另一种思路是使用XOR（即异或操作），将两个字符串中所有的字符进行“异或”操作，最后剩下的那个字符就是我们要的结果，这是因为在“异或”过程中，两个相同字符会变成0，所以“异或”到最后就等价于0和目标字符进行“异或”，结果还是目标字符，直接输出即可，代码如下：

<span style="font-size:14px;">public char findTheDifference_B(String s, String t) {
char c = 0;
for (int i = 0; i < s.length(); ++i) {
c ^= s.charAt(i);
}
for (int i = 0; i < t.length(); ++i) {
c ^= t.charAt(i);
}
return c;
}</span>

最后再说一句，异或操作可以用来找不同或者进行模拟加法运算，就酱。