专栏首页灵魂画师牧码画解算法:389. 找不同

画解算法:389. 找不同

题目链接 https://leetcode-cn.com/problems/find-the-difference/题目描述 给定两个字符串 s 和 t,它们只包含小写字母。字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。请找出在 t 中被添加的字母。示例:输入:
s = "abcd"
t = "abcde"

输出:
e

解释:
'e' 是那个被添加的字母。
解题方案 思路标签:哈希表本题最容易想到的就是使用哈希表进行运算,遍历第一个字符串标记出现的字符数量,再遍历第二个减去出现的数量,直到遇到为0或者原哈希表就不存在的情况标签:异或运算除了上述方法外,会有一个更tricky的解法,就是使用字符(注意不是字符串)异或运算,尽管并没有降低时间复杂度,但也是一种开阔思路的解题方式使用异或运算可以解题主要因为异或运算有以下几个特点:一个数和0做XOR运算等于本身:a⊕0 = a一个数和其本身做XOR运算等于0:a⊕a = 0XOR运算满足交换律和结合律:a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b故而在以上的基础条件上,将所有数字按照顺序做抑或运算,最后剩下的结果即为唯一的数字时间复杂度:O(m+n),m为字符串s的长度,n为字符串t的长度代码Java版本class Solution {
    public char findTheDifference(String s, String t) {
        char ans = t.charAt(t.length()-1);
        for(int i = 0; i < s.length(); i++) {
            ans ^= s.charAt(i);
            ans ^= t.charAt(i);
        }
        return ans;
    }
}
JavaScript版本JavaScript由于没有字符位运算所以无法使用异或运算解法。故而使用了第一种哈希表的解法/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
    const map = new Map();
    for(let i = 0; i < s.length; i++) {
        const val = map.get(s[i]);
        map.set(s[i], val === undefined ? 1 : val + 1);
    }
    for(let i = 0; i < t.length; i++) {
        const val = map.get(t[i]);
        if(val === 0 || val === undefined) {
            return t[i];
        } else {
            map.set(t[i], val - 1);
        }
    }
};
画解后台回复「算法」,加入天天算法群觉得算法直击灵魂,欢迎点击在看和转发

本文分享自微信公众号 - 牧码啦(mumalo),作者:灵魂画师牧码

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ​画解算法:100. 相同的树

    https://leetcode-cn.com/problems/same-tree/

    灵魂画师牧码
  • 我体验开源世界的这几年

    开源软件在好多年前就已经在软件开发技术人群中火热起来,最著名的开源软件平台GitHub也成为了程序员聚集地,甚至于GitHub上的Star数量一度成为了招聘加分...

    灵魂画师牧码
  • 画解算法:13. 罗马数字转整数

    https://leetcode-cn.com/problems/roman-to-integer/

    灵魂画师牧码
  • mybatis报Could not find result map java.lang.Integer之类的错误

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    suveng
  • 《Go 语言程序设计》读书笔记 (一)基础类型和复合类型

    最近在读《Go 语言程序设计》这本书想通过看书巩固一下自己的基础知识,把已经积累的点通过看书学习再编织成一个网,这样看别人写的优秀代码时才能更好理解。当初工作中...

    KevinYan
  • 远程升级准备工作: 安装Web服务器

      前言:大家可以安装Apache,Tomcat,nginx 等Web服务器软件,这篇文章安装 OpenResty 作为Web服务器软件,该软件安装在云端电脑,...

    杨奉武
  • unique函数

    现在总结一下unique,unique的作用是“去掉”容器中相邻元素的重复元素(不一定要求数组有序),它会把重复的元素添加到容器末尾(所以数组大小并没有改变),...

    用户7727433
  • Linux下使用yum安装LNMP环境

    北溟有鱼QAQ
  • 毛骨悚然,亚马逊AI突然笑出声来

    ? 最近有件事,又把美国人民吓到了。 全都怪亚马逊Alexa。 Alexa,就是亚马逊基于AI技术推出的语音助手,就相当于iPhone手机里的Siri,但是要...

    量子位
  • C++ STL算法系列4---unique , unique_copy函数

     一.unique函数 类属性算法unique的作用是从输入序列中“删除”所有相邻的重复元素。 该算法删除相邻的重复元素,然后重新排列输入范围内的元素,并且返回...

    猿人谷

扫码关注云+社区

领取腾讯云代金券