Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
solve.c
solve.cpp

README.md

Largest Number

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.

Solution

首先想到这其实就是一道排序题,当不是简单的数值排序,而是实现字典排序。

当数字长度一样时,显然直接字典排序即可。关键在于当长度不一样时,如何排?

12 121, 显然12121 > 12112, 因此12排在121前面,12 123,显然12312 > 12123,因此123排在12前面.

因此简单认为短的排在前面还是后面都是错误的

当短的字符结束还没有得到结果,显然短的字符串一定是长字符串的前缀,当短的字符结束时,短的重新回到起始位置,继续比较。

但当其中一个字符串是另一个字符串的重复字串时会出现死循环,比如12 1212,因此需要特殊处理.

另外需要注意全是0的情况,此时应该输出0,而不是0000.

Code

bool isDup(char *s1, char *s2)
{
	if (s1 == NULL)
		return s2 == NULL;
	int len1 = strlen(s1), len2 = strlen(s2);
	if (len1 == 0 || len2 == 0)
		return false;
	char *p1, *p2;
	if (len1 >= len2) {
		if (len1 % len2 != 0)
			return false;
		p1 = s1;
		p2 = s2;
	} else {
		if (len2 % len1 != 0)
			return false;
		p1 = s2;
		p2 = s1;
	}
	while (*p1) {
		if (*p1 != *p2)
			return false;
		*p1++, *p2++;
		if (*p2 == 0) {
			if (len1 >= len2)
				p2 = s2;
			else
				p2 = s1;
		}
	}
	return true;
}
int cmp(const void *a, const void *b)
{
	char s1[20], s2[20];
	sprintf(s1, "%d", *(int *)a);
	sprintf(s2, "%d", *(int *)b);
	if (isDup(s1, s2))
		return 0;
	char *p1 = s1, *p2 = s2;
	while (*p1 && p2) {
		if (*p1 != *p2)
			return *p2 - *p1;
		p1++, p2++;
		if (*p1 == 0)
			p1 = s1;
		if (*p2 == 0)
			p2 = s2;
	}
	return 0;
}
char *largestNumber(int *num, int n)
{
	char *result = malloc(sizeof(char) * N);
	memset(result, 0, sizeof(char) * N);
	qsort(num, n, sizeof(num[0]), cmp);
	if (num[0] == 0) {
		strcpy(result, "0\0");
		return result;
	}
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		sum += sprintf(result + sum, "%d", num[i]);
	}
	return result;
}

Solution 2

上面的方法,关键都在处理长度不一样时的情况,先判断是否重复字串,然后循环比较字符。代码有点复杂。

其实我们只需要判断两个字符串组合时谁先谁大。设s1,s2, 其实我们只需要比较 s1 + s2 s2 + s1即可。

Code

class Solution {
	public:
		static bool cmp(const string &s1, const string &s2) {
			return s1 + s2 > s2 + s1;
		}
		string largestNumber(vector<int> &num) {
			vector<string> v;
			for_each(num.begin(), num.end(), [&](int i){v.push_back(to_string(i));});
			sort(v.begin(), v.end(), cmp);
			string result;
			for_each(v.begin(), v.end(), [&](string s){result += s;});
			if (result[0] == '0')
				return "0";
			return result;
		}

};

上面代码使用了函数式编程方法,并使用了c++11的lambda表达式,语法为

[ capture ] ( params ) mutable exception attribute -> ret { body }
其中capture为空、= 、 &,分别表示不捕获外部变量、传值、传引用。
You can’t perform that action at this time.