[挑战题]Largest Number
[i=s] 本帖最后由 523066680 于 2016-8-23 10:52 编辑 [/i]这里有一个算法竞赛网站出的题目 [url]https://leetcode.com/problems/largest-number/[/url]
你可以选自己擅长的语言做题并上传代码，该网站会用各种极端情况的输入值测试你的代码，如果没有出错，则同其他人上传的代码效率做比较、排名
问题179. Largest Number[code]Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
[/code]以下是本人渣翻译[code]
给出一系列正整数，对这些数进行排列，使其拼凑出一个尽可能大（最大）的数。
例如，给出[3, 30, 34, 5, 9]，则这些数所能拼凑出的最大数字是 9534330。
注：给出的数组元素数量不定，结果可能非常非常大，所以你需要将结果作为字符串返回而不是int类型的整数（尤其是对于那些强类型的语言）
[/code]可惜可以在该网站上传测试的语言类型有限，C/C++, java, python, ruby, js, go [i=s] 本帖最后由 523066680 于 2016-8-23 10:57 编辑 [/i]
本人上一次用C挑战的结果。测试221种输入情况累计用时 4ms-6ms
[img]http://imgout.ph.126.net/51733001/100percent.jpg[/img]
[img]http://imgout.ph.126.net/51733002/100percent2.jpg[/img]
某群里最快的是0ms-2ms区间，C语言 （据说用语法糖越多的语言用时越多 [i=s] 本帖最后由 CrLf 于 2016-8-23 19:16 编辑 [/i]
JavaScript 136ms：[code]var largestNumber = function(nums) {
return [].join.call(arguments)
.split(',')
.sort(function(a,b){
return b+a > (a+b) ? 1 : -1
})
.join('').replace(/^0+(.)/,'$1')
}[/code]不懂那些更快的是怎么实现的，好想看一看... [i=s] 本帖最后由 523066680 于 2016-8-23 19:02 编辑 [/i]
[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=189308&ptid=41474]3#[/url] [i]CrLf[/i] [/b]
更快的当然是把那些sort函数之类的自己用更底层的语言实现啦。
好消息是我之前编译能过的代码现在不仅测试不通过而且本地编译运行崩溃，哈哈哈哈 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=189309&ptid=41474]4#[/url] [i]523066680[/i] [/b]
JavaScript 组有人是 120ms，比我快多了，实在想不出来他把时间省在哪里了
回头我也用c玩一个 [i=s] 本帖最后由 pcl_test 于 2016-8-23 20:56 编辑 [/i]
[code]#*&cls&gawk -f "%~f0"&pause&exit
BEGIN{
str="3,30,34,5,9"
split(str,a,",");
if(length(a)==1){
print a[1];
}else{
if(str~/^[0,]*$/){
print 0;
}else{
for(i=1;i<=length(a);i++){
if(a[i]~/^0+[1-9][0-9]*$/){
sub(/^0+/,"",a[i]);
}else{
if(a[i]~/^0+$/)sub(/0+/,"0",a[i]);
}
t=a[i];
j=i-1;
while(j>=1&&(!comp(a[j],t))){
a[j+1]=a[j];
j--;
}
a[j+1]=t;
}
for(i=1;i<=length(a);i++)s=s""a[i];
print s;
}
}
}
function comp(a,b){return (a""b)*1>(b""a)*1?1:0;}[/code] [i=s] 本帖最后由 xxpinqz 于 2016-8-24 12:57 编辑 [/i]
[code]
@echo off&setlocal enabledelayedexpansion
set "s=89 89891 830 8308 8300 89899 9 999999999999999999999 9999999999999999999999999999"
for %%a in (%s%) do (
set "a=%%a%%a%%a%%a%%a%%a%%a%%a%%a!random!"
set #!a!=%%a
)
(for /f "tokens=2 delims==" %%a in ('set # ^|sort /r') do set/p.=%%a)<nul
pause
[/code]变量a受最长的数值影响。。。。。。 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=189286&ptid=41474]2#[/url] [i]523066680[/i] [/b]
看完夜场谍影重重，回家撸了C语言
[quote]221 / 221 test cases passed.
Status: Accepted
Runtime: 0 ms[/quote]
还不下跪 [i=s] 本帖最后由 523066680 于 2016-8-24 08:42 编辑 [/i]
[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=189319&ptid=41474]7#[/url] [i]xxpinqz[/i] [/b]
当输入数字是 830 8308 时，显示结果为：8308 JavaScript 124ms：[code]var largestNumber = function(nums) {
var arr = [];
[].forEach.call(arguments,function(a){a.map?[].push.apply(arr,a):arr.push(a)})
return arr
.sort(function(a,b){
return ''+b+a > ''+a+b ? 1 : -1
})
.join('').replace(/^0+(.)/,'$1')
}[/code]C语言 0ms：[code]char* largestNumber(int* nums, int numsSize) {
struct struct_num{
int digit;
int number;
};
struct struct_num *group[10][100], *pg, *pg2;
int group_count[10]={0,0,0,0,0,0,0,0,0,0};
int i,j,k;
int number,index,digit;
char output[10000]="0";
char *p=output;
const char itoa_map[11]="0123456789";
for(i=numsSize;i--;){
number = nums[i];
for(digit=10;number>=digit;digit*=10){}
index = number/(digit/10);
pg=(struct struct_num *)malloc(sizeof(struct struct_num));
group[index][group_count[index]++]=pg;
(pg)->number = number;
(pg)->digit = digit;
}
for(i=10;i--;){
for(j=group_count[i];j-->0;){
pg = group[i][j];
for(k=j;k-->0;){
pg2 = group[i][k];
if(
((long long) pg->number * pg2->digit+pg2->number)< ((long long) pg2->number * pg->digit + pg->number)
){
* (long long*) pg ^= * (long long*) pg2;
* (long long*) pg2 ^= * (long long*) pg;
* (long long*) pg ^= * (long long*) pg2;
}
}
}
for(j=group_count[i];j--;){
pg = group[i][j];
number = pg->number;
digit = pg->digit / 10;
while(digit >= 1){
*p++ = itoa_map[number / digit % 10];
digit /= 10;
}
free(pg);
}
}
if(output[0]=='0')return "0";
*p='\0';
return output;
}[/code] 大家都习惯花括号不换行吗…… [b]回复 [url]9#[/url] [i]523066680[/i] [/b]
嗯，不截取就好，我干嘛去截取。谢谢！ [b]回复 [url]8#[/url] [i]CrLf[/i] [/b]
听说谍影系列不适合看3d版。。。晃不
没影院放2d的。
转一个别人的代码
[code]#define _CRT_SECURE_NO_WARNINGS
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int Comparer(char * strLeft, char * strRight)
{
char * cmpLeft = strLeft;
char * cmpRight = strRight;
for (;; ++cmpLeft, ++cmpRight)
{
char chLeft = *cmpLeft;
char chRight = *cmpRight;
if (!chLeft && !chRight)
return 0;
if (!chLeft)
{
cmpLeft = strRight;
chLeft = *cmpLeft;
}
if (!chRight)
{
cmpRight = strLeft;
chRight = *cmpRight;
}
if (chLeft == chRight)
continue;
else
return chLeft > chRight;
}
return 0;
}
void QS_Swap(char ** left, char ** right)
{
char * tmp = *left;
*left = *right;
*right = tmp;
}
int QS_Partition(char ** arr, int lo, int hi)
{
char * pivot = arr[hi];
int i = lo;
for (int j = lo; j < hi; ++j)
{
if (Comparer(arr[j], pivot))
{
QS_Swap(&arr[i], &arr[j]);
++i;
}
}
QS_Swap(&arr[i], &arr[hi]);
return i;
}
void QS_Sort(char ** arr, int lo, int hi)
{
if (lo < hi)
{
int p = QS_Partition(arr, lo, hi);
QS_Sort(arr, lo, p - 1);
QS_Sort(arr, p + 1, hi);
}
}
void QSort(char ** arr, int len)
{
QS_Sort(arr, 0, len - 1);
}
char * largestNumber(int * nums, int numsSize)
{
char * strBuf = (char*)malloc(numsSize * 16);
char ** strNums = (char**)malloc(sizeof(char*) * numsSize);
int szTotalLen = 0;
for (int i = 0; i < numsSize; ++i)
{
//char * strItem = _itoa(pNums[i], strBuf, 10);
sprintf(strBuf, "%d", nums[i]);
char * strItem = strBuf;
int slen = strlen(strItem);
szTotalLen += slen;
strBuf += slen + 1;
strNums[i] = strItem;
}
QSort(strNums, numsSize);
strBuf = (char*)malloc(szTotalLen + 1);
char * strRes = strBuf;
for (int i = 0; i < numsSize; ++i)
{
char * strItem = strNums[i];
strcpy(strBuf, strItem);
strBuf += strlen(strItem);
}
while (*strRes == '0' && *(strRes + 1))
++strRes;
return strRes;
}
int main()
{
int nums[] = { 0, 0, 1 };
char *s = largestNumber(nums, sizeof(nums) / sizeof(nums[0]));
printf("%s", s);
return 0;
}[/code] [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=189331&ptid=41474]13#[/url] [i]xxpinqz[/i] [/b]
说实话，不是很喜欢谍影重重5这种全程高能的肌肉片 好像还可以继续优化，可惜没有微秒和纳秒，比较不出来 [b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=189344&ptid=41474]16#[/url] [i]CrLf[/i] [/b]
PowerShell的 Measure-Command 可以获取到 Ticks
1 Ticks = 100 纳秒 = 1/10000 毫秒 [i=s] 本帖最后由 523066680 于 2016-8-24 18:43 编辑 [/i]
[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=189351&ptid=41474]17#[/url] [i]GNU[/i] [/b]
他们当然知道如何获取更详细的时间单位，说的是那个网站的在线测试的时间单位精度有限。
再说线下比较还可以增加测试次数和列表数据量。所以不同的结论需要结合前后文(Context)。 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=189329&ptid=41474]11#[/url] [i]523066680[/i] [/b]
是否可以用快速排序 [b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=189356&ptid=41474]19#[/url] [i]happy886rr[/i] [/b]
? 贴了一个别人的，好像是快速排序 C[code]
void q_sort(char* arr[], const int len) {
typedef struct _Range {
int start, end;
} Range;
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
if (len <= 0)
return;
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
char* mid = arr[range.end], * cp;
int left = range.start, right = range.end - 1;
while (left < right) {
while (GTR(mid, arr[left]) && left < right)
left++;
while (!GTR(mid, arr[right]) && left < right)
right--;
cp = arr[left], arr[left] = arr[right], arr[right] = cp;
}
if (!GTR(mid, arr[left]))
cp = arr[left], arr[left] = arr[range.end], arr[range.end] = cp;
else
left++;
r[p++] = new_Range(range.start, left - 1);
r[p++] = new_Range(left + 1, range.end);
}
}
int GTR(char* s1, char* s2) {
char * p1 = s1, * p2 = s2;
while (1) {
if (!*p1 && !*p2) return 1;
if (!*p1) p1 = s2;
if (!*p2) p2 = s1;
if (*p1 > *p2)
return 1;
else if (*p1 < *p2)
return 0;
else p1++, p2++;
}
}
char* largestNumber(int* nums, int numsSize) {
char strs [numsSize][11], * strPtrs[numsSize], * cp1, * cp2, * strRet = malloc(10 * numsSize + 1), ch;
int i, j, k, t;
for (i = 0; i < numsSize; i++) {
t = *(nums + i);
j = 0;
k = -1;
// digits convert to string
do {
strs[i][j++] = '0' + t % 10;
} while ((t /= 10) > 0);
strs[i][j] = '\0';
// reverse string
*(strPtrs + i) = cp1 = *(strs + i);
while (--j > ++k)
* (cp1 + j) ^= *(cp1 + k), * (cp1 + k) ^= *(cp1 + j), * (cp1 + j) ^= *(cp1 + k);
}
q_sort(strPtrs, numsSize);
// printf("After q_sort\n");
// for (i = numsSize - 1; i >= 0; i--) printf("%s\n", strPtrs[i]);
cp2 = strRet;
if (strPtrs[numsSize - 1][0] == '0') {
*strRet = '0';
*(strRet + 1) = '\0';
return strRet;
}
for (i = numsSize - 1; i >= 0; i--) {
cp1 = *(strPtrs + i);
while (ch = *(cp1++)) *(cp2++) = ch;
}
*cp2 = '\0';
return strRet;
}
[/code] [i=s] 本帖最后由 CrLf 于 2016-8-25 00:29 编辑 [/i]
[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=189356&ptid=41474]19#[/url] [i]happy886rr[/i] [/b]
感觉排序方式不是最重要的，个人经验，结构优化的收益远比冒泡和快速排序之间的效率差异大得多：[code]1、用结构体 struct_num 保存数字和进位，排序时用 (long long) 数值比较大小，等到输出时再转为字符串
2、分设 10 个数组 hash 表，用于保存由 0-9 开头的数字组成的数组，这样只需要对 1-9 各组单独排序即可
3、函数自实现/内联，就题解题，节省函数调用开销[/code] [b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=189364&ptid=41474]22#[/url] [i]CrLf[/i] [/b]
没仔细看你的代码, 估计用到了这种方式
比较 830 和 8308
预处理时, 计算出了大于 各数位数 的最小的 10 的幂
830(1000), 8308(10000)
比较时:
互相乘以对方的特征幂 再加上对方, 得到等位数拼接串:
830 * 10000 + 8308 <--> 8308 * 1000 + 830
最后得到比较结果
为防止 int 类型溢出, 必须用超出 int 范围的类型处理
字符数组指针方式比较仍然烦琐 [i=s] 本帖最后由 aa77dd@163.com 于 2016-8-26 20:40 编辑 [/i]
[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=189308&ptid=41474]3#[/url] [i]CrLf[/i] [/b]
多测试几次就能做到, 我用同一个代码提交了多次
最慢时 184ms, 最快时 116ms
在 my submissions 里记录了每一次提交测试的结果[code]/**
* @param {number[]} nums
* @return {string}
*/
var largestNumber = function(nums) {
nums = nums.map(function(num) {
return '' + num;
});
var rs=[],re=[],p=0;
rs[p] = 0;
re[p++]= nums.length-1;
var ss,ee,t;
while (p) {
ss = rs[--p];
ee = re[p];
if (ss >= ee)
continue;
var mid = nums[ee];
var left = ss, right = ee - 1;
while (left < right) {
while (nums[left] + mid > mid + nums[left] && left < right)
left++;
while (mid + nums[right] >= nums[right] + mid && left < right)
right--;
t = nums[left];
nums[left] = nums[right];
nums[right] = t;
}
if (mid + nums[left] >= nums[left] + mid) {
t = nums[left];
nums[left] = nums[ee];
nums[ee] = t;
} else
left++;
rs[p] = ss;
re[p++] = left - 1;
rs[p] = left + 1;
re[p++] = ee;
}
if (nums[0] == 0) return '0';
return nums.join('');
};[/code] 为啥你们脑袋这么好使呢，在这论坛混了这么久，还是只会bat。 [i=s] 本帖最后由 523066680 于 2016-8-26 23:33 编辑 [/i]
[b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=189516&ptid=41474]25#[/url] [i]xxpinqz[/i] [/b]
个人意见：
多学几种语言，批处理之后，推荐ruby 或者 python，最好先熟悉C语言。
然后如果要自己打造应用，C# 或者 C++
刚工作那会儿有大量时间，我很后悔在批处理特效上面花太多时间，我不是说特效没卵用，而是搞图形的话应该一开始就上C/C++，可惜，当时缺少视野。
然后花了小量时间学Python，放弃后转而投入大量业余时间学Perl，这是手感上和批处理最像的。不过我觉得时间成本不太划算，C#、C++可以做更多的事。
最后，关于语言的吐槽，推荐一本书：《程序员的呐喊》 [i=s] 本帖最后由 xxpinqz 于 2016-8-27 00:04 编辑 [/i]
[b]回复 [url]26#[/url] [i]523066680[/i] [/b]
过谦了。
谢谢你的建议。奶瓶、尿布得花费好大精力了，实在力所不及。
学无先后，达者为师。你也不必介怀当年所耗费精力，毕竟假设的条件就是假设。
而且也说不准你这学习的精神就是你当年留下的烙印。况且能在喜欢的事情上下功夫，本身就是一种乐趣~
发现本帖跑题的都是我~~~
这书在豆瓣上评价不错，有空看看，爱看书，但都是0.1桶水。。 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=189511&ptid=41474]24#[/url] [i]aa77dd@163.com[/i] [/b]
要看稳定值，我看到120毫秒那个档很集中，绝不是偶然，一定有什么我还没想到的办法 [b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=189524&ptid=41474]26#[/url] [i]523066680[/i] [/b]
这书扫完了。这作者的套路就是放地图炮喷或者狂奶某个语言，然后再指责别人狂热不可理喻，能在言语上无论如何都让自己站在比较优越的位置。本身就是个语言宗教粉，但是会标榜自己是自由主义。 [i=s] 本帖最后由 happy886rr 于 2016-11-14 00:49 编辑 [/i]
故题重游，C语言版：
Submission Details
221 / 221 test cases passed.
Status: Accepted
Runtime: 0 ms[code]
char outStr[];
int CompNums(const void* a, const void* b){
char* str1=*(char**)a;
char* str2=*(char**)b;
int i, L1=strlen(str1), L2=strlen(str2);
for(i=0; i<10; i++){
if(*str1=='\0'){str1-=L1;}
if(*str2=='\0'){str2-=L2;}
if(*str1 != *str2){break;}
str1++, str2++;
}
return *str2-*str1;
}
char* largestNumber(int* nums, int numsSize) {
int i;
outStr[0]=0;
char* p[numsSize];
for(i=0; i<numsSize; i++){p[i]=(char*)malloc(sizeof(char)*16);sprintf(p[i], "%d\0", nums[i]);}
qsort(p, numsSize, sizeof(char*), CompNums);
for(i=0; i<numsSize; i++){strcat(outStr, p[i]);}
return outStr[0]=='0'?"0":outStr;
}
[/code]>>>
补充，针对本帖所有回帖的C代码，在100万次的测试当中，只有21楼aa77dd@163.com兄的代码速度最快，100万次耗时0.7秒，本人用itoa函数也只能做到100万次耗时1.1秒。其他C语言方案均耗时数秒，并且存在严重漏洞。
>>>
另外小于5000次的测试根本无法体现性能，几乎都是0毫秒。只在百万次的测试上个别方案才会出现极大的漏洞。
页:
[1]
2