a**********2
发帖数: 340 | 1 Given an array of elements find the largest possible number that can
be formed by using the elements of the array.
eg: 10 9
ans: 910
2 3 5 78
ans: 78532
100 9
ans: 9100 | j*******r
发帖数: 52 | 2 1 def my_cmp(x,y):
2 if str(x)[0]>str(y)[0]:
3 return -1
4 elif str(x)[0]==str(y)[0]:
5 return 0
6 return 1
7
8 def BiggestNum(L):
9 L.sort(my_cmp)
10 print L
11 return reduce(lambda x,y: str(x)+str(y), L)
貌似比较数字最大位上的值就可以了？ | a**********2
发帖数: 340 | 3
how about 3,3,32?
【在 j*******r 的大作中提到】
: 1 def my_cmp(x,y):
: 2 if str(x)[0]>str(y)[0]:
: 3 return -1
: 4 elif str(x)[0]==str(y)[0]:
: 5 return 0
: 6 return 1
: 7
: 8 def BiggestNum(L):
: 9 L.sort(my_cmp)
: 10 print L
| g**********y
发帖数: 14569 | 4 按位bucket sort =>
1. 把所有数按从左数第k位分进9~0的bucket, 如果某数没有k位，直接用掉。
2. 从9～0的bucket, 依次call above function with k+1 | a**********2
发帖数: 340 | 5
不是太理解，这样的话，3，3，43的结果又是多少呢？能不能举个例子说说，谢谢
【在 g**********y 的大作中提到】
: 按位bucket sort =>
: 1. 把所有数按从左数第k位分进9~0的bucket, 如果某数没有k位，直接用掉。
: 2. 从9～0的bucket, 依次call above function with k+1
| g**********y
发帖数: 14569 | 6 3, 3, 43 =>
1. 分成{43}, {3, 3}
2. {43} 用掉
3. {3, 3}都没有下一位，用掉both
结果：4333
举个复杂点的例子：{9, 98, 987, 902, 399, 380}
1. 分成两个bucket {9, 98, 987, 902}, {399, 380}
2. 对第一个bucket, 9用掉；剩下分成两个bucket: {98, 987}, {902}
3. 对{98, 987}, 用掉98； 然后再call function, 用掉987
4. 对{902}, 用掉902
5. 对{399, 380}, 分成{399}, {380},
6. 用掉399,
7. 用掉380
结果：
9 98 987 902 399 380
【在 a**********2 的大作中提到】
:
: 不是太理解，这样的话，3，3，43的结果又是多少呢？能不能举个例子说说，谢谢
| a**********2
发帖数: 340 | 7
那么如果现在给3，3，34， 先干掉了3,3的话结果就不对了
【在 g**********y 的大作中提到】
: 3, 3, 43 =>
: 1. 分成{43}, {3, 3}
: 2. {43} 用掉
: 3. {3, 3}都没有下一位，用掉both
: 结果：4333
: 举个复杂点的例子：{9, 98, 987, 902, 399, 380}
: 1. 分成两个bucket {9, 98, 987, 902}, {399, 380}
: 2. 对第一个bucket, 9用掉；剩下分成两个bucket: {98, 987}, {902}
: 3. 对{98, 987}, 用掉98； 然后再call function, 用掉987
: 4. 对{902}, 用掉902
| j*******r
发帖数: 52 | 8 u r right, I didn't noticed it.
那就在等于判断时加一下吧，把长度较低的那个数按其个位上的数字扩张到另一个数的
长度，比如3和32就将3扩张为33，再进行比较。
假设x比y短，则：return cmp(str(x)+str(x)[-1]*(len(y)-len(x)), str(y))
hope it works :)
【在 a**********2 的大作中提到】
:
: 那么如果现在给3，3，34， 先干掉了3,3的话结果就不对了
| t*s
发帖数: 1504 | 9 900, 9001, 2
【在 g**********y 的大作中提到】
: 3, 3, 43 =>
: 1. 分成{43}, {3, 3}
: 2. {43} 用掉
: 3. {3, 3}都没有下一位，用掉both
: 结果：4333
: 举个复杂点的例子：{9, 98, 987, 902, 399, 380}
: 1. 分成两个bucket {9, 98, 987, 902}, {399, 380}
: 2. 对第一个bucket, 9用掉；剩下分成两个bucket: {98, 987}, {902}
: 3. 对{98, 987}, 用掉98； 然后再call function, 用掉987
: 4. 对{902}, 用掉902
| b*******y
发帖数: 232 | 10 先排序吧，排完序串起来
32 3 3的话
肯定就是 3 3 32排序
如果是 3 3 34的话，就是 34 3 3
如果是3 32 342 324 就是 342 3 324 32
也就是说，比较的时候，对最后一个数字重复延伸
【在 a**********2 的大作中提到】
: Given an array of elements find the largest possible number that can
: be formed by using the elements of the array.
: eg: 10 9
: ans: 910
: 2 3 5 78
: ans: 78532
: 100 9
: ans: 9100
| | | a**********2
发帖数: 340 | 11
貌似向前向后都不太对啊，举个反例
向后扩张，64，645 -> 644 < 645 按这个算法，应该是64564，但结果应该是64645
同样向钱扩张的话，46，447 -> 446 < 447 按这个算法，应该是44746，但结果应该是
46447吧
【在 j*******r 的大作中提到】
: u r right, I didn't noticed it.
: 那就在等于判断时加一下吧，把长度较低的那个数按其个位上的数字扩张到另一个数的
: 长度，比如3和32就将3扩张为33，再进行比较。
: 假设x比y短，则：return cmp(str(x)+str(x)[-1]*(len(y)-len(x)), str(y))
: hope it works :)
| g**********y
发帖数: 14569 | 12 简化一下code,
1. 对所有数按codingman的比较办法，看a+b, b+a谁大
2. 按次序输出
public String largest(String... numbers) {
StringBuilder builder = new StringBuilder();
ArrayList list = new ArrayList();
for (String number : numbers) list.add(number);
Collections.sort(list, new Comparator() {
public int compare(String a, String b) {
return (b+a).compareTo(a+b);
}
});
for (String s : list) builder.append(s);
return builder.toString();
} | c*******n
发帖数: 63 | 13 两个数 a=a1...am...an 和 b=b1...bm 假设比较的时候a的位数比b长或相等
c = a1...am...anb1...bm 比 d = b1...bma1...am...an大的条件是
there exists a k <= m s.t. ai >= bi for any i <= k
i.e.
for i=1 to m
if ai > bi
return a
else if bi > ai
return b
根据这个规则排序，使用quick sort，时间复杂度应该是 O(knlgn)吧，k是最大位长 | g**********y
发帖数: 14569 | 14 这个coding简单，面试时很好。
【在 c*******n 的大作中提到】
: 两个数 a=a1...am...an 和 b=b1...bm 假设比较的时候a的位数比b长或相等
: c = a1...am...anb1...bm 比 d = b1...bma1...am...an大的条件是
: there exists a k <= m s.t. ai >= bi for any i <= k
: i.e.
: for i=1 to m
: if ai > bi
: return a
: else if bi > ai
: return b
: 根据这个规则排序，使用quick sort，时间复杂度应该是 O(knlgn)吧，k是最大位长
| g**e
发帖数: 6127 | 15 应该是 else if bi >= ai 吧
【在 c*******n 的大作中提到】
: 两个数 a=a1...am...an 和 b=b1...bm 假设比较的时候a的位数比b长或相等
: c = a1...am...anb1...bm 比 d = b1...bma1...am...an大的条件是
: there exists a k <= m s.t. ai >= bi for any i <= k
: i.e.
: for i=1 to m
: if ai > bi
: return a
: else if bi > ai
: return b
: 根据这个规则排序，使用quick sort，时间复杂度应该是 O(knlgn)吧，k是最大位长
| c*******n
发帖数: 63 | 16
bi == ai的话，大小应该由下一个数字(i+1位)决定
【在 g**e 的大作中提到】
: 应该是 else if bi >= ai 吧
| g**e
发帖数: 6127 | 17 a=87
b=8
你上面的代码输出？
【在 c*******n 的大作中提到】
:
: bi == ai的话，大小应该由下一个数字(i+1位)决定
| y***m
发帖数: 7027 | 18 第一个字母排大小后【拼接？
【在 a**********2 的大作中提到】
: Given an array of elements find the largest possible number that can
: be formed by using the elements of the array.
: eg: 10 9
: ans: 910
: 2 3 5 78
: ans: 78532
: 100 9
: ans: 9100
| c*******n
发帖数: 63 | 19
哦
在循环结束后应该价格return b
因为b是位数短的那位，如果循环结束表示a的前m位和b相等，这个时候 ba比ab要大
【在 g**e 的大作中提到】
: a=87
: b=8
: 你上面的代码输出？
| g**********y
发帖数: 14569 | 20 直接String.compareTo就好了，除非他非要看。interview时写细的code容易错。
我写循环的边界条件(复杂一点的)，如果不用test code测，>50%的时候要写错。
【在 c*******n 的大作中提到】
:
: 哦
: 在循环结束后应该价格return b
: 因为b是位数短的那位，如果循环结束表示a的前m位和b相等，这个时候 ba比ab要大
| | | i**********e
发帖数: 1145 | 21 This is correct, although easier but converting to string might not be
efficient. codingman's solution is more efficient. This problem is a
variation from Facebook's Hackercup "Studious Student".
http://www.ihas1337code.com/2011/01/studious-student-problem-an
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g**********y 的大作中提到】
: 简化一下code,
: 1. 对所有数按codingman的比较办法，看a+b, b+a谁大
: 2. 按次序输出
: public String largest(String... numbers) {
: StringBuilder builder = new StringBuilder();
: ArrayList list = new ArrayList();
: for (String number : numbers) list.add(number);
: Collections.sort(list, new Comparator() {
: public int compare(String a, String b) {
: return (b+a).compareTo(a+b);
| b*******h
发帖数: 53 | 22 int compare(int a, int b)
{
String x= Integer.toString(a)
String y = Integer.toString(b);
if (Integer.parseInt(x+y)< Integer.parseInt(x+y))
return -1;
else if(Integer.parseInt(x+y)= Integer.parseInt(x+y))
return 0;
else return 1;
}
void Quick_Sort(int[] a, int p, int r)
{
if(p
{
int q = partition(a,p,r);
Quick_Sort(a,p,q-1);
Quick_Sort(a,q+1,r);
}
}
int Partition(int[] a, int p, int r)
{
int key = a[r];
int i = p-1;
int temp=0;
for(int j=p; j<=r; j++)
{
if(compare(a[j],key)<1)
{
i++;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
return i;
} | t******g
发帖数: 252 | 23 What if there are multiple a's and b's?
【在 b*******h 的大作中提到】
: int compare(int a, int b)
: {
: String x= Integer.toString(a)
: String y = Integer.toString(b);
: if (Integer.parseInt(x+y)< Integer.parseInt(x+y))
: return -1;
: else if(Integer.parseInt(x+y)= Integer.parseInt(x+y))
: return 0;
: else return 1;
: }
| b*******h
发帖数: 53 | 24 a=89
b=8
ab>ba
【在 c*******n 的大作中提到】
:
: 哦
: 在循环结束后应该价格return b
: 因为b是位数短的那位，如果循环结束表示a的前m位和b相等，这个时候 ba比ab要大
| b*******h
发帖数: 53 | 25 if there is 89 and 878
compute 89878 and 87889 which is larger, here 89878 is larger, 878 is less
than 89
here. the quick sort will sort 878 in the front and then 89.
Sorry, the compare should be
int compare(int a, int b)
}
change x+y to y+x. | c*******n
发帖数: 63 | 26 you're right!
we should keep comparing the following digits
a1 ... am a[m+1]...a[n] b1 ... bm
b1 ... bm a1...a[n-m+1] ... an
compare a[m+1] ... a[n] and a[1] ... a[n-m+1]
don't need to compare a's and b's because we already know them are
equal | t******g
发帖数: 252 | 27 {34, 34, 342}
【在 c*******n 的大作中提到】
: you're right!
: we should keep comparing the following digits
: a1 ... am a[m+1]...a[n] b1 ... bm
: b1 ... bm a1...a[n-m+1] ... an
: compare a[m+1] ... a[n] and a[1] ... a[n-m+1]
: don't need to compare a's and b's because we already know them are
: equal
| g***s
发帖数: 3811 | 28 it would be quicker if using a trie. | g**e
发帖数: 6127 | 29 一语惊醒梦中人 赞
【在 g***s 的大作中提到】
: it would be quicker if using a trie.
| b*******h
发帖数: 53 | 30 QuickSort will sort it： 342,34,34. read reversely, result is 3434342
【在 t******g 的大作中提到】
: {34, 34, 342}
| | | g**********y
发帖数: 14569 | 31 Trie怎么决定35435, 354哪个在前？
【在 g***s 的大作中提到】
: it would be quicker if using a trie.
| h*********n
发帖数: 11319 | 32 好吧，我想了两个方案都被你这个例子打败了
【在 g**********y 的大作中提到】
: Trie怎么决定35435, 354哪个在前？
| p*****a
发帖数: 147 | 33 这个好像是对的。
【在 b*******h 的大作中提到】
: int compare(int a, int b)
: {
: String x= Integer.toString(a)
: String y = Integer.toString(b);
: if (Integer.parseInt(x+y)< Integer.parseInt(x+y))
: return -1;
: else if(Integer.parseInt(x+y)= Integer.parseInt(x+y))
: return 0;
: else return 1;
: }
| s*****y
发帖数: 897 | 34 写了一个基于tree的，插入的原则是
1.比较最高位的digit，大的插入右边，小于或者等于的插入左边
2.如果最高位相等，比较combine 2个数的结果，哪个大决定插入左边或者右边
所有node都插入到树的最低层。
建完tree后，traverse tree按照right, current left的顺序，测了一下案例，似乎是
对的，
//int A[] = {2, 3, 5, 78 }; //pass
//int A[] = {2, 3, 89, 897 }; //pass
// int A[] = {3,3,43}; //pass
int A[] = {9, 98, 987, 902, 399, 380}; //pass
//int A[] = {900, 9001, 2}; //pass
// int A[] = {2, 3, 89,94, 899 }; //pass
// int A[] = {2, 3, 89, 897 }; //pass
// int A[] = {2, 3, 5, 35435, 354 }; //pass
code 如下，比较乱，有冗余代码。
#include "stdafx.h"
#include
#include
#include | g***s
发帖数: 3811 | 35 all extend to the max length of the numbers * 2
354 35435 3 123 23
k = max length = 5;
=>
354(3543543)
35435(35435)
333333(3333)
123123(1231)
232323(2323)
(it can be done when we build the trie)
O(kn)
【在 g**********y 的大作中提到】
: Trie怎么决定35435, 354哪个在前？
| a**m
发帖数: 151 | 36 就是把两个数接起来比较大小
c array: a+b;
d array: b+a;
compare(a, b, m, n)
{
c = a;
d = b;
offsetc = offsetd = 0;
for (i=0; i< m+n; i++)
{
if (i>=m) {
c = b;
offsetc = m;
}
if (i>=n) {
d = a;
offsetd = n;
}
if (c[i-offsetc]>d[i-offsetd]) return 1;
if (c[i-offsetc]
}
return 0;
} | d*******r
发帖数: 208 | 37 用sort的方法有两个缺点
1. tie break
2. overflow
how about use raw permutation ?
code:
void findMax(const std::vector& prefix, const std::vector& exist,
int& max) {
if (exist.empty()) {
int cur = getNum(prefix);
if (cur > max) {
max = cur;
}
} else {
for (std::vector::const_iterator i=exist.begin(); i!=exist.end(
); ++i) {
std::vector new_pre = prefix;
new_pre.push_back(*i);
std::vector new_ex(exist.begin(), i);
new_ex.insert(new_ex.end(),i+1, exist.end());
findMax(new_pre, new_ex, max);
}
}
}
【在 a**********2 的大作中提到】
: Given an array of elements find the largest possible number that can
: be formed by using the elements of the array.
: eg: 10 9
: ans: 910
: 2 3 5 78
: ans: 78532
: 100 9
: ans: 9100
| s*********0
发帖数: 89 | 38 这个方法很赞。
We still need to show this comparison method is equavlent to the previous
comparison method. This can be proved by discussing all possible cases.
Anyone has a easier way to prove?
【在 g***s 的大作中提到】
: all extend to the max length of the numbers * 2
: 354 35435 3 123 23
: k = max length = 5;
: =>
: 354(3543543)
: 35435(35435)
: 333333(3333)
: 123123(1231)
: 232323(2323)
: (it can be done when we build the trie)
| s*********0
发帖数: 89 | 39 Still need to prove two things:
1. This partial order can actually define a total order. That is, we need to
show a>b && b>c ==> a>c. The proof is not trivial to me. Anyone has a
simple proof?
2. After the sorting and concatnating them, we indeed find the solution.
This can be proved by induction.
My $0.02
【在 b*******h 的大作中提到】
: int compare(int a, int b)
: {
: String x= Integer.toString(a)
: String y = Integer.toString(b);
: if (Integer.parseInt(x+y)< Integer.parseInt(x+y))
: return -1;
: else if(Integer.parseInt(x+y)= Integer.parseInt(x+y))
: return 0;
: else return 1;
: }
| d*******d
发帖数: 2050 | | | | d*******d
发帖数: 2050 | 41 didn't see the code you guys posted, maybe you guys already covered my
method.
bool compare_string(const string & str1, const string & str2){
int length1 = str1.length();
int length2 = str2.length();
int max = length1 > length2 ? length1 : length2;
int i1 = 0, i2 = 0;
int i=0;
while(i
if( str1[i1] > str2[i2] )
return true;
else if( str1[i1] < str2[i2])
return false;
else{
i1++;
if( i1>=length1){
i1 = i1 - length1;
}
i2++;
if( i2 >=length2){
i2 = i2 - length2;
}
i++;
}
}
}
int main(int argc, char ** argv){
ifstream fin(argv[1]);
int n = 0;
string a[10];
while( fin >> a[n] ){
n++;
}
sort(a, a+n, compare_string);
for(int i =0; i
cout << a[i];
}
cout << endl;
}
【在 a**********2 的大作中提到】
: Given an array of elements find the largest possible number that can
: be formed by using the elements of the array.
: eg: 10 9
: ans: 910
: 2 3 5 78
: ans: 78532
: 100 9
: ans: 9100
| g***s
发帖数: 3811 | 42 这个不对。
34534 345的判断
或者
34234 345肯定有一个是错的
把你的max=2×Math.max(lenght1，lenght2)，就和我的是一个思想了。 加速的方法可
以用
trie，但复杂不少。
【在 d*******d 的大作中提到】
: didn't see the code you guys posted, maybe you guys already covered my
: method.
: bool compare_string(const string & str1, const string & str2){
: int length1 = str1.length();
: int length2 = str2.length();
: int max = length1 > length2 ? length1 : length2;
: int i1 = 0, i2 = 0;
: int i=0;
: while(i: if( str1[i1] > str2[i2] )
| y*******g
发帖数: 6599 | 43 不过怎么想到去X2呢？ 有什么原型是做这个的？
【在 g***s 的大作中提到】
: 这个不对。
: 34534 345的判断
: 或者
: 34234 345肯定有一个是错的
: 把你的max=2×Math.max(lenght1，lenght2)，就和我的是一个思想了。 加速的方法可
: 以用
: trie，但复杂不少。
| d*******d
发帖数: 2050 | | d*******d
发帖数: 2050 | 45 我又验证了一遍,你这两个我都对阿.
【在 g***s 的大作中提到】
: 这个不对。
: 34534 345的判断
: 或者
: 34234 345肯定有一个是错的
: 把你的max=2×Math.max(lenght1，lenght2)，就和我的是一个思想了。 加速的方法可
: 以用
: trie，但复杂不少。
| g***s
发帖数: 3811 | 46 敲错了，你再试试：
34234 342或者
34534 345
while外的return是啥？这两个都会跳出循环。本来应该一个return true，一个return
false。
【在 d*******d 的大作中提到】
: 我又验证了一遍,你这两个我都对阿.
| d*******d
发帖数: 2050 | 47 还真是.
现在搞明白了,确实max x2就对了.
while后面return true就可以了,其实如果出了while还没结果,return什么都没关系.
不过这个用trie加速也太不值了. | r****r
发帖数: 37 | 48 一个动态规划的解法：
DP[i] = 可以组成的i位数中最大的数
DP[0] = 0
DP[i] = max{ DP[i-1] + max(1), DP[i-2] + max(2), ... , DP[i-n] + max(n) }
其中max(k) 表示*剩余的*k位数中最大的数 | s*****y
发帖数: 897 | 49 could you give some example. Do not quite understand.
【在 r****r 的大作中提到】
: 一个动态规划的解法：
: DP[i] = 可以组成的i位数中最大的数
: DP[0] = 0
: DP[i] = max{ DP[i-1] + max(1), DP[i-2] + max(2), ... , DP[i-n] + max(n) }
: 其中max(k) 表示*剩余的*k位数中最大的数
| s*******d
发帖数: 4135 | 50 扔一块砖
/*
Given an array of elements find the largest possible number that can
be formed by using the elements of the array.
eg: 10 9
ans: 910
2 3 5 78
ans: 78532
100 9
ans: 9100
*/
#include
#include
#include
#include
using namespace std;
bool compare(int a, int b)
{
stringstream ss;
ss << a;
string as = ss.str();
ss << b;
string bs = ss.str();
int i = 0;
int as_len = as.length();
int bs_len = bs.length();
while (i < as_len && i < bs_len)
{
if (as[i]>bs[i]) return false;
else if (as[i]
i++;
}
if (as_len < bs_len) return false;
else return true;
}
int main(int argc, char const *argv[])
{
vector v;
v.push_back(9);
v.push_back(98);
v.push_back(987);
v.push_back(902);
v.push_back(399);
v.push_back(380);
sort(v.begin(),v.end(),compare);
copy(v.begin(),v.end(),ostream_iterator(cout,""));
cout << endl;
return 0;
} | | | s*****y
发帖数: 897 | 51 v.push_back(4);
v.push_back(98);
v.push_back(982);
v.push_back(902);
v.push_back(399);
v.push_back(380);
output: 498982902399380 ---wrong in the first digit
v.push_back(4);
v.push_back(98);
v.push_back(982);
v.push_back(987);
v.push_back(399);
v.push_back(380);
output: 498982987399380 ----wrong. how come 982 before 987?
【在 s*******d 的大作中提到】
: 扔一块砖
: /*
: Given an array of elements find the largest possible number that can
: be formed by using the elements of the array.
: eg: 10 9
: ans: 910
: 2 3 5 78
: ans: 78532
: 100 9
: ans: 9100
| s*******d
发帖数: 4135 | 52 多谢指出错误。。。还是要多检查啊。
/*
Given an array of elements find the largest possible number that can
be formed by using the elements of the array.
eg: 10 9
ans: 910
2 3 5 78
ans: 78532
100 9
ans: 9100
*/
#include
#include
#include
#include
using namespace std;
bool compare(int a, int b)
{
stringstream ss,ss1;
ss << a;
string as = ss.str();
ss1 << b;
string bs = ss1.str();
int i = 0;
int as_len = as.length();
int bs_len = bs.length();
while (i < as_len && i < bs_len)
{
if (as[i]>bs[i]) return true;
else if (as[i]
i++;
}
if (as_len < bs_len) return true;
else return false;
}
int main(int argc, char const *argv[])
{
vector v;
v.push_back(4);
v.push_back(98);
v.push_back(982);
v.push_back(987);
v.push_back(399);
v.push_back(380);
sort(v.begin(),v.end(),compare);
copy(v.begin(),v.end(),ostream_iterator(cout,""));
cout << endl;
return 0;
} | k****n
发帖数: 369 | 53 wrong
499, 414, 4 => 4499414
【在 s*******d 的大作中提到】
: 多谢指出错误。。。还是要多检查啊。
: /*
: Given an array of elements find the largest possible number that can
: be formed by using the elements of the array.
: eg: 10 9
: ans: 910
: 2 3 5 78
: ans: 78532
: 100 9
: ans: 9100
| s*******d
发帖数: 4135 | |
|
