389.找不同

LeetCode LeetCode 哈希表排序字符串位运算

发布时间 : 2000-01-10 03:08

字数:1.5k 阅读 :

评论:

389.找不同

389.找不同

389.1 题目

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

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

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

示例 1：

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

示例 2：

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

提示：

0 <= s.length <= 1000
t.length == s.length + 1
s 和 t 只包含小写字母

389.2 题解

方法一：List添加后移除

思路

将字符串 t 的所有字符加入 List，然后遍历字符串 s，依次从 List 中移除对应字符。最终 List 中剩余的唯一字符就是被添加的字母。

核心思想：用 List 模拟集合差运算。

具体步骤：

将字符串 t 的所有字符加入 List。
遍历字符串 s，从 List 中移除对应字符。
List 中剩余的唯一字符即为答案。

举例：对于 s = "abcd", t = "abcde"：

tList：['a', 'b', 'c', 'd', 'e']
遍历 s：移除 a → ['b', 'c', 'd', 'e']
移除 b → ['c', 'd', 'e']
移除 c → ['d', 'e']
移除 d → ['e']
结果：'e'

复杂度分析

时间复杂度：O(n²)，List.Remove 是线性查找。
空间复杂度：O(n)，List 存储字符。

代码

// 方法一：List添加后移除
static char FindAddedChar1(string s, string t)
{
    // 创建一个字符列表用于存储字符串 t 的每个字符
    List<char> tList = new List<char>();
    foreach (var item in t)
    {
        // 将字符串 t 的每个字符添加到列表中
        tList.Add(item);
    }

    // 遍历字符串 s 的每个字符
    foreach (var item in s)
    {
        // 如果列表中包含当前字符，移除列表中的该字符
        if (tList.Contains(item))
        {
            tList.Remove(item);
        }
    }

    // 返回列表中剩余的字符，即在字符串 t 中被添加的字符
    return tList[0];
}

方法二：求和后作差

思路

分别计算两个字符串的 ASCII 码总和，差值即为被添加字符的 ASCII 码。将差值强转为字符即可。

核心思想：字符求和差值 = 被添加字符的 ASCII 码。

具体步骤：

计算字符串 t 的所有字符 ASCII 码总和 tSum。
计算字符串 s 的所有字符 ASCII 码总和 sSum。
返回 (char)(tSum - sSum)。

举例：对于 s = "abcd", t = "abcde"：

sSum = 97 + 98 + 99 + 100 = 394
tSum = 97 + 98 + 99 + 100 + 101 = 495
tSum - sSum = 101
(char)101 = 'e'
结果：'e'

复杂度分析

时间复杂度：O(n)，遍历两个字符串。
空间复杂度：O(1)，只使用常数变量。

代码

// 方法二：求和后作差强转成字符
static char FindAddedChar2(string s, string t)
{
    // 初始化变量用于存储字符串 t 的字符总和
    int tSum = 0;
    foreach (var item in t)
    {
        // 将字符串 t 的每个字符的 ASCII 值累加到总和中
        tSum += item;
    }

    // 初始化变量用于存储字符串 s 的字符总和
    int sSum = 0;
    foreach (var item in s)
    {
        // 将字符串 s 的每个字符的 ASCII 值累加到总和中
        sSum += item;
    }

    // 返回字符总和的差值，将其强制转换为字符，即在字符串 t 中被添加的字符
    return (char)(tSum - sSum);
}

389.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定两个字符串 s 和 t ，它们只包含小写字母。
        // 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
        // 请找出在 t 中被添加的字母。

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

        // 示例 2：
        // 输入：s = "", t = "y"
        // 输出："y"

        // 提示：
        // 0 <= s.length <= 1000
        // t.length == s.length + 1
        // s 和 t 只包含小写字母

        #endregion

        #region 测试

        // 示例 1
        string s1 = "abcd";
        string t1 = "abcde";
        char result1 = FindAddedChar1(s1, t1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        char result1_2 = FindAddedChar2(s1, t1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        string s2 = "";
        string t2 = "y";
        char result2 = FindAddedChar1(s2, t2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        char result2_2 = FindAddedChar2(s2, t2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：List添加后移除
    static char FindAddedChar1(string s, string t)
    {
        // 创建一个字符列表用于存储字符串 t 的每个字符
        List<char> tList = new List<char>();
        foreach (var item in t)
        {
            // 将字符串 t 的每个字符添加到列表中
            tList.Add(item);
        }

        // 遍历字符串 s 的每个字符
        foreach (var item in s)
        {
            // 如果列表中包含当前字符，移除列表中的该字符
            if (tList.Contains(item))
            {
                tList.Remove(item);
            }
        }

        // 返回列表中剩余的字符，即在字符串 t 中被添加的字符
        return tList[0];
    }

    // 方法二：求和后作差强转成字符
    static char FindAddedChar2(string s, string t)
    {
        // 初始化变量用于存储字符串 t 的字符总和
        int tSum = 0;
        foreach (var item in t)
        {
            // 将字符串 t 的每个字符的 ASCII 值累加到总和中
            tSum += item;
        }

        // 初始化变量用于存储字符串 s 的字符总和
        int sSum = 0;
        foreach (var item in s)
        {
            // 将字符串 s 的每个字符的 ASCII 值累加到总和中
            sSum += item;
        }

        // 返回字符总和的差值，将其强制转换为字符，即在字符串 t 中被添加的字符
        return (char)(tSum - sSum);
    }

    #endregion
}

389.4 运行结果

示例1 方法1 输出：e
示例1 方法2 输出：e
示例2 方法1 输出：y
示例2 方法2 输出：y

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com