算法题每日一练—第51天：找不同-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、问题描述

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

题目链接：找不同。

二、题目要求

样例 1

输入： s = "abcd", t = "abcde"
输出： "e"
解释： 'e' 是那个被添加的字母。
复制代码

样例 2

输入： s = "", t = "y"
输出： "y"
复制代码

考察

1.map的简单应用，位运算
2.建议用时15~30min
复制代码

三、问题分析

本题是位运算的第6题，没了解过位运算相关知识点可以看这一篇文章，讲解比较详细：

算法题每日一练—第45天：位运算

1.map

就像小时候玩的找不同一样，只不过这次只有一个不同，我们可以使用map函数分别统计字符串 s 和 t 每个字符出现的次数，如果哪一个字符出现的次数不一样，那就找到咧。

也可以排序之后，逐位对比。

2.位运算

字符如何和位运算靠上关系？如果我们将两个字符串拼接成一个，那么不同的那一个出现的次数肯定是奇数，因为没人配对，所以我们可以使用位运算的异或运算，之前这一篇文章算法题每日一练—第46天：只出现一次的数字思路差不多。

四、编码实现

1.map

class Solution {
public:
    char findTheDifference(string s, string t) {
       int i;
       map<char,int>a,b; //map初始化定义两个数组     
       for(i=0;i<s.size();i++)//遍历字符串s的字符
            a[s[i]]++;//统计数目
       for(i=0;i<t.size();i++)//遍历字符串t的字符
           b[t[i]]++;//统计数目
        for(char j='a';j<='z';j++)//只有小写字母
        {
            if(a[j]!=b[j])//不相同
            {
                return j;//输出
            }
        }
    return 0;
    }
};
复制代码

2.位运算

class Solution {
public:
    char findTheDifference(string s, string t) {
    char ch=0;//初始化变量
    int i;
    for(i=0;i<s.size();i++)//异或第一个字符
    {
        ch=ch^s[i];
    } 
    for(i=0;i<t.size();i++)//异或第二个字符
    {
        ch=ch^t[i];
    } 
    return ch;//输出结果
    }
};
复制代码