发布时间:2023-09-03 12:30
☀(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值,那么不同的字符又是唯一的,所以我们只需要分别将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❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄