[leetcode]--389. Find the Difference

    xiaoxiao2021-03-26  11

    Question 389:

    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.

    z中文解释:

    字符串t是由字符串s创建出来的,只是字符串t比字符串s多加了一个字母.现在是要找出这个多加的字母.

    解决思路:这里提供两种解决思路:

    (1)利用两层遍历找出 单独的字符:

    源码如下:

    /** * 思路: 循环遍历字符串s,对每一个字符,到对应的字符串t中删除,知道最后t只有一个字符. * @param s 源字符串 * @param t 加了一个字符之后的字符串 * @return 新加的这个字符串 */ public static char findTheDifference(String s, String t) { //将两个字符串转换成字符数组 char[] schar = s.toCharArray(); char[] tchar = t.toCharArray(); //遍历字符串s的字符数组,然后再字符串t中删除对应的字符,最后字符串t就会只剩下一个字符,即结果. for(char c: schar){ for(int i=0; i<tchar.length; i++){ if(c == tchar[i]){ tchar[i] = ' '; break; } } } for(char tc: tchar){ if(tc != ' '){ return tc; } } return 'f'; }

    (2)利用亦或操作的特性 单独的字符:

    我们都知道亦或操作有一个特点:

    交换律 a^b = b^a结合律 a^b^c=a^(b^c)=(a^b)^c0^a=a 0与任何数亦或都是这个数a^a=0

    所以借助这个特点,通过亦或操作^ 字节对s和t全部执行亦或操作,因为a^a结果是0,所以最后的结果是单独的那个字符

    源码如下:

    /** * 第二种方法:通过亦或操作^ 字节对s和t全部执行亦或操作,因为a^a结果是0,所以最后的结果是单独的那个字符 * @param s * @param t * @return */ public static char findTheDifference2(String s, String t) { int c = t.charAt(0); for(int i=0; i<s.length(); i++){ c = c ^ s.charAt(i); } //注意 i为0时已经取出了,所以这里是从1开始的. for(int i=1; i<t.length(); i++){ c = c ^ t.charAt(i); } return (char)c; }

    测试案例:

    public static void main(String[] args) { if('a' == 'a'){ LogUtil.log_debug("true"); } LogUtil.log_debug("result:" + findTheDifference2("aebcd", "abcdfe")); }

    输出:

    f
    转载请注明原文地址: https://ju.6miu.com/read-650317.html

    最新回复(0)