哈希表

找不同 画解算法:389.

作者:牧码啦 / 关注公众号:mumalo  发布:2019-11-01

题目链接
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 = 0
XOR运算满足交换律和结合律: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由于没有字符位运算所以无法使用异或运算解法。故而使用了第一种哈希表的解法
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); } }};画解
后台回复「算法」,加入天天算法群觉得算法直击灵魂,欢迎点击在看和转发


本文作者 :牧码啦

关注Ta的微信公众号获取更多图文精彩内容...