LeetCode算法题-Find the Difference(Java实现-五种解法)
这是悦乐书的第214次更新,第227篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第82题(顺位题号是389)。给定两个字符串s和t,它们只包含小写字母。字符串t由随机混洗字符串s生成,然后在随机位置再添加一个字母。找到t中添加的字母。例如:
输入:s =“abcd”, t =“abcde”
输出:‘e’
说明:'e’是添加的字母。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
因为限定字符串都是小写字母,可以借助一个26长度的数组,将t中的字符出现次数记录下来,然后再去遍历s的字符,只要有对应的就做减法,最后再去找数组中为1的元素的索引,将其和字符a相加,就是t中添加的字母。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public char findTheDifference(String s, String t) {
int[] arr = new int[26];
for (int i=0; i<t.length(); i++) {
arr[t.charAt(i)-'a']++;
}
for (int j=0; j<s.length(); j++) {
arr[s.charAt(j)-'a']--;
}
for (int k=0; k<arr.length; k++) {
if (arr[k] == 1) {
return (char)(k+'a');
}
}
return '0';
}
03 第二种解法
还是使用长度26的数组,将s中出现的字符及次数记录下来,再去遍历t的字符,同时对其对应数组中的元素做自减,如果自减后小于0,即表示当前字符没有在s中出现过,此字符就是t中添加的字母。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public char findTheDifference2(String s, String t) {
int[] arr = new int[26];
for (int i=0; i<s.length(); i++) {
arr[s.charAt(i)-'a']++;
}
for (int j=0; j<t.length(); j++) {
if (--arr[t.charAt(j)-'a'] < 0) {
return t.charAt(j);
}
}
return '0';
}
04 第三种解法
使用异或位运算,其规则是两边的对应位不同时,取1,否则取0。两个相同的数做异或运算时,运算结果是0。0和一个非0的数做异或运算时,运算结果是那个非0的数。将s和t中的所有字符做异或运算,最后的运算结果就是多出来的那个字符。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public char findTheDifference3(String s, String t) {
int ch = 0;
for (int i=0; i<s.length(); i++) {
ch = ch^s.charAt(i);
}
for (int j=0; j<t.length(); j++) {
ch = ch^t.charAt(j);
}
return (char)ch;
}
05 第四种解法
此解法思路和第三种解法一样,只是将两次循环合并到一次循环中去了。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public char findTheDifference4(String s, String t) {
int ch = t.charAt(t.length()-1);
for (int i=0; i<s.length(); i++) {
ch = ch^t.charAt(i)^s.charAt(i);
}
return (char)ch;
}
06 第五种解法
既然可以做异或运算,那么也可以尝试做加减运算,用t中所有字符的和减去s中所有字符的和,剩下的差就是t中多出的字母。
此解法的时间复杂度是O(n),空间复杂度是O(1)。
public char findTheDifference5(String s, String t) {
char ch = t.charAt(t.length()-1);
for (int i=0; i<s.length(); i++) {
ch -= s.charAt(i);
ch += t.charAt(i);
}
return ch;
}
07 小结
算法专题目前已连续日更超过两个月,算法题文章82+篇,