【问题】阿里在线笔试题，好难啊！

编程说明也发出来吧。。里面信息挺多的

怎么感觉是动态规划 【 在 ABs (意涵团 | 求Offer) 的大作中提到: 】 : 各位大神，来看看吧，我已经被虐晕倒在电脑前[ema1] : [upload=1][/upload] : --

我有一个想法： 1 首先，对于这个环，我们选择的起点如果恰好是某个字符串的起点，那么得到的就是n个串的某种顺序的大整数。 2 对于一个字符串和它的逆，选择较大的一个，那么所有被选择的n个串按照大小顺序逐个连接，得到的大整数就是起点恰为字符串起点时的最大整数。 3 接下来，如果起点从某个字符串中间开始，那么最优时剩余的串就是按照上面的规则顺次连接的。 4 所以现在我们只要选一个最优的截断点。初始时，最优起点是第2步中的第一个串的第一个字符，对所有n个被选择的串，查看是否从某个位置开始它的字典序不小于目前的最优起点，如果小于，看下一个串，等于看下一位，大于就更新最优起点。 5 最后把最优起点串拿出来，剩余串按照前面的规则连接，最后再补上最优起点串前面截断的部分，就能得到最大整数。 不知道有没有漏洞。 【 在 ABs 的大作中提到: 】 : 各位大神，来看看吧，我已经被虐晕倒在电脑前[ema1] : [upload=1][/upload] : 发自「贵邮」

【 在 ABs 的大作中提到: 】 : 各位大神，来看看吧，我已经被虐晕倒在电脑前 : [upload=1][/upload] 阿里的题目感觉有些简单，有些很难，要看自己运气。。。。。

我的想法是这样的，其实可以分成四个步骤： （1）寻找起始串（这个串从其中某个部分出发到最右侧字典序最大，或者从某个部分出发到最左侧字典序最大），如果两个串的部分最大字典序一样，则比较剩余部分的谁大（相当于就是最大整数串的末尾几个数）； （2）寻找其他各个串的正向/逆向最大字典序的形式（即这个串要么是正向的，要么是逆向的）； （3）对其他串进行排序 （4）将起始串和寻找到的其他各个串的最大字典序形式concat一下，然后从之前起始串中选出的起始位置出发，就是最大整数串。 （1）和（2）可以一起做，（1）可以用int来记录起始串的index以及起始点以及顺序（正或者逆），（2）可以用一个bool数组来存储到底是正序还是逆序，（3）需要根据其他串的字典序进行排序，最后就直接把起始串和排好序的其他串连接，并从起始点出发，就可以了。 时间复杂度O（nlogn+nm）

https://leetcode.com/problems/largest-number/#/description，我没理解错的话就是原题，这个无非再加上单个数再比一下正序逆序的大小

很不一样啊。 比如说 [123,494,878]三个数，按照那道题解法会得到878494321，再选最大值会得到943218784.但是实际上的答案应该是948783214. 【 在 mzcwudi 的大作中提到: 】 : https://leetcode.com/problems/largest-number/#/description，我没理解错的话就是原题，这个无非再加上单个数再比一下正序逆序的大小

我的想法是这样的。 0. 选出一个旋转后截断最大字典序的数，这个数就是最终序列的第一个数。比如[123,494,878]旋转后截断最大数分别是321,94，878。所以选择494作为第一个数。 1. 对剩下字符串进行排序。按字典序排，每个数都选择自己最大的形态，比如123就翻转为321,878还是878.按照字典序排列。然后得到的结果就是 494,878,321. 2. 然后选择第一个字符串的最大截断后的顺序，比如494可以是494，也可以是94，也可是4. 3. 排序完之后最大的字典序就出来了。就是948783214. 我感觉这个算法好像还有点问题。比如选878作为第一个数的时候，是选878最为第一个的顺序还是选择8作为第一个顺序而把剩下的87放到末尾。这个情况貌似不能很干净的覆盖到...

leecode 179 的一种解法：(C++代码),显然不能用在阿里这个题目上： https://leetcode.com/problems/largest-number/#/description string largestNumber(vector<int>& nums) { struct bignum_cmp { bool operator ()(const string & x, const string & y) const { return (x + y) > (y + x); } }; // vector<string> snum; for (auto& v : nums) { snum.push_back(std::to_string(v)); } sort(snum.begin(), snum.end(), bignum_cmp()); // string strnum = ""; for (auto & s : snum) { strnum += s; } unsigned int i; for (i = 0; i < strnum.length(); i++) { if (strnum[i] != '0') break; } if (i >= strnum.length()) strnum = "0"; return strnum; }