首页 > 试题广场 >

最大数

[编程题]最大数
  • 热度指数:38219 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个长度为n的数组nums,数组由一些非负整数组成,现需要将他们进行排列并拼接,每个数不可拆分,使得最后的结果最大,返回值需要是string类型,否则可能会溢出。

数据范围:
进阶:时间复杂度 ,空间复杂度:
示例1

输入

[30,1]

输出

"301"
示例2

输入

[2,20,23,4,8]

输出

"8423220"
示例3

输入

[2]

输出

"2"
示例4

输入

[10]

输出

"10"

备注:
输出结果可能非常大,所以你需要返回一个字符串而不是整数。
把数字转为字符串,然后strncmp进行比较,结合比较结果和不同情况,进行不同状态的特殊处理
本地仿真都正常,但就是结果结果不对
/**
 * 最大数
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return string字符串
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
static char str_ret[501] = {'\0'};
void swap(char *str1, char *str2)
{
    int str1_len = strlen(str1);
    int str2_len = strlen(str2);
    char tmp[6] = {'\0'};
    strcpy(tmp,str1);
                
    strcpy(str1,str2);
    strcpy(str2,tmp);   
    str1[str2_len] = '\0';
    str2[str1_len] = '\0';
}

int numtostring(int num, char *str)
{
    int str_index = 0;
    int multiple[4] = {0, 1,10,100,1000,10000};
    int tmp = 0; 
    int bit = 0;
    for(int i = 5; i > 0; i--)
    {
        bit = tmp / multiple[i];
        if((bit) || (str_index))   //高位0->不转换  高位非0及低位非0需要填充
        {
            str[str_index] = bit + '0' - 0;
            str_index++;
        }
        tmp = num % multiple[i];   //xxxxx
    }
    return str_index;
}

char* solve(int* nums, int numsLen ) {
    // write code here
    char str[100][6] = {'\0'};
    
    int str_ret_len = 0;
    int strlen1 = 0;
    int strlen2 = 0;
    int min_strlen = 0;
    int cmp_ret = 0;
    //char tmp[6] = {'\0'};
    for(int i = 0; i < numsLen; i++)
    {
        numtostring(nums[i], &str[i][0]);
    }
    
    for(int i = 0; i < numsLen; i++)
    {
        for(int j = i + 1; j < numsLen; j++)
        {
            strlen1 = strlen(&str[i][0]);
            strlen2 = strlen(&str[j][0]);/*
            if((str[j][strlen2 - 1] == '0') && (str[i][strlen1 - 1] != '0'))
            {
                str[j][strlen2 - 1] = '\0';                
                if(strcmp(&str[j][0],&str[i][0]) > 0) 
                    swap(&str[j][0],&str[i][0]);
                str[i][strlen2 - 1] = '0';      //恢复现场
                str[i][strlen2] = '\0';
            }
            else if((str[j][strlen2 - 1] != '0') && (str[i][strlen1 - 1] == '0'))
            {
                str[i][strlen1 - 1] = '\0';                
                if(strcmp(&str[j][0],&str[i][0]) > 0) 
                    swap(&str[j][0],&str[i][0]);
                str[j][strlen1 - 1] = '0';      //恢复现场               
                str[j][strlen1] = '0';
            }
            else */
            min_strlen = strlen1 > strlen2 ? strlen2 : strlen1;
            cmp_ret = strncmp(&str[j][0],&str[i][0],min_strlen);
            if(cmp_ret > 0)
            {
                swap(&str[j][0],&str[i][0]);
            }
            else if(cmp_ret == 0)
            {
                if(strlen1 > strlen2)
                {
                    if(str[i][strlen2] < str[i][0])
                    {
                        swap(&str[j][0],&str[i][0]);
                    }
                }
                else if(strlen1 < strlen2)
                {
                    if(str[i][0] < str[j][strlen1]) //比如str[i] = 2; str[j] = 23,需要进行替换,232
                    {
                        swap(&str[j][0],&str[i][0]);
                    }
                }
            }
        }
    }
    
    for(int i = 0; i < numsLen; i++)
    {        
        strcpy(&str_ret[str_ret_len],&str[i][0]);
        str_ret_len += strlen(str[i]);
    }
    str_ret[str_ret_len] = '\0';
    printf("%s\n",str_ret);
    return str_ret;
}

发表于 2021-11-30 20:52:10 回复(0)
C语言来完成是比较麻烦的,因为C语言中将整形变成字符串的函数itoa不在标准库中,这就需要自己来编写,思路是参照暴力解
char *itoa (int value,char str[],int radix)
{
 char temp[33];
  char *tp = temp;
  int i;
  unsigned v;
  int sign;
  char *sp;
  if(radix > 36 || radix < 1)
    return 0;
  sign = (radix == 10 && value < 0); //十进制负数
  if(sign)
    v = -value;
  else
    v = (unsigned)value;
  while(v || tp == temp)       //转化操作
  {
    i = v % radix;
    v = v / radix;
    if(i < 10)
      *tp++ = i + '0';
    else
      *tp++ = i + 'a' - 10;
  }
  if(str == 0)
    str = (char*)malloc((tp - temp) + sign + 1);
  sp = str;
  if(sign)   //是负数的话把负号先加入数组
    *sp++ = '-';
  while(tp > temp)
    *sp++ = *--tp;
  *sp = 0; 
 
  return str;
}



char* solve(int* nums, int numsLen ) {
    // write code here
    if( nums == NULL || numsLen == 0)
        return "";
    char str[10];
    char str1[10];
    char str2[10];
    char str3[10];
    int i,j,swap;
    for(i=0;i<numsLen-1;i++)
    {
        for(j=0;j<numsLen-i-1;j++)
        {
            memset(str,0,sizeof(10));
            memset(str1,0,sizeof(10));
            memset(str2,0,sizeof(10));
            memset(str3,0,sizeof(10));
            itoa(nums[j],str,10);
            itoa(nums[j+1],str1,10);
            printf("num[j]=%d\n",nums[j]);
            printf("num[j]=%d\n",nums[j+1]);            
            printf("%s\n",str);
            printf("%s\n",str1);
            strcpy(str2,str);
            strcpy(str3,str1);
            printf("%s\n",str2);
            printf("%s\n",str3);            
            strcat(str2,str1);
            strcat(str3,str);
            printf("%s\n",str2);
            printf("%s\n",str3);                
            if(!strcmp(str2,str3))
            {
                swap =nums[j];
                nums[i] =nums[j+1];
                nums[j+1]=swap;
            }
        }
    }
   static  char pnum[20]= {0};
    char iu[20] ={0};
    for(i=0;i<numsLen;i++)
    {
        itoa(nums[i],iu,10);
        printf("%d\n",nums[i]);
        printf("%s\n",iu);
        strcat(pnum,iu);
    }
    printf("%s\n",pnum);
    return pnum;
}

发表于 2021-11-04 15:55:20 回复(0)