11

我正在做一个问题，上面写着“连接单词以生成字典顺序最低的字符串”。从比赛中。

以这个字符串为例：jibw ji jp bw jibw

实际输出结果是：bw jibw jibw ji jp

当我对此进行排序时，我得到：bw ji jibw jibw jp。

这是否意味着这不是排序？如果是排序，“字典”排序是否考虑将较短的字符串推到后面或其他什么？

我一直在阅读字典顺序，但我没有看到任何使用它的点或场景，你有吗？

4

10 回答 10

25

看来您要寻找的是对问题的更好理解，所以让我说清楚。通常对字符串的排序是字典排序。如果将字符串 [jibw, ji, jp, bw, jibw] 排序为字典顺序，排序后的序列是[bw, ji, jibw, jibw, jp]，这就是你得到的。所以你的问题不在于理解“词典”这个词。你已经正确理解了。

你的问题是你误读了这个问题。该问题不要求您按字典顺序对字符串进行排序。（如果是这样，您通过排序得到的答案将是正确的。）相反，它要求您生成一个字符串，该字符串是通过以某种顺序连接输入字符串（即，使一个字符串没有空格）得到的，以便生成一个string 在字典上是最小的。

为了说明差异，请考虑通过连接排序序列和答案字符串获得的字符串：

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

现在，当您比较这两个字符串时——请注意，您只是在比较两个 14 个字符的字符串，而不是两个字符串序列——您可以看到正确的答案在字典上确实比您的答案小：您的答案以“bwjij”开头，而正确答案以“bwjib”开头，而“bwjib”按字典顺序排在“bwjij”之前。

希望你现在明白这个问题。这根本不是一个排序问题。（也就是说，对输入字符串进行排序不是问题。您可以对通过排列和连接输入字符串得到的所有可能的字符串进行排序；如果输入字符串的数量很少，这是解决问题的一种方法。）

于 2011-01-08T08:33:05.883 回答
1

您可以通过比较 word1 + word2 与 word2 + word1 将其转换为一个简单的排序问题。在 Python 中：

def cmp_concetanate(word1, word2):
    c1 = word1 + word2
    c2 = word2 + word1
    if c1 < c2:
        return -1
    elif c1 > c2:
        return 1
    else:
        return 0

将此比较功能与标准排序一起使用可以解决问题。

于 2011-01-18T04:35:35.120 回答
1

我一直在这个 Facebook 黑客杯中使用 F#。在这次比赛中学到了不少东西。由于网络上关于 F# 的文档还是很少见的，所以我想我不妨在这里分享一下。

此问题要求您根据自定义的比较方法对字符串列表进行排序。这是我在 F# 中的代码片段。


    let comparer (string1:string) (string2:string) =
         String.Compare(string1 + string2, string2 + string1)

    // Assume words is an array of strings that you read from the input
    // Do inplace sorting there
    Array.sortInPlaceWith comparer words
    // result contains the string for output
    let result = Array.fold (+) "" words
于 2011-01-27T14:08:42.560 回答
1

//使用此代码块打印数组的字典排序字符，或者它可以以多种方式使用。

  #include<stdio.h>
  #include<conio.h>

  void combo(int,int,char[],char[],int*,int*,int*);

  void main()
  {
      char a[4]={'a','b','c'};
      char a1[10];
      int i=0,no=0;
      int l=0,j=0;
      combo(0,3,a,a1,&j,&l,&no);
      printf("%d",no);
      getch();
  }
  void combo(int ctr,int n,char a[],char a1[],int*j,int*l,int*no)
  {
      int i=0;
      if(ctr==n)
      {
        for(i=0;i<n;i++)
            printf("%c",a1[i]);
        printf("\n");
        (*no)++;
        (*j)++;
        if((*j)==n)
        { 
            *l=0;
             *j=0;
        }
        else
        *l=1;       
        getch();
      }
      else
        for(i=0;i<n;i++)
        {
        if(*l!=1)
            *j=i;
        a1[ctr]=a[*j];
        combo(ctr+1,n,a,a1,j,l,no);
        }
    }
于 2013-03-26T18:09:15.793 回答
0

一个仅涉及排序的简单技巧（在指定最大字符串长度时适用于此问题）是使用字符串中的第一个字母将所有字符串填充到最大长度。然后对填充的字符串进行排序，但输出原始未填充的字符串。例如。对于字符串长度 2 和输入 b 和 ba，您将排序 bb 和 ba，这将给您 ba 和 bb，因此您应该输出 bab。

于 2011-01-09T15:23:11.617 回答
0

如果您在字符串排序函数中使用一个特殊的“占位符”字符填充，该字符的权重可能大于“z”，那么 Prasun 的技巧就会奏效。结果将为您提供最低词典组合的顺序。

于 2011-01-09T18:00:20.933 回答
0

您发布的示例表明，仅排序不会生成字典顺序最低的字符串。对于给定的问题，您需要应用一些额外的技巧来确定哪个字符串应该在哪个之前（截至目前，我想不出确切的方法）

实际输出不违反词典最低单词的条件。

于 2011-01-08T06:39:36.630 回答
0

检查这里发生了什么：

如果您只是应用字典排序，您将得到 bw ji jibw jibw jp 但如果您逐个分析令牌，您会发现“bwjibw”（bw，jibw）在字典上低于“bwjijibw”（bw，ji，jibw）这就是为什么答案是 bw jibw jibw ji jp 因为首先你应该附加 bwjibwjibw 然后你可以连接 ji 和 jp 以获得最低的字符串。

于 2011-01-08T07:51:10.350 回答
0

linux 上的 sort 命令也进行字典排序，并按 bw ji jibw jibw jp 的顺序生成输出

于 2011-01-08T07:07:17.667 回答
0

比赛结束了，所以我发布了一个可能的解决方案，不是最有效的，而是一种方法

 #include <iostream>
 #include <fstream>
 #include <string>
    #include <algorithm>
    using namespace std;
   int main()
  {
ofstream myfile;
myfile.open("output.txt");
int numTestCases;
int numStrings;
string* ptr=NULL;
char*ptr2=NULL;
string tosort;
scanf("%d",&numTestCases);
for(int i=0;i<numTestCases;i++)
{
    scanf("%d",&numStrings);
    ptr=new string[numStrings];
    for(int i=0;i<numStrings;i++)
    {
        cin>>ptr[i];
    }
    sort(ptr,ptr+numStrings);
    for(int i=0;i<numStrings;i++)
    {
        next_permutation(ptr,ptr+numStrings);
    }
    tosort.clear();
    for(int i=0;i<numStrings;i++)
    {
        tosort.append(ptr[i]);
    }
    ptr2=&tosort[i];

    cout<<tosort<<endl;
    myfile<<tosort<<endl;   
    delete[]ptr;
}
return 0;
  }

我在 C++ 中使用 STL 库中的算法，prev_permutation 函数只是生成按字典顺序排序的排列

于 2011-01-10T21:56:48.870 回答