CTF of Z2BNS
0%

找不同

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

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

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

示例1：

1
2
3
输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。

示例2：

1
2
输入：s = "", t = "y"
输出："y"

示例3：

1
2
输入：s = "a", t = "aa"
输出："a"

示例4：

1
2
输入：s = "ae", t = "aea"
输出："a"

提示：

  • 0 <= s.length <= 1000
  • t.length == s.length + 1
  • s 和 t 只包含小写字母
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

计数法：

unordered_map集合（字符为键，次数为值）存储两个字符串中字符出现的次数，只有添加的一个字母次数为奇数其余都为偶数，遍历集合返回值为奇数的键。

c++代码：(执行用时4ms，击败73.81%，内存消耗7.2M，击败5.03%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    char findTheDifference(string s, string t) {
        unordered_map<char,int> m;
        for(char c:s){
            ++m[c];
        }
        for(char c:t){
            ++m[c];
        }
        //遍历容器查找值为奇数（注意是奇数不是1）的键返回
        for(auto p:m){
            if(p.second%2==1){
                return p.first;
            }
        }
        //避免报错，随便返回一个字符
        return 'a';
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：计数
首先遍历字符串 s，对其中的每个字符都将计数值加 1；然后遍历字符串 t，对其中的每个字符都将计数值减 1。当发现某个字符计数值为负数时，说明该字符在字符串 t 中出现的次数大于在字符串 s 中出现的次数，因此该字符为被添加的字符。

c++代码：(执行用时4ms，击败73.81%，内存消耗7M，击败9.86%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    char findTheDifference(string s, string t) {
        vector<int> cnt(26, 0);
        for (char ch: s) {
            cnt[ch - 'a']++;
        }
        for (char ch: t) {
            cnt[ch - 'a']--;
            if (cnt[ch - 'a'] < 0) {
                return ch;
            }
        }
        return ' ';
    }
};

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$ 为字符串的长度。

  • 空间复杂度：$O(|\Sigma|)$，其中 $\Sigma$ 是字符集，这道题中字符串只包含小写字母，$|\Sigma|=26$。需要使用数组对每个字符计数。

方法二：求和

将字符串 s 中每个字符的 ASCII 码的值求和，得到 $A_s$；对字符串 tt 同样的方法得到

$A_t$ 。两者的差值 $A_t-A_s$即代表了被添加的字符。

c++代码：(执行用时0ms，击败100.00%，内存消耗7M，击败17.30%）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        int as = 0, at = 0;
        for (char ch: s) {
            as += ch;
        }
        for (char ch: t) {
            at += ch;
        }
        return at - as;
    }
};

复杂度分析

  • 时间复杂度：$O(N)$。

  • 空间复杂度：$O(1)$。

方法三：位运算

如果将两个字符串拼接成一个字符串，则问题转换成求字符串中出现奇数次的字符。

类似于「 只出现一次的数字」，我们使用位运算的技巧解决本题。

c++代码：(执行用时0ms，击败100.00%，内存消耗7M，击败8.27%）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        int ret = 0;
        for (char ch: s) {
            ret ^= ch;
        }
        for (char ch: t) {
            ret ^= ch;
        }
        return ret;
    }
};

复杂度分析

  • 时间复杂度：$O(N)$。

  • 空间复杂度：$O(1)$。

⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

题目也比较简单，官方题解给出了多种解法，也比较全面。

------------- THE END! THANKS! -------------