专栏首页chenjx85的技术专栏leetcode-179-Largest Number(理解规则,自定义cmp函数进行排序)

leetcode-179-Largest Number(理解规则,自定义cmp函数进行排序)

题目描述:

给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210

示例 2:

输入: [3,30,34,5,9]
输出: 9534330

说明: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。

要完成的函数:

string largestNumber(vector<int>& nums) 

说明:

1、这道题给定一个vector,里面存放着int类型的非负整数,要求把这些非负整数拼起来,尽可能拼成一个最大的整数。

比如[10,2],可以拼成102,也可以拼成210,最大的整数就是210,那么返回210,以字符串的形式。

2、这道题关键在于判断,判断vector中的两个数谁大谁小,谁应该放在前面。

举个例子,比如[3,30,31,32,33,34,35,102,9,990],大家觉得应该怎么排序?

我们要尽可能让大的数字放在前面,所以首位肯定要放个大一点的,那么就是9了,其余的都是3,放在首位不合适。

那么9有两个,要放9还是990,这里要对这两个数的组合做个判断。

一种是9990,一种是9909,所以还是9-990这种组合。

那么接下来呢,9-990之后呢?3跟30比,一种是330,一种是303,所以还是3在30前面。

那3跟31比呢,一种是331,一种是313,还是3在31前面。

是不是所有短的数字都要放在前面?

其实不是的,比如3和34,一种是334,一种是343,还要考虑到后面这一位的情况。

所以最终排列下来,“降序”排列,是[9,990,35,34,33,3,32,31,30]。

按照这个vector从前往后添加到要返回的字符串中,就可以了。

这道题的关键在于判断谁在前谁在后,比较的方法也很普通,就是补齐两个字符串,比较谁大谁小。

当然在实际操作中,没有必要真的对字符串补齐,我们同样可以操作。

代码如下:(附详解)

    static bool cmp(int &a1,int &b1)//自定义一个比较函数,大的放前面
    {
    	string a=to_string(a1),b=to_string(b1);//先把两个整数转化为字符串,操作起来比较方便
        int s1=a.size(),s2=b.size();
        if(s1<s2)//如果a短b长
        {
            for(int i=0;i<s1;i++)//在a的长度内比较
            {
                if(a[i]>b[i])//如果发现a中的某一位数值已经大于b中同一位的数值,比如4和39
                    return true;//那么比较到此结束,4要放在前面
                else if(a[i]<b[i])//如果发现a中的某一位数值已经小于b中同一位的数值,比如4和61
                    return false;//那么比较到此结束,61要放在前面
            }
            for(int i=s1;i<s2;i++)//如果上面的比较没出结果,比如4和456这种情况,那么开始新的比较,直到到达第二个字符串的最后一位
            {            //这个循环其实比较的是4和5,5和6,到达第二个字符串的最后一位就不比较了
                if(b[i-s1]>b[i])//如果满足条件,那么a要放在前面
                    return true;
                else if(b[i-s1]<b[i])//如果满足条件,那么b要放在前面
                    return false;
            }
            for(int i=0;i<s1;i++)//如果上面的比较没出结果,其实我们还有最后一位没有比较,6和4
            {
            	if(a[i]<b[s2-s1+i])
            		return true;
            	else if(a[i]>b[s2-s1+i])
            		return false;
			}
            return false;//如果上述比较都没出结果,比如3和333,那么返回false,这里随便拼都可以
        }
        else if(s1>s2)//如果a长b短,一样的比较方式
        {
            for(int i=0;i<s2;i++)
            {
                if(a[i]<b[i])
                    return false;
                else if(a[i]>b[i])
                    return true;
            }
            for(int i=s2;i<s1;i++)
            {
                if(a[i-s2]>a[i])
                    return false;
                else if(a[i-s2]<a[i])
                    return true;
            }
            for(int i=0;i<s2;i++)
            {
            	if(b[i]>a[s1-s2+i])
            		return true;
            	else if(b[i]<a[s1-s2+i])
            		return false;
			}
            return false;
        }
        else//如果两个一样长,那么直接逐位比较就可以了
        {
            for(int i=0;i<s1;i++)
            {
                if(a[i]>b[i])
                    return true;
                else if(a[i]<b[i])
                    return false;
            }
            return false;
        }
    }
    string largestNumber(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end(),cmp);//调用sort函数进行排序,排序准则是我们自定义的比较函数
        string res;
        for(auto i:nums)
            res+=to_string(i);//不断地插入到字符串的末尾
        if(res[0]=='0')return "0";//边界条件,如果第一位是0,那么说明后面即使有,也是全0,这时候我们只需要返回0就可以了了,而不是一长串的0
        return res;
    }

上述代码实测4ms,beats 99.85% of cpp submissions。

关于cmp函数,笔者在网上看到过一个简单的降序排列的版本,如下:

    bool cmp1(int &a,int &b)
    {
    	return a>b;
	}
    int main()
	{
		vector<int>nums={1,2,3,4,5,6,7,8,9,10,11,12};
		sort(nums.begin(),nums.end(),cmp1);
		for(int i:nums)
		cout<<i<<"  ";
		cout<<endl;
		return 0;
	} 

上面的cmp1这个函数,笔者个人猜想其实是说,如果a>b,那么返回true,认为前面的数大于后面的数是正确的。

所以在进行排序的时候,如果前面的数大于后面的,那么经过cmp1这个函数,返回true,认为正确,所以不用更改。

如果前面的数小于后面的数,那么经过cmp1这个函数,返回false,认为错误,所以要换一下位置。

所以笔者就根据自己的猜想,设计了题解代码中的cmp函数,从结果来看,上述认识还是有一定可取之处的。

但上述仅为笔者个人的猜想,有可能是不完全的甚至有些错误,没有仔细地去查sort函数的参数,仅作为一个个人的认识。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-367-Valid Perfect Square

    chenjx85
  • leetcode-504-Base 7

    chenjx85
  • leetcode-507-Perfect Number

    chenjx85
  • LWC 59:728. Self Dividing Numbers

    LWC 59:728. Self Dividing Numbers 传送门:728. Self Dividing Numbers Problem: A sel...

    用户1147447
  • 欧拉计划 Problem7

    题目: 第10001个素数 列出前6个素数,它们分别是2、3、5、7、11和13。我们可以看出,第6个素数是13。

    用户4492257
  • 算24

    解题思路: n个数算24,必有两个数要先算。这两个数算的结果,和剩余n-2个数,就构成了n-1个数求24的问题。枚举先算的两个数,以及这两个数的运算方式。n...

    AI那点小事
  • python基础学习1

      1. 字母数字下划线组成   2. 不能以数字开头,不能含有特殊字符和空格   3. 不能以保留字命名   4. 不能以中文命名   5. 定义的变量名应该...

    py3study
  • PHP验证身份证格式

    互联网公司对身份证验证的需求越来越多,然而普通的小公司是无法对接公安部门的身份认证系统的。几乎都是在网上买一些大的互联网公司的一些认证服务。即使是便宜一些的认证...

    叫我可儿呀
  • java递归算法入门小结(一)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

    用户2965908
  • BZOJ4373: 算术天才⑨与等差数列(线段树 hash?)

    第三条后面的可以直接推式子推出来(\(\sum_{i = 1}^n i^2 = \frac{n(n+1)(2n+1)}{6}\))

    attack

扫码关注云+社区

领取腾讯云代金券