力扣Leetcode 179. 最大数 EOJ 和你在一起 字符串拼接 组成最大数

最大数

力扣

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

示例 1:

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

示例 2:

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

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

eoj 18年复试机试真题

单点时限: 1.0 sec

内存限制: 256 MB

我想和你在一起

直到我不爱你

宝贝 人和人 一场游戏

我愿意为你死去

如果我还爱你

宝贝 反正活着 也没意义

宝贝 我也只能 这样为你

——*《和你在一起》

力扣Leetcode 179. 最大数 EOJ 和你在一起 字符串拼接 组成最大数

现场4分10秒,小哥跟着逼哥嘶吼,泪流满面。我要和你在一起,直到我不爱你。有这么 n 个数字,联成一排拼到一起便是我爱你的时间,那么我们会在一起多久呢

例如: n=3 时,3 个整数 13,312,343 联接成的最长时间为: 34331213。

又如: n=4 时,4 个整数 7,13,4,246 联接成的最长时间为: 7424613。

输入格式

n (1≤n≤20),表示 n 个数。

接下来一行 n 个正整数,大小不超过 104。

输出格式

拼成的最长时间。

样例

input

3
623 583 413

output

623583413

解题思路

两题一个意思 只不过力扣不需要输入

用 stl 巧解 用字符串拼接来比较 其实难的在数学证明 这里且先记下这种由小范围推到全局(有点类似贪心这意思)

/* 力扣 leetcode */
bool cmp(string a, string b)//直接相加比较
{
return a+b > b+a; // 范围二者拼接较大的那个
} class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string> v;
for (int i = 0; i < nums.size(); i++)
{
string temp = to_string(nums[i]); // 将输入的int转为string
v.push_back(temp); // 推进vector中
}
sort(v.begin(), v.end(), cmp); // 关键排序
string ret; // 答案集
for (int i = 0; i < v.size(); i++)
{
ret += v[i]; // 直接按序拼接即可 数学理论暂不证明
if (v[0] == "0") // 经过上面的cmp 如若第一位为 0 后面也不用算了 最大就是0了
break;
}
return ret;
}
}; /* 需要输入的oj */
#include <bits/stdc++.h>
using namespace std;
bool cmp(string a, string b)
{
return a+b > b+a;
}
int main()
{
int n; cin >> n;
vector<int> nums;
vector<string> v;
for (int i = 0; i < n; i++)
{
int tmp; cin >> tmp;
nums.push_back(tmp);
} for (int i = 0; i < nums.size(); i++)
{
string temp = to_string(nums[i]);
v.push_back(temp);
}
sort(v.begin(), v.end(), cmp);
string ret;
for (int i = 0; i < v.size(); i++)
{
ret += v[i];
if (v[0] == "0")
break;
}
cout << ret;
return 0;
}
上一篇:springcloud入门系列(二):注册中心Eureka


下一篇:对抗样本攻防战,清华大学TSAIL团队再获CAAD攻防赛第一