从C到Capable-----找不同

☀(day55:C5)

目录

题目:

题目分析:

解题思路:

解法一:常规解法

代码实现

✨代码注释 

解法二:ASCII码求和

代码实现

✨代码注释

解法三:位运算

代码实现

✨代码注释


题目:

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

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

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

⭐示例 1:

输入:s = "abcd", t = "abcde"

输出:"e"

说明:'e' 是那个被添加的字母。

⭐示例 2:

输入:s = "", t = "y"

输出:"y"

题目分析:

注意题目中的字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。着就意味着唯一个不同的字母再t中。

解题思路:

解法一:常规解法

由分析我们知道我们找的不同也就是唯一个不同的字母再t中。

那么为了找出这个不同的字母我们可以个s字符串中的每一个字母做一个标记,接着遍历字符串t,如果t中的某个字母没有标记,则这个字母就是唯一不同的那个。

那么这个标记我们可以使用赋值来表示。我们先创建一个长度为26的数组用来“储存”s字符串的每个字符。其中的储存并不是真正的储存,而是以字母的ASCII值 - ‘a’ 的ASCII值 = i以i作为数组索引来给数组下标为i的元素赋值。

这样当s字符串中的字母为a时,a的ASCII值 - a的ASCII值 = i = 0,下标0就代表字母a的位置,当字母为z时,z的ASCII值 - a的ASCII值 = i = 26,下标26就代表字母a的位置.那么我们给对应下标i位置赋值也就相当于给对应的字母做标记。这也解释了数组的长度为什么要设为26.

那么,在遍历s时我们根据字母给对应下标为i的位置+1(会有重复字母我们也重复+1),接着我们再遍历字符串t,根据字母给对应下标为i的位置-1(会有重复字母我们也重复-1)。由于t中有一个字母时s中没有的,那么这个字母对应的位置-1后就是负数(-1),这时我们就可以判断那个位置上为负数,根据位置推出相应字母即可。

代码实现

# include 
# include 

char findTheDifference(char* s, char* t)
{
    int arr[26];
    memset(arr, 0, sizeof(arr));
    int n = strlen(s);
    int m = strlen(t);

    for (int i = 0; i < n; i++)
        arr[s[i] - 'a']++;

    for (int i = 0; i < m; i++)
    {
        arr[t[i] - 'a']--;
        if (arr[t[i] - 'a'] < 0)
            return t[i];
    }
    return ' ';
}

void main (void)
{
    char s[4] = "abc";
    char t[5] = "abce";
    char differen;

    differen = findTheDifference(s, t);
    printf("%c", differen);
}

✨代码注释 

# include 
# include 

char findTheDifference(char* s, char* t)
{
    int arr[26];
    // 使用memset函数将数组arr的元素全部初始化为0
    memset(arr, 0, sizeof(arr));
    // 使用strlen方法获取s和t字符串长度并分别赋值给n,m
    int n = strlen(s);
    int m = strlen(t);

    for (int i = 0; i < n; i++)
        // 遍历s的字母并将字母对应下标i的位置+1
        arr[s[i] - 'a']++;

    for (int i = 0; i < m; i++)
    {
        // 遍历t的字母并将字母对应下标i的位置-1
        arr[t[i] - 'a']--;
        // 判断-1后改位置上的数是否<0,<0则找到不同的字母
        if (arr[t[i] - 'a'] < 0)
            return t[i];
    }
    return ' ';
}

void main (void)
{
    char s[4] = "abc";
    char t[5] = "abce";
    char differen;

    differen = findTheDifference(s, t);
    printf("%c", differen);
}

这里简单说一下memset()函数的用法。memset(buffer, c, count)

buffer:为指针或是数组,

c:是赋给buffer的值,

count:是buffer的长度.

上面代码中表示,将数组buffer中的值全部赋值为c

代码时间复杂度为O(n+m)n和m分别为字符串s和t的长度,空间复杂度为O(k)k = 26.

还不了解时间复杂度,空间复杂度的同学可以看这里:一个小故事带你了解大O表示法

解法二:ASCII码求和

上面我们说到ASCII码,我们也知道每个字母都有对应的ASCII值,那么不同的字符又是唯一的,所以我们只需要分别将s和t字符串中所有字母对应的ASCII值相加,接着再将s的总ASCII值 - t的总ASCII值,那么得到的差就是不同的那个字母的ASCII值。

代码实现

# include 
# include 

char findTheDifference(char* s, char* t)
{
    int n = strlen(s), m = strlen(t);
    int ASCII_s = 0;
    int ASCII_t = 0;

    for (int i = 0; i < n; i++)
        ASCII_s += s[i];

    for (int i = 0; i < m; i++)
        ASCII_t += t[i];

    return ASCII_t - ASCII_s;
}

void main (void)
{
    char s[4] = "abc";
    char t[5] = "abce";
    char difference;

    difference = findTheDifference(s, t);
    printf("%c", difference);
}

✨代码注释

# include 
# include 

char findTheDifference(char* s, char* t)
{
    // 使用strlen方法获取s和t字符串长度并分别赋值给n,m
    int n = strlen(s), m = strlen(t);
    // ASCII_s,ascii_t分别表示s和t的总ASCII值
    int ASCII_s = 0;
    int ASCII_t = 0;

    // 求s中所有字母的ASCII值
    for (int i = 0; i < n; i++)
        ASCII_s += s[i];
    // 求t中所有字母的ASCII值
    for (int i = 0; i < m; i++)
        ASCII_t += t[i];

    return ASCII_t - ASCII_s;
}

void main (void)
{
    char s[4] = "abc";
    char t[5] = "abce";
    char difference;

    difference = findTheDifference(s, t);
    printf("%c", difference);
}

遍历s和t,时间复杂度O(n+m)。用有限变量储存数值,空间复杂度O(1).

解法三:位运算

不了解位运算的同学可以看这里:还在为原码、反码、补码和位运算搞得头昏脑涨?点这里,还你清析脑回路​​​​​​

 再位运算中,按位异或有个特点:当使用按位异或不断运算具相同的数时最后的结果为0.

如我们先将0分别与1,2,4进行位运算

0^1 = 1, 1^2 = 3, 3^4 = 7

我们再将7,分别与1,2,4(或4,1,2,可任意转换位置)进行位运算,

7^1 = 6, 6^2 = 4, 4^4 = 0

我们看到最终的运算又回到了运算起点0(把0换成其他数也是回到运算开始的数),那么我们也可以使用同样的方法位运算s,t中字母的ASCII的值,要是最终运算结果为0说明s和t相同,不为0则最后运算的数即为该字母的ascii值。

代码实现

# include 
# include 

char findTheDifference(char* s, char* t) 
{
    int n = strlen(s), m = strlen(t);
    int result = 0;
    for (int i = 0; i < n; i++)
        result ^= s[i];

    for (int i = 0; i < m; i++)
        result ^= t[i];

    return result;
}

void main (void)
{
    char s[4] = "abc";
    char t[5] = "abce";
    char difference;

    difference = findTheDifference(s, t);
    printf("%c", difference);
}

✨代码注释

# include 
# include 

char findTheDifference(char* s, char* t)
{
    // 使用strlen方法获取s和t字符串长度并分别赋值给n,m
    int n = strlen(s), m = strlen(t);
    int result = 0;
    // 对s中所有字母的ascii值进行按位异或运算
    for (int i = 0; i < n; i++)
        result ^= s[i];
    
    // 对t中所有字母的ascii值进行按位异或运算
    for (int i = 0; i < m; i++)
        result ^= t[i];

    return result;
}

void main (void)
{
    char s[4] = "abc";
    char t[5] = "abce";
    char difference;

    difference = findTheDifference(s, t);
    printf("%c", difference);
}

遍历s和t,时间复杂度O(n+m)。用有限变量储存数值,空间复杂度O(1).

今天就到这,明天见。

❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄

你可能感兴趣的