注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex179 Largest Number  

2015-05-22 21:40:41|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.


数组内多个字符拼凑得到最大值。题目很容易理解,而且最先想到的肯定是排序,然后第一位大的数字肯定排在前面,接着就是比较后面的位置上的数字了。这一题最恶心的地方就是前面位置上的数字相同,后面不同的排序方式。例如 3 30 34,他的排序方式应该是 34 30 3,其实是不对的,比较的时候会出问题  34330>34303。后来写cmp函数的就是卡在这儿了。下面是我的解题思路
第一步  将数字转化为字符存在起来,构造一个struct类型 保存num和 num_str
第二步  快排序,里面需要自己写cmp函数
第三步 拼接字符串输出

第一步没什么好说的,不用考虑负数,题目都说了。第二步的cmp函数有点儿技巧,我是吃饭的时候想到的。比较的时候不是说的可能长度不一样么,那么我就把两种前后拼接的方式比较一下不就出来了!!另外需要考虑一下极限输入,比如全部是0的情况。

如下是c++代码

struct Node{
int num;
string str;
};

bool cmp(Node a,Node b)
{
//两个串拼接起来比较,这个时候就没有谁长谁短的问题了
string str1 = a.str+b.str;
string str2 = b.str+a.str;
int len1 = str1.size();
int len2 = str2.size();
int i;

int num1, num2;
for (i = 0; i < len1&&i < len2; i++)
{
num1 = str1[i] - '0';
num2 = str2[i] - '0';
if (num1 == num2)
{
continue;
}
return num1 > num2;
}
return num1 > num2;
}
class Solution {
public:
vector<Node> array;
string largestNumber(vector<int>& nums) {
string str;

preProcess(nums);
sort(array.begin(), array.end(),cmp);
int i, len = nums.size();
int index = 0;
while (index<len&&array[index].num == 0)
{
index++;
}
//考虑都是0的特殊情况
if (len!=0&&index == len)
{
str = "0";
return str;
}
for (i = index; i <len; i++)
{
str.append(array[i].str);
//cout << array[i].str << endl;
}
return str;
}
void preProcess(vector<int>nums)
{
int len = nums.size();
Node temp;
for (int i = 0; i < len; i++)
{
temp.num = nums[i];
temp.str = num2str(nums[i]);
array.push_back(temp);
}
}
string num2str(int num)
{
//这里的num是大于0的,所以不用考虑负号
string str;
int tmp;
while (num >= 10)
{
tmp = num % 10;
str.push_back(tmp+'0');
num /= 10;
}
str.push_back(num+'0');
reverse(str.begin(),str.end());
return str;
}
};


  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017