设为首页收藏本站
切换到宽版

 找回密码
 注册
搜索
批处理之家»论坛 › 批处理专区: BAT CMD DOS › 出题挑战 › [挑战题]Largest Number
[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
123下一页
返回列表 发新帖
查看: 65698|回复: 33

[挑战题]Largest Number

[复制链接]
523066680
发表于 2016-8-23 10:22:13 | 显示全部楼层 |阅读模式
本帖最后由 523066680 于 2016-8-23 10:52 编辑

这里有一个算法竞赛网站出的题目 https://leetcode.com/problems/largest-number/

你可以选自己擅长的语言做题并上传代码，该网站会用各种极端情况的输入值测试你的代码，如果没有出错，则同其他人上传的代码效率做比较、排名

问题179. Largest Number
  1. Given a list of non negative integers, arrange them such that they form the largest number.

  3. For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

  5. Note: The result may be very large, so you need to return a string instead of an integer.

  7. Credits:
  8. Special thanks to @ts for adding this problem and creating all test cases.

  10. Subscribe to see which companies asked this question
复制代码
以下是本人渣翻译

  2. 给出一系列正整数，对这些数进行排列，使其拼凑出一个尽可能大（最大）的数。

  4. 例如，给出[3, 30, 34, 5, 9]，则这些数所能拼凑出的最大数字是 9534330。

  6. 注：给出的数组元素数量不定，结果可能非常非常大，所以你需要将结果作为字符串返回而不是int类型的整数（尤其是对于那些强类型的语言）
复制代码
可惜可以在该网站上传测试的语言类型有限，C/C++, java, python, ruby, js, go
回复

举报

523066680
 楼主| 发表于 2016-8-23 10:47:00 | 显示全部楼层
本帖最后由 523066680 于 2016-8-23 10:57 编辑

本人上一次用C挑战的结果。测试221种输入情况累计用时 4ms-6ms




某群里最快的是0ms-2ms区间，C语言 （据说用语法糖越多的语言用时越多
回复

举报

CrLf
发表于 2016-8-23 18:41:57 | 显示全部楼层
本帖最后由 CrLf 于 2016-8-23 19:16 编辑

JavaScript 136ms：
  1. var largestNumber = function(nums) {
  2.         return [].join.call(arguments)
  3.         .split(',')
  4.         .sort(function(a,b){
  5.                 return b+a > (a+b) ? 1 : -1
  6.         })
  7.         .join('').replace(/^0+(.)/,'$1')
  8. }
复制代码
不懂那些更快的是怎么实现的，好想看一看...
回复

举报

523066680
 楼主| 发表于 2016-8-23 18:51:18 | 显示全部楼层
本帖最后由 523066680 于 2016-8-23 19:02 编辑

回复 3# CrLf


    更快的当然是把那些sort函数之类的自己用更底层的语言实现啦。
好消息是我之前编译能过的代码现在不仅测试不通过而且本地编译运行崩溃，哈哈哈哈
回复

举报

CrLf
发表于 2016-8-23 19:04:12 | 显示全部楼层
回复 4# 523066680


    JavaScript 组有人是 120ms，比我快多了，实在想不出来他把时间省在哪里了
    回头我也用c玩一个
回复

举报

pcl_test
发表于 2016-8-23 20:46:19 | 显示全部楼层
本帖最后由 pcl_test 于 2016-8-23 20:56 编辑
  1. #*&cls&gawk -f "%~f0"&pause&exit

  3. BEGIN{
  4.     str="3,30,34,5,9"
  5.     split(str,a,",");
  6.     if(length(a)==1){
  7.         print a[1];
  8.     }else{
  9.         if(str~/^[0,]*$/){
  10.             print 0;
  11.         }else{
  12.             for(i=1;i<=length(a);i++){
  13.                 if(a[i]~/^0+[1-9][0-9]*$/){
  14.                     sub(/^0+/,"",a[i]);
  15.                 }else{
  16.                     if(a[i]~/^0+$/)sub(/0+/,"0",a[i]);
  17.                 }
  18.                 t=a[i];
  19.                 j=i-1;
  20.                 while(j>=1&&(!comp(a[j],t))){
  21.                     a[j+1]=a[j];
  22.                     j--;
  23.                 }
  24.                 a[j+1]=t;
  25.             }
  26.             for(i=1;i<=length(a);i++)s=s""a[i];
  27.             print s;
  28.         }
  29.     }
  30. }
  31. function comp(a,b){return (a""b)*1>(b""a)*1?1:0;}
复制代码

评分

参与人数 1PB +6 收起 理由
523066680 + 6 类C

查看全部评分

回复

举报

xxpinqz
发表于 2016-8-23 23:33:13 | 显示全部楼层
本帖最后由 xxpinqz 于 2016-8-24 12:57 编辑

  2. @echo off&setlocal enabledelayedexpansion
  3. set "s=89 89891 830 8308 8300 89899 9 999999999999999999999 9999999999999999999999999999"
  4. for %%a in (%s%) do (
  5.     set "a=%%a%%a%%a%%a%%a%%a%%a%%a%%a!random!"
  6.     set #!a!=%%a
  7. )
  8. (for /f "tokens=2 delims==" %%a in ('set # ^|sort /r') do set/p.=%%a)<nul
  9. pause
复制代码
变量a受最长的数值影响。。。。。。

评分

参与人数 1技术 +1 收起 理由
happy886rr + 1 几乎批处理不可能的，一个sort就完事了

查看全部评分

回复

举报

CrLf
发表于 2016-8-24 02:43:58 | 显示全部楼层
回复 2# 523066680


    看完夜场谍影重重，回家撸了C语言
221 / 221 test cases passed.
Status: Accepted
Runtime: 0 ms

还不下跪

评分

参与人数 1PB +12 收起 理由
523066680 + 12 斯国一

查看全部评分

回复

举报

523066680
 楼主| 发表于 2016-8-24 08:31:54 | 显示全部楼层
本帖最后由 523066680 于 2016-8-24 08:42 编辑

回复 7# xxpinqz


    当输入数字是 830 8308 时，显示结果为：8308
回复

举报

CrLf
发表于 2016-8-24 09:21:50 | 显示全部楼层
JavaScript 124ms：
  1. var largestNumber = function(nums) {
  2.     var arr = [];
  3.     [].forEach.call(arguments,function(a){a.map?[].push.apply(arr,a):arr.push(a)})
  4.         return arr
  5.             .sort(function(a,b){
  6.                     return ''+b+a > ''+a+b ? 1 : -1
  7.             })
  8.             .join('').replace(/^0+(.)/,'$1')
  9. }
复制代码
C语言 0ms：
  1. char* largestNumber(int* nums, int numsSize) {
  2.         struct struct_num{
  3.                 int digit;
  4.                 int number;
  5.         };

  7.         struct struct_num *group[10][100], *pg, *pg2;
  8.         int group_count[10]={0,0,0,0,0,0,0,0,0,0};
  9.         int i,j,k;
  10.         int number,index,digit;
  11.         char output[10000]="0";
  12.         char *p=output;

  14.         const char itoa_map[11]="0123456789";

  16.         for(i=numsSize;i--;){
  17.                 number = nums[i];

  19.                 for(digit=10;number>=digit;digit*=10){}
  20.                 index = number/(digit/10);

  22.                 pg=(struct struct_num *)malloc(sizeof(struct struct_num));

  24.                 group[index][group_count[index]++]=pg;
  25.                 (pg)->number = number;
  26.                 (pg)->digit = digit;
  27.         }

  29.         for(i=10;i--;){
  30.                 for(j=group_count[i];j-->0;){
  31.                         pg = group[i][j];

  33.                         for(k=j;k-->0;){
  34.                                 pg2 = group[i][k];
  35.                                 if(
  36.                                         ((long long) pg->number * pg2->digit+pg2->number)< ((long long) pg2->number * pg->digit + pg->number)
  37.                                 ){
  38.                                         * (long long*) pg ^= * (long long*) pg2;
  39.                                         * (long long*) pg2 ^= * (long long*) pg;
  40.                                         * (long long*) pg ^= * (long long*) pg2;
  41.                                 }
  42.                         }
  43.                 }
  44.                 for(j=group_count[i];j--;){
  45.                         pg = group[i][j];
  46.                         number = pg->number;
  47.                         digit = pg->digit / 10;
  48.                         while(digit >= 1){
  49.                                 *p++ = itoa_map[number / digit % 10];
  50.                                 digit /= 10;
  51.                         }
  52.                         free(pg);
  53.                 }
  54.         }
  55.         if(output[0]=='0')return "0";

  57.         *p='\0';

  59.         return output;
  60. }
复制代码

评分

参与人数 2技术 +2 收起 理由
happy886rr + 1 大师的代码如此深奥
523066680 + 1 先顶

查看全部评分

回复

举报

523066680
 楼主| 发表于 2016-8-24 10:07:30 | 显示全部楼层
大家都习惯花括号不换行吗……
回复

举报

xxpinqz
发表于 2016-8-24 12:58:48 | 显示全部楼层
回复 9# 523066680

嗯，不截取就好，我干嘛去截取。谢谢！
回复

举报

xxpinqz
发表于 2016-8-24 13:01:47 | 显示全部楼层
回复 8# CrLf

听说谍影系列不适合看3d版。。。晃不
没影院放2d的。
回复

举报

523066680
 楼主| 发表于 2016-8-24 14:39:59 | 显示全部楼层

转一个别人的代码


  2. #define _CRT_SECURE_NO_WARNINGS

  4. #include <stdint.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include <stdio.h>

  9. int Comparer(char * strLeft, char * strRight)
  10. {
  11.         char * cmpLeft = strLeft;
  12.         char * cmpRight = strRight;
  13.         for (;; ++cmpLeft, ++cmpRight)
  14.         {
  15.                 char chLeft = *cmpLeft;
  16.                 char chRight = *cmpRight;

  18.                 if (!chLeft && !chRight)
  19.                         return 0;

  21.                 if (!chLeft)
  22.                 {
  23.                         cmpLeft = strRight;
  24.                         chLeft = *cmpLeft;
  25.                 }

  27.                 if (!chRight)
  28.                 {
  29.                         cmpRight = strLeft;
  30.                         chRight = *cmpRight;
  31.                 }

  33.                 if (chLeft == chRight)
  34.                         continue;
  35.                 else
  36.                         return chLeft > chRight;
  37.         }
  38.         return 0;
  39. }

  41. void QS_Swap(char ** left, char ** right)
  42. {
  43.         char * tmp = *left;
  44.         *left = *right;
  45.         *right = tmp;
  46. }

  48. int QS_Partition(char ** arr, int lo, int hi)
  49. {
  50.         char * pivot = arr[hi];
  51.         int i = lo;

  53.         for (int j = lo; j < hi; ++j)
  54.         {
  55.                 if (Comparer(arr[j], pivot))
  56.                 {
  57.                         QS_Swap(&arr[i], &arr[j]);
  58.                         ++i;
  59.                 }
  60.         }
  61.         QS_Swap(&arr[i], &arr[hi]);
  62.         return i;
  63. }

  65. void QS_Sort(char ** arr, int lo, int hi)
  66. {
  67.         if (lo < hi)
  68.         {
  69.                 int p = QS_Partition(arr, lo, hi);
  70.                 QS_Sort(arr, lo, p - 1);
  71.                 QS_Sort(arr, p + 1, hi);
  72.         }
  73. }

  75. void QSort(char ** arr, int len)
  76. {
  77.         QS_Sort(arr, 0, len - 1);
  78. }

  80. char * largestNumber(int * nums, int numsSize)
  81. {
  82.         char * strBuf = (char*)malloc(numsSize * 16);
  83.         char ** strNums = (char**)malloc(sizeof(char*) * numsSize);
  84.         int szTotalLen = 0;
  85.         for (int i = 0; i < numsSize; ++i)
  86.         {
  87.                 //char * strItem = _itoa(pNums[i], strBuf, 10);
  88.                 sprintf(strBuf, "%d", nums[i]);
  89.                 char * strItem = strBuf;

  91.                 int slen = strlen(strItem);
  92.                 szTotalLen += slen;

  94.                 strBuf += slen + 1;
  95.                 strNums[i] = strItem;
  96.         }

  98.         QSort(strNums, numsSize);

  100.         strBuf = (char*)malloc(szTotalLen + 1);
  101.         char * strRes = strBuf;
  102.         for (int i = 0; i < numsSize; ++i)
  103.         {
  104.                 char * strItem = strNums[i];
  105.                 strcpy(strBuf, strItem);
  106.                 strBuf += strlen(strItem);
  107.         }

  109.         while (*strRes == '0' && *(strRes + 1))
  110.                 ++strRes;

  112.         return strRes;
  113. }

  115. int main()
  116. {
  117.         int nums[] = { 0, 0, 1 };
  118.         char *s = largestNumber(nums, sizeof(nums) / sizeof(nums[0]));
  119.         printf("%s", s);

  121.         return 0;
  122. }
复制代码
回复

举报

CrLf
发表于 2016-8-24 16:21:16 | 显示全部楼层
回复 13# xxpinqz


    说实话，不是很喜欢谍影重重5这种全程高能的肌肉片
回复

举报

下一页 »
123下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|批处理之家 ( 渝ICP备10000708号 )

GMT+8, 2026-3-17 00:33 , Processed in 0.024801 second(s), 9 queries , File On.

Powered by Discuz! X3.5

© 2001-2026 Discuz! Team.

快速回复 返回顶部 返回列表