LeetCode算法题-Find the Difference(Java实现-五种解法)

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+篇,