leetcode中如何解决找不同问题

这篇文章主要介绍了leetcode中如何解决找不同问题,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。

成都创新互联公司专注为客户提供全方位的互联网综合服务,包含不限于做网站、网站设计、安图网络推广、微信小程序、安图网络营销、安图企业策划、安图品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们最大的嘉奖;成都创新互联公司为所有大学生创业者提供安图建站搭建服务,24小时服务热线:18980820575,官方网址:www.cdcxhl.com

 

题目链接

https://leetcode-cn.com/problems/find-the-difference/

 

题目描述

给定两个字符串 st,它们只包含小写字母。

字符串 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由于没有字符位运算所以无法使用异或运算解法。故而使用了第一种哈希表的解法

/**
* @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);
       }
   }
};
   

画解

leetcode中如何解决找不同问题

leetcode中如何解决找不同问题

感谢你能够认真阅读完这篇文章,希望小编分享的“leetcode中如何解决找不同问题”这篇文章对大家有帮助,同时也希望大家多多支持创新互联,关注创新互联行业资讯频道,更多相关知识等着你来学习!


分享题目:leetcode中如何解决找不同问题
文章来源:http://pwwzsj.com/article/ppohci.html