Anagram - 最小删除次数 - 某些测试用例失败
Anagram - Minimum Number of deletion - failing certain test cases
这是一个解决以下问题的程序"Given two strings, and , that may or may not be of the same length, determine the minimum number of character deletions required to make and anagrams. Any characters can be deleted from either of the strings"。最后,两个字符串应该具有相同的字母和每个字母的相同频率。例如,字符串 A = ccda 字符串 B = dcac
我的逻辑是用虚拟字符串替换两个字符串中相同的字母,比如“0”。因此,当我计算每个字符串中不等于“0”的字母数时,它会给出删除的次数。
但我不知道为什么在某些情况下这会失败。
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int count =0;
const char dummy= '0';
int i =0, j=0;
char* a = (char *)malloc(512000 * sizeof(char));
scanf("%s",a);
char* b = (char *)malloc(512000 * sizeof(char));
scanf("%s",b);
for (i=0;a[i]!= '[=10=]' ;i++){
for(j=0; b[j]!= '[=10=]';j++){
if (a[i]==b[j]){
a[i]= dummy;
b[j]= dummy;
}
}
}
for (i=0;a[i]!= '[=10=]' ;i++){
if(a[i]!= dummy){
count = count+1;
}
}
for (i=0;a[i]!= '[=10=]' ;i++){
if(b[i]!= dummy){
count = count+1;
}
}
printf("%d",count);
return 0;
}
它失败的测试用例之一是
字符串 A : fcrxzwscanmligyxyvym
字符串 B : jxwtrhvujlmrpdoqbisbwhmgpmeoke
给出的结果:22
预期结果:30
任何人都可以指出我这里的错误。请提前致谢!
您的代码中有一个错误 - 第二个循环中的条件无效。
for (i=0;a[i]!= '[=10=]' ;i++){
if(a[i]!= dummy){
count = count+1;
}
}
for (i=0;a[i]!= '[=10=]' ;i++){
^^^^
if(b[i]!= dummy){
count = count+1;
}
}
标记点应该是b[i]
而不是a[i]
。
小毛病:由于您正在学习编码,因此在学习过程中尽量养成一些有用的习惯。代码应该漂亮(请注意,不是很漂亮,而是苦行僧)——它有助于您和其他人轻松阅读。结果很重要。如果你在运算符周围做空格,那么到处都做。布局很重要。所有这些都会帮助您注意到您的(专业人士也很常见,他们只是更快发现)错误。
在 运行 性能方面还有更好的算法。 :)
这是一个解决以下问题的程序"Given two strings, and , that may or may not be of the same length, determine the minimum number of character deletions required to make and anagrams. Any characters can be deleted from either of the strings"。最后,两个字符串应该具有相同的字母和每个字母的相同频率。例如,字符串 A = ccda 字符串 B = dcac 我的逻辑是用虚拟字符串替换两个字符串中相同的字母,比如“0”。因此,当我计算每个字符串中不等于“0”的字母数时,它会给出删除的次数。 但我不知道为什么在某些情况下这会失败。
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int count =0;
const char dummy= '0';
int i =0, j=0;
char* a = (char *)malloc(512000 * sizeof(char));
scanf("%s",a);
char* b = (char *)malloc(512000 * sizeof(char));
scanf("%s",b);
for (i=0;a[i]!= '[=10=]' ;i++){
for(j=0; b[j]!= '[=10=]';j++){
if (a[i]==b[j]){
a[i]= dummy;
b[j]= dummy;
}
}
}
for (i=0;a[i]!= '[=10=]' ;i++){
if(a[i]!= dummy){
count = count+1;
}
}
for (i=0;a[i]!= '[=10=]' ;i++){
if(b[i]!= dummy){
count = count+1;
}
}
printf("%d",count);
return 0;
}
它失败的测试用例之一是 字符串 A : fcrxzwscanmligyxyvym 字符串 B : jxwtrhvujlmrpdoqbisbwhmgpmeoke 给出的结果:22 预期结果:30
任何人都可以指出我这里的错误。请提前致谢!
您的代码中有一个错误 - 第二个循环中的条件无效。
for (i=0;a[i]!= '[=10=]' ;i++){
if(a[i]!= dummy){
count = count+1;
}
}
for (i=0;a[i]!= '[=10=]' ;i++){
^^^^
if(b[i]!= dummy){
count = count+1;
}
}
标记点应该是b[i]
而不是a[i]
。
小毛病:由于您正在学习编码,因此在学习过程中尽量养成一些有用的习惯。代码应该漂亮(请注意,不是很漂亮,而是苦行僧)——它有助于您和其他人轻松阅读。结果很重要。如果你在运算符周围做空格,那么到处都做。布局很重要。所有这些都会帮助您注意到您的(专业人士也很常见,他们只是更快发现)错误。 在 运行 性能方面还有更好的算法。 :)