Morgan和一个字符串算法 [英] Morgan and a String Algorithm

问题描述

我正在通过以下链接尝试问题：

I'm trying the problem from the following link:

https://www.hackerrank.com/challenges/morgan-and-a-string/problem

杰克和丹尼尔是朋友。他们两个都喜欢字母，尤其是
大写字母。他们削减报纸上的大写字母，
，每个字母都有自己的字母集合，分别存放在
中。美好的一天，摩根拜访了杰克和丹尼尔。
他看到了他们的收藏。摩根想知道，由这两个集合组成的
在字典上最小的字符串是什么。当
位于集合顶部时，他可以从集合中获取一封信。
另外，摩根还想使用男孩收藏中的所有字母。

Jack and Daniel are friends. Both of them like letters, especially upper-case ones. They are cutting upper-case letters from newspapers, and each one of them has their collection of letters stored in separate stacks. One beautiful day, Morgan visited Jack and Daniel. He saw their collections. Morgan wondered what is the lexicographically minimal string, made of that two collections. He can take a letter from a collection when it is on the top of the stack. Also, Morgan wants to use all the letters in the boys' collections.

我的代码如下：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

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字母大的字符。我每次都找不到正确的解决方案。

I compare both the strings after popping each character. Also, I've taken care of strings of unequal length by appending the shorter string with a character larger than any other alphabet in ASCII. I don't get the correct solution every time.

以下工作原理：

输入：

1
c
ca

预期和正确的输出：

cac

以下内容不是：

输入：

1
zbc
aaaaz

预期输出：

aaaazbcz

实际输出：

aaaazzbc

我想念的是什么？

推荐答案

我现在明白了。下列情况如何？

I got it now. How about the following case?

1
zbc
aaaaz

在您看到4个 a 之后，我们剩下一个 z 和 zbc [[其中 [是 'Z'+ 1 。显然， z < zbc [[会为 z zbc [[]中的$ c>，而不要选择另一个。结果应为 aaaazzbc ，而应为 aaaazbcz 。

As you see after 4 a's we're left with a z and zbc[[ where [ is 'Z'+1. Obviously, z<zbc[[ which creates trouble as the z of zbc[[ should be chosen and not the other one. The result would be aaaazzbc while it should be aaaazbcz.

那么，我们如何缓解这个问题呢？

So, how do we mitigate this problem?

我们每次弹出时都在末尾添加 [数组中的一个字符，以确保长度相等，以使 strcmp（）可以正常工作。这是接受的修改后的代码。太糟糕了，我放弃了，现在我无法在该点上得分。

We append a [ at the end every time we pop a character from an array to ensure the lengths are equal for strcmp() to work as intended. Here's the modified code that's accepted. Too bad I gave up and now I can't score points on that.

在这里供以后参考：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

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<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++]);a[x++]='Z'+1;a[x]='\0';}
            else {printf("%c",b[k++]);b[y++]='Z'+1;b[y]='\0';}

        }
        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;
}

这篇关于Morgan和一个字符串算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！