题
我正在做一个问题,上面写着“串联以产生词典最低的弦。”从比赛中。
以此字符串为例: jibw ji jp bw jibw
实际产出的结果是: bw jibw jibw ji jp
当我对此进行分类时,我会得到: bw ji jibw jibw jp
.
这是否意味着这没有排序?如果是排序,“词典”分类是否考虑到将较短的字符串推向背面或其他东西?
我一直在阅读 词汇秩序 而且我看不到使用的任何点或方案,您有什么吗?
解决方案
看来您正在寻找的是对这个问题的更好理解,所以让我清楚地表明。通常对字符串进行分类 是 词典分类。如果将字符串[JIBW,JI,JP,BW,JIBW]排序为词典顺序,则分类序列 是 BW,JI,JIBW,JIBW,JP],这就是您得到的。因此,您的问题不是理解“词典”一词。您已经正确理解了它。
您的问题是您正在误读问题。这个问题不要求你 种类 字符串按词典顺序。 (如果确实如此,您通过排序得到的答案是正确的。)相反,它要求您生产 一 字符串,得到 串联 输入字符串以某种顺序(即,制作一个没有空间的字符串),因此所得的单字符串在词典上是最小的。
为了说明差异,请考虑通过串联排序序列和答案字符串来考虑您获得的字符串:
bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer
现在,当您比较这两个字符串时 - 请注意,您只是在比较两个14个字符的字符串,而不是两个字符串 - 您可以看到正确答案的确比您的答案要小于您的答案:您的答案以“ bwjij”开始,正确的答案以“ Bwjib”和“ Bwjib”开头,以词典序列为“ Bwjij”。
希望您现在了解这个问题。这根本不是一个分类问题。 (也就是说,这不是对输入字符串进行分类的问题。 可以 通过置换和串联输入字符串对所有可能的字符串进行分类;如果输入字符串的数量很少,这是解决问题的一种方法。
其他提示
您可以通过将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
使用此比较功能与标准排序解决问题。
我一直在这个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
//使用此代码块打印阵列的词典分类字符,或者可以通过多种方式使用。
#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);
}
}
您发布的示例表明,单纯的排序不会产生词典最低的字符串。对于给定的问题,您需要应用一些其他技巧来确定在哪个字符串之前(截至目前,我无法想到确切的方法)
实际输出不会违反词典最低词的条件。
Linux上的排序命令还进行词典分类,并以bw ji ji jibw jibw jp的顺序生成输出
检查这里发生的事情:
如果您只使用词典形式,您将获得BW JI JIBW JIBW JP,但是如果您通过令牌分析令牌,您会发现“ BWJIBW”(BW,JIBW)的词典比“ Bwjibw”低(BWJIBW”(BW,JI,JI,JI,JI,JI,JI,JI,JI,JI)这就是为什么答案是bw jibw jibw ji jp,因为首先,您应该附加bwjibwjibw,然后您可以加入JI和JP以获得最低的字符串。
一个仅涉及排序的简单技巧,它将适用于此问题,因为指定了最大字符串长度,将是将所有字符串添加到最大长度,并在字符串中的第一个字母。然后,您对填充的字符串进行排序,但输出原始的未加固的字符串。对于前。对于字符串长度2和输入B和BA,您将对BB和BA进行排序,这将为您提供BA和BB,因此您应该输出BAB。
如果您使用特殊的“占位符”字符添加,那么Prasun的技巧就可以使用,该角色可以加权以比字符串排序功能中的“ Z”大。结果将为您提供最低词典组合的顺序。
比赛已经结束,所以我发布了可能的解决方案,不是最有效的,而是一种方法
#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_PerMuart功能简单地生成置换词典。