福田企业网站推广哪个好,精品网游,wordpress静态nginx规则,广州教育网站建设一、题目 函数原型#xff1a;char findTheDifference(char * s, char * t) 二、思路 作者原先的思路是先将两个字符串从小到大排序#xff0c;然后两个字符串依次比较。若出现字符串t中的元素和字符串s不相等#xff0c;则说明该元素就是被添加的字母。 但是#xff0c;该… 一、题目 函数原型char findTheDifference(char * s, char * t) 二、思路 作者原先的思路是先将两个字符串从小到大排序然后两个字符串依次比较。若出现字符串t中的元素和字符串s不相等则说明该元素就是被添加的字母。 但是该算法时间上仅仅击败13.33%的人效率极低。 int cmp(const void *e1,const void *e2)
{return *(char*)e1 - *(char*)e2;
}char findTheDifference(char * s, char * t){int sz1strlen(s);int sz2strlen(t);qsort(s,sz1,1,cmp);qsort(t,sz2,1,cmp);int i0;for(i0;isz1;i){if(s[i]!t[i]s[i]t[i1]){return t[i];}}return t[i];
} 下面介绍几种时间效率比较高的算法 思路1 利用找单身狗的思想详见《leetcode136. 只出现一次的数字找单身狗》 将两个字符串全部进行异或运算最后得到的就是只出现一次的字母即被添加的字母 char findTheDifference(char* s, char* t) {char result0;int sz1strlen(s);int sz2strlen(t);for(int i0;isz1;i){result^s[i];}for(int i0;isz2;i){result^t[i];}return result;
} 思路2 用字符串t的字母总和减去字符串s的字母总和因为相同字母相减结果为0所以剩下的就是被添加的字母 char findTheDifference(char* s, char* t) {char result0;int sz1strlen(s);int sz2strlen(t);for(int i0;isz2;i){resultt[i];}for(int i0;isz1;i){result-s[i];}return result;
} 思路3 设置一个大小为26的数组初始值为0字母 a-z 分别对应位置 0-25 通过各字母通过减去a可以转换为对应的数字。先遍历字符串s当某个字母出现其对应的位置就1再遍历字符串t当某个字母出现其对应位置就-1。最后若某个位置变为了-1说明该字母在s中未出现在t中出现了该字母就是被添加的字母返回该字母即可。 char findTheDifference(char* s, char* t)
{int nums[26]{0};memset(nums,0,sizeof(nums));int sz1strlen(s);int sz2strlen(t);for(int i0;isz1;i){nums[s[i]-a];}for(int i0;isz2;i){nums[t[i]-a]--;if(nums[t[i]-a]-1)return t[i];}return ;
}
