编码挑战：安排数字以形成最大可能的整数 [英] Coding challenge: arrange numbers to form the largest possible integer
问题描述
今天的后期编码挑战很简单。
给定一组整数，排列整数，以便这样形成的最终整数是可能的最大整数。
例如。
{1,5,67,9}将被安排成96751
该列表最多可包含50个数字，每个数字将小于256且为正数。
我尝试过：
为了保持问题的含糊不清。
上周的获胜者是Graeme_Grant，主要是因为他教给我们所有我们从未知道的单词。向Sean发送你的详细信息和适当的东西（可能）将会回家。
The late coding challenge for today is straightforward.
Given a set of integers, arrange the integers so that the final integer thus formed is the largest number possible.
For example.
{ 1,5,67,9 } would be arranged to form 96751
The list may contain up to 50 numbers, and each number will be less than 256 and positive.
What I have tried:
To keep the problems suitably ambiguous.
Last week's winner was Graeme_Grant, mainly because he taught us all words we never knew. Send Sean your details and something (possibly) appropriate will wing it's way home.
推荐答案
System.Console.WriteLine ( BiggestIntegerInator
(
System.Environment.CommandLine.Rive
( Option.RemoveEmptyEntries
| Option.RemoveQuotes
| Option.HonorEscapes
| Option.HonorQuotes
)
) ) ;
（Rive在我的一篇文章中，它是Split的一个更灵活的版本。）< br $>
1 05 6.7E + 19收益率 96751
(Rive is in one of my Articles, it's a more flexible version of Split.)
1 05 6.7E+1 "9" yields 96751
private static string
BiggestIntegerInator
(
System.Collections.Generic.IList<string> Values
)
{
System.Text.StringBuilder result = new System.Text.StringBuilder() ;
System.Collections.Generic.SortedList<string,int> l =
new System.Collections.Generic.SortedList<string,int>
(
Values.Count
,
new DescendingComparer<string>()
) ;
for ( int i = 0 ; i < Values.Count ; i++ )
{
string v = Values [ i ] ;
double j ;
if ( System.Double.TryParse ( v , out j ) && ( ( v = j.ToString() ).IndexOf ( '.' ) == -1 ) )
{
if ( l.ContainsKey ( v ) )
{
l [ v ]++ ;
}
else
{
l [ v ] = 1 ;
}
}
}
for ( int i = 0 ; i < l.Count ; i++ )
{
string v = l.Keys [ i ] ;
for ( int j = 0 ; j < l [ v ] ; j++ )
{
result.Append ( v ) ;
}
}
return ( result.ToString() );
}
private class DescendingComparer<T> : System.Collections.Generic.IComparer<T>
where T : System.IComparable<T>
{
public int
Compare
(
T Op0
,
T Op1
)
{
return ( Op1.CompareTo ( Op0 ) ) ;
}
}
好的，所以上面的比较器不太合适，这是另一个：
OK, so that comparer above doesn't quite do the trick, here's another:
private class DescendingNumericStringComparer : System.Collections.Generic.IComparer<string>
{
public int
Compare
(
string Op0
,
string Op1
)
{
int result = 0 ;
int i0 = -1 ;
int i1 = -1 ;
while ( ( result == 0 ) && ( ( i0 < Op0.Length - 1 ) || ( i1 < Op1.Length - 1 ) ) )
{
if ( i0 < Op0.Length - 1 ) i0++ ;
if ( i1 < Op1.Length - 1 ) i1++ ;
result = Op1 [ i1 ].CompareTo ( Op0 [ i0 ] ) ;
}
if ( result == 0 )
{
result = Op0.Length.CompareTo ( Op1.Length ) ;
}
return ( result ) ;
}
}
43 432 435 433 收益 435 43 433 432
所以也是一个缺陷。这是一个肮脏的小修复（不建议，由于字符串操作），而我正在进行更好的实现：
43 432 435 433 yields 435 43 433 432
So that one has a flaw as well. Here's a dirty little fix (not recommended, due to string manipulation) while I work on a better implementation:
private class DescendingStringComparer : System.Collections.Generic.IComparer<string>
{
public int
Compare
(
string Op0
,
string Op1
)
{
int result = (Op1 + Op0).CompareTo ( Op0 + Op1 ) ;
if ( result == 0 )
{
result = Op0.Length.CompareTo ( Op1.Length ) ;
}
return ( result ) ;
}
}
24 242 243 收益 243 24 242
第四个比较器，没有字符串连接。
获取两个长度中的较长者并迭代。
当我们用其中一个值中的字符用完时，开始使用另一个值开头的字符。
24 242 243 yields 243 24 242
Fourth comparer, no string concatenation.
Get the longer of the two lengths and iterate.
When we run out of characters in one of the values, start using the characters at the start of the other value instead.
private class DescendingStringComparer : System.Collections.Generic.IComparer<string>
{
public unsafe int
Compare
(
string Op0
,
string Op1
)
{
int result = 0 ;
int len = Op0.Length > Op1.Length ? Op0.Length : Op1.Length ;
for ( int i = 0 ; ( result == 0 ) && ( i < len ) ; i++ )
{
char c0 = i < Op0.Length ? Op0 [ i ] : Op1 [ i - Op0.Length ] ;
char c1 = i < Op1.Length ? Op1 [ i ] : Op0 [ i - Op1.Length ] ;
result = c1.CompareTo ( c0 ) ;
}
if ( result == 0 )
{
result = Op0.Length.CompareTo ( Op1.Length ) ;
}
return ( result ) ;
}
}
My Clipper（类似FoxPro的xBase系列）语言。
程序：
1）转换为字符串
2）在填充相同大小后按相反顺序对数字进行排序。
My Clipper (xBase family like FoxPro) language once again.
Procedure:
1) Convert to strings
2) Sort the numbers in reverse order after some padding to same size.
* CCCP Code Challenge Code Project
* Build largest integer
clear
largest({1, 5, 67, 9})
largest({100, 11, 10, 110, 112,1,114})
largest({4, 45, 46, 43})
largest({43, 432, 435, 433})
largest({2, 243, 242, 245, 241, 24, 221})
largest({20, 221, 226, 202, 2, 201})
procedure largest(lst)
* convert 2 string
for scan=1 to len(lst)
lst[scan]= str(lst[scan],,,.T.)
next
?
? lst[1]
for scan=2 to len(lst)
?? " "
?? lst[scan]
next
* tri par insertion
for scan=2 to len(lst)
for ptr= scan to 2 step -1
* pad until same lentgh
mx= max(len(lst[ptr]), len(lst[ptr-1]))+1
tmp1= lst[ptr]
while len(tmp1) < mx
tmp1 += lst[ptr]
enddo
tmp1= left(tmp1,mx)
tmp2= lst[ptr-1]
while len(tmp2) < mx
tmp2 += lst[ptr-1]
enddo
tmp2= left(tmp2,mx)
if tmp1 > tmp2
tmp= lst[ptr]
lst[ptr]= lst[ptr-1]
lst[ptr-1]= tmp
endif
next
next
* result
? lst[1]
for scan=2 to len(lst)
?? " "
?? lst[scan]
next
return
没有填充的变体字符串：
Variant without padding the strings:
for scan=2 to len(lst)
for ptr= scan to 2 step -1
if len(lst[ptr])= len(lst[ptr-1])
tmp1= lst[ptr]
tmp2= lst[ptr-1]
else
mx= len(lst[ptr])+ len(lst[ptr-1])- 1
for scanl= 0 to mx
tmp1= lst[ptr, scanl%len(lst[ptr])+1]
tmp2= lst[ptr-1, scanl%len(lst[ptr-1])+1]
if tmp1 != tmp2
exit
endif
next
endif
if tmp1 > tmp2
tmp= lst[ptr]
lst[ptr]= lst[ptr-1]
lst[ptr-1]= tmp
endif
next
next
测试集
Test sets
1 5 67 9
9 67 5 1
100 11 10 110 112 1 114
114 112 11 1 110 10 100
4 45 46 43
46 45 4 43
43 432 435 433
435 43 433 432
2 243 242 245 241 24 221
245 243 24 242 241 2 221
20 221 226 202 2 201
226 2 221 202 20 201
注意：答案中的空格只是帮助读出如何订购数字。
[更新]精炼排序部分
填充部分非常棘手，我到目前为止最好的猜测：
填充是直到最大长度+ 1
填充是通过重复该值来进行的。
取20和202.什么是Ť他订购了吗？
填充：20 - > 2020,202 - > 2022
订单与2020年和2022年相同，所以202,20。
取24和242.订单是什么？
填充：24 - > 2424,242 - > 2422
订单与2424和2422相同，所以24,242。
Note: Spaces in answers just help reading out how numbers are ordered.
[Update] Refined the sort part
The padding part is really tricky, my best guess so far:
The padding is to be made until maximum length + 1
The padding is to be made by repeating the value.
Take 20 and 202. What is the order ?
padding: 20 -> 2020, 202 -> 2022
The order is same as for 2020 and 2022, so 202, 20.
Take 24 and 242. What is the order ?
padding: 24 -> 2424, 242 -> 2422
The order is same as for 2424 and 2422, so 24, 242.
一个LINQ单线程！ （嗯，说实话，大约八条线被残忍地捣碎成一条......）
A LINQ one-liner! (Well, to be honest, about eight lines brutally mashed into one...)
public static BigInteger DoChallenge(this IEnumerable<byte> question)
{
return (from x in question
orderby (x < 10) ? x * 1110 :
(x < 100) ? x * 100 + Math.Min(x, (x % 10) * 10 + x / 10) :
x * 10 descending
select new BigInteger(x))
.Aggregate((x, y) =>
(y < 10) ? x * 10 + y :
(y < 100) ? x * 100 + y :
x * 1000 + y);
}数学思想是将每个1-2位和3位数字转换为4位数字，以便进行排序：
- 123转到1230
- 12转到1212，在122（1220）和121（1210）之间切换
- 21转到2112，在212（2120）之间切换）和211（2110）
- 2进入2220，在223（2230）和221（2210）之间以及23（2323）和21（2112）之间插入
- 123 goes to 1230
- 12 goes to 1212, slotting it between 122 (1220) and 121 (1210)
- 21 goes to 2112, slotting it between 212 (2120) and 211 (2110)
- 2 goes to 2220, slotting it between 223 (2230) and 221 (2210), and between 23 (2323) and 21 (2112)
The math idea is to convert each 1- 2- and 3-digit number to a 4-digit number for the purposes of sorting:
这篇关于编码挑战：安排数字以形成最大可能的整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
