摩根和一个字符串算法
我正在尝试以下链接中的问题:
https://www.hackerrank.com/challenges/morgan-and-a-string/problem
杰克和丹尼尔是朋友。 它们都像字母,特别是大写字母。 他们正在从报纸上剪下大写字母,并且每个人都将他们的信件集合存储在不同的堆栈中。 美好的一天,摩根访问了杰克和丹尼尔。 他看到了他们的藏品。 摩根想知道由这两个系列组成的字典最小字符串是什么。 当它位于堆栈顶部时,他可以从集合中收集一封信。 此外,摩根希望使用男孩collections中的所有字母。
我的代码如下:
#include #include #include #include int main() { int flag,choice; long n,i,j=0,k=0,x,y; char *a,*b; a=(char*)malloc(sizeof(char)*100000); b=(char*)malloc(sizeof(char)*100000); scanf("%ld",&n); for(i=0;i<n;i++){ j=k=0; scanf("%s%s",a,b); x=strlen(a); y=strlen(b); while(x<y)a[x++]='Z'+1; while(y<x)b[y++]='Z'+1; a[x]=b[y]='\0'; while(j<x && k<y && (a[j]!=('Z'+1) && b[k]!=('Z'+1))){ if(strcmp(a+j,b+k)<0)printf("%c",a[j++]); else printf("%c",b[k++]); } while(j<x && a[j]!=('Z'+1))printf("%c",a[j++]); while(k<y && b[k]!=('Z'+1))printf("%c",b[k++]); printf("\n"); } return 0; }
弹出每个字符后我比较两个字符串。 另外,我通过在ASCII中添加比任何其他字母更大的字符的较短字符串来处理不等长度的字符串。 我不是每次都得到正确的解决方案。
以下作品:
输入:
1 c ca
预期和正确的输出:
cac
以下不是:
输入:
1 zbc aaaaz
预期产量:
aaaazbcz
实际产量:
aaaazzbc
我错过了什么?
我现在明白了。 以下案例怎么样?
1 zbc aaaaz
正如你在4 a
后看到的那样,我们留下了z
和zbc[[
where [
是'Z'+1
。 显然, z
< zbc[[
会产生麻烦,因为zbc[[
的z
zbc[[
应该选择而不是另一个。 结果将是aaaazzbc
而它应该是aaaazbcz
。
那么,我们如何缓解这个问题呢?
每次我们从数组中弹出一个字符时,我们会追加[
最后确保strcmp()
的长度相等,以便按预期工作。 这是已接受的修改后的代码。 太糟糕了,我放弃了,现在我无法得分。
这是为了将来参考:
#include #include #include #include int main() { int flag,choice; long n,i,j=0,k=0,x,y; char *a,*b; a= malloc(sizeof(char)*200000); b= malloc(sizeof(char)*200000); scanf("%ld",&n); for(i=0;i