x220, win8.1 升级 win10 很顺畅 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Hardware - 计算机硬件

x220, win8.1 升级 win10 很顺畅

x220, win8.1 升级 win10 很顺畅# Hardware - 计算机硬件

a*22015-08-11 07:08

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

a*g2015-08-11 07:08

2 楼

线段MN with endpoints M(6, 10) and N(1, 0)
is rotated 30° about the origin. What are
the coordinates of N after the rotation?
1. ( sqrt3/2, 1/2)
2.(12/, sqrt 3/2)
请教该如何做此题？谢谢。

V*r2015-08-11 07:08

3 楼

系统没有感到明显的变慢
原有的驱动都有效
就不折腾重装了

j*r2015-08-11 07:08

4 楼

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)
貌似比较数字最大位上的值就可以了？

p*s2015-08-11 07:08

5 楼

a*22015-08-11 07:08

6 楼

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

X*r2015-08-11 07:08

7 楼

这个不是几何题，就是代数题啊。
x' = x*cos(a) - y*sin(a)
y' = x*sin(a) + y*cos(a)
代入
x = 1
y = 0
a = 30 deg
得
x' = sqrt(3)/2
y' = 1/2

【在 a*****g 的大作中提到】

: 线段MN with endpoints M(6, 10) and N(1, 0)
: is rotated 30° about the origin. What are
: the coordinates of N after the rotation?
: 1. ( sqrt3/2, 1/2)
: 2.(12/, sqrt 3/2)
: 请教该如何做此题？谢谢。

g*y2015-08-11 07:08

8 楼

按位bucket sort =>
1. 把所有数按从左数第k位分进9~0的bucket, 如果某数没有k位，直接用掉。
2. 从9～0的bucket, 依次call above function with k+1

a*g2015-08-11 07:08

9 楼

先谢我再仔细想想。有什么几何方面的解释吗？

【在 X****r 的大作中提到】

: 这个不是几何题，就是代数题啊。
: x' = x*cos(a) - y*sin(a)
: y' = x*sin(a) + y*cos(a)
: 代入
: x = 1
: y = 0
: a = 30 deg
: 得
: x' = sqrt(3)/2
: y' = 1/2

a*22015-08-11 07:08

10 楼

不是太理解，这样的话，3，3，43的结果又是多少呢？能不能举个例子说说，谢谢

【在 g**********y 的大作中提到】

: 按位bucket sort =>
: 1. 把所有数按从左数第k位分进9~0的bucket, 如果某数没有k位，直接用掉。
: 2. 从9～0的bucket, 依次call above function with k+1

n*22015-08-11 07:08

11 楼

哈哈，我完全都忘记这些题了，估计以后教娃前，要先自己再学一遍

【在 X****r 的大作中提到】

: 这个不是几何题，就是代数题啊。
: x' = x*cos(a) - y*sin(a)
: y' = x*sin(a) + y*cos(a)
: 代入
: x = 1
: y = 0
: a = 30 deg
: 得
: x' = sqrt(3)/2
: y' = 1/2

g*y2015-08-11 07:08

12 楼

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*g2015-08-11 07:08

13 楼

我算出来了，真笨啊。

【在 a*****g 的大作中提到】

: 先谢我再仔细想想。有什么几何方面的解释吗？

a*22015-08-11 07:08

14 楼

那么如果现在给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

c*62015-08-11 07:08

15 楼

没这么复杂，其实就是算cos30和sin30

【在 X****r 的大作中提到】

: 这个不是几何题，就是代数题啊。
: x' = x*cos(a) - y*sin(a)
: y' = x*sin(a) + y*cos(a)
: 代入
: x = 1
: y = 0
: a = 30 deg
: 得
: x' = sqrt(3)/2
: y' = 1/2

j*r2015-08-11 07:08

16 楼

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的话结果就不对了

M*A2015-08-11 07:08

17 楼

这不就是解析几何么
解析几何其实就是代数

t*s2015-08-11 07:08

18 楼

900, 9001, 2

【在 g**********y 的大作中提到】

i*e2015-08-11 07:08

19 楼

我英文太差啊
这个origin是指坐标原点？
这个旋转30度，是指顺时针还是逆时针？

【在 a*****g 的大作中提到】

b*y2015-08-11 07:08

20 楼

先排序吧，排完序串起来
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

c*62015-08-11 07:08

21 楼

是的。是逆时针转动（至少答案是这样说的）

【在 i**e 的大作中提到】

: 我英文太差啊
: 这个origin是指坐标原点？
: 这个旋转30度，是指顺时针还是逆时针？

a*22015-08-11 07:08

22 楼

貌似向前向后都不太对啊，举个反例
向后扩张，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 :)

M*A2015-08-11 07:08

23 楼

其实M点坐标没啥用，就是N点以圆点为中心逆时针转了30度。从坐标(1,0)可以得知ON
长度为1。角N'ON为30度，三角形长边ON'长度为1，新坐标(x',y')中的x'就是1*cos30=
(sqrt3)/2，y'就是1*sin30=1/2
是不是啊~好几十年都记不太清了~

g*y2015-08-11 07:08

24 楼

简化一下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*n2015-08-11 07:08

25 楼

两个数 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*y2015-08-11 07:08

26 楼

这个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*e2015-08-11 07:08

27 楼

应该是 else if bi >= ai 吧

【在 c*******n 的大作中提到】

c*n2015-08-11 07:08

28 楼

bi == ai的话，大小应该由下一个数字(i+1位)决定

【在 g**e 的大作中提到】

: 应该是 else if bi >= ai 吧

g*e2015-08-11 07:08

29 楼

a=87
b=8
你上面的代码输出？

【在 c*******n 的大作中提到】

:
: bi == ai的话，大小应该由下一个数字(i+1位)决定

y*m2015-08-11 07:08

30 楼

第一个字母排大小后【拼接？

【在 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*n2015-08-11 07:08

31 楼

哦
在循环结束后应该价格return b
因为b是位数短的那位，如果循环结束表示a的前m位和b相等，这个时候 ba比ab要大

【在 g**e 的大作中提到】

: a=87
: b=8
: 你上面的代码输出？

g*y2015-08-11 07:08

32 楼

直接String.compareTo就好了，除非他非要看。interview时写细的code容易错。
我写循环的边界条件(复杂一点的)，如果不用test code测，>50%的时候要写错。

【在 c*******n 的大作中提到】

:
: 哦
: 在循环结束后应该价格return b
: 因为b是位数短的那位，如果循环结束表示a的前m位和b相等，这个时候 ba比ab要大

i*e2015-08-11 07:08

33 楼

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*h2015-08-11 07:08

34 楼

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*g2015-08-11 07:08

35 楼

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*h2015-08-11 07:08

36 楼

a=89
b=8
ab>ba

【在 c*******n 的大作中提到】

:
: 哦
: 在循环结束后应该价格return b
: 因为b是位数短的那位，如果循环结束表示a的前m位和b相等，这个时候 ba比ab要大

b*h2015-08-11 07:08

37 楼

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*n2015-08-11 07:08

38 楼

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*g2015-08-11 07:08

39 楼

{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*s2015-08-11 07:08

40 楼

it would be quicker if using a trie.

g*e2015-08-11 07:08

41 楼

一语惊醒梦中人赞

【在 g***s 的大作中提到】

: it would be quicker if using a trie.

b*h2015-08-11 07:08

42 楼

QuickSort will sort it： 342,34,34. read reversely, result is 3434342

【在 t******g 的大作中提到】

: {34, 34, 342}

g*y2015-08-11 07:08

43 楼

Trie怎么决定35435, 354哪个在前？

【在 g***s 的大作中提到】

: it would be quicker if using a trie.

h*n2015-08-11 07:08

44 楼

好吧，我想了两个方案都被你这个例子打败了

【在 g**********y 的大作中提到】

: Trie怎么决定35435, 354哪个在前？

p*a2015-08-11 07:08

45 楼

这个好像是对的。

【在 b*******h 的大作中提到】

s*y2015-08-11 07:08

46 楼

写了一个基于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
#include
#include
#include
using namespace std;
class Node_t {
public:
Node_t(int data): left(NULL), right(NULL) {
length = 0;
while (data > 0) {
digits.push_back(data%10);
length ++;
data /= 10;
}
}
int length;
vector digits;
Node_t *left, *right;
};
inline int min(int a, int b) {
return a < b? a: b;
}
int combine(Node_t *first, Node_t *second)
{
vector rtn;
vector::iterator it = rtn.end();
rtn.insert(it, first->digits.rbegin(), first->digits.rend());
it = rtn.end();
rtn.insert(it, second->digits.rbegin(), second->digits.rend());
/*convert vector to number*/
int num = 0;
for (int i = 0; i < rtn.size(); i++) {
num = num*10 + rtn[i];
}
return num;
}
void Insert(Node_t *root, Node_t *newnode)
{
Node_t *tmp = root;
while (root->left || root->right) {
if (root->digits[root->length -1] > newnode->digits[newnode->length
-1]) {
if (root->left) root = root->left;
else {root->left = newnode; return;}
} else if (root->digits[root->length -1] < newnode->digits[newnode->
length -1]) {
if (root->right) root = root->right;
else {root->right = newnode; return;}
} else { /* equal at the highest bits, compare next bit*/
int option1 = combine(root, newnode);
int option2 = combine(newnode, root);
if (option1 >= option2) {
if (root->left) root = root->left;
else {root->left = newnode; return;}
} else {
if (root->right) root = root->right;
else {root->right = newnode; return;}
}
}
}
if (root->digits[root->length -1] > newnode->digits[newnode->length -1])
root->left = newnode;
else if (root->digits[root->length -1] < newnode->digits[newnode->length
-1]) {
root->right = newnode;
} else {
int option1 = combine(root, newnode);
int option2 = combine(newnode, root);
if (option1 < option2) {
root->right = newnode;
} else {
root->left = newnode;
}
}
}
void Traverse_Tree(Node_t* root, vector &num) {
if (root->right != NULL)
Traverse_Tree(root->right, num);
vector::iterator it = num.end();
num.insert(it, root->digits.rbegin(), root->digits.rend());
if (root->left != NULL)
Traverse_Tree(root->left, num);
}
int main() {
//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
Node_t *root = new Node_t(A[0]);
for (int i = 1; i < sizeof(A)/sizeof(int); i++) {
Node_t *newnode = new Node_t(A[i]);
Insert(root, newnode);
}
vector num;
Traverse_Tree(root,num);
return 0;
}

g*s2015-08-11 07:08

47 楼

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*m2015-08-11 07:08

48 楼

就是把两个数接起来比较大小
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*r2015-08-11 07:08

49 楼

用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*02015-08-11 07:08

50 楼

这个方法很赞。
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*02015-08-11 07:08

51 楼

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 的大作中提到】

d*d2015-08-11 07:08

52 楼

这题真没那么复杂，等会有空了我来贴code

d*d2015-08-11 07:08

53 楼

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(iif( 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; icout << 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*s2015-08-11 07:08

54 楼

这个不对。
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*g2015-08-11 07:08

55 楼

不过怎么想到去X2呢？有什么原型是做这个的？

【在 g***s 的大作中提到】

: 这个不对。
: 34534 345的判断
: 或者
: 34234 345肯定有一个是错的
: 把你的max=2×Math.max(lenght1，lenght2)，就和我的是一个思想了。加速的方法可
: 以用
: trie，但复杂不少。

d*d2015-08-11 07:08

56 楼

这两个我都验证过阿,都对阿.

d*d2015-08-11 07:08

57 楼

我又验证了一遍,你这两个我都对阿.

【在 g***s 的大作中提到】

g*s2015-08-11 07:08

58 楼

敲错了，你再试试：
34234 342或者
34534 345
while外的return是啥？这两个都会跳出循环。本来应该一个return true，一个return
false。

【在 d*******d 的大作中提到】

: 我又验证了一遍,你这两个我都对阿.

d*d2015-08-11 07:08

59 楼

还真是.
现在搞明白了,确实max x2就对了.
while后面return true就可以了,其实如果出了while还没结果,return什么都没关系.
不过这个用trie加速也太不值了.

r*r2015-08-11 07:08

60 楼

一个动态规划的解法：
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*y2015-08-11 07:08

61 楼

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*d2015-08-11 07:08

62 楼

扔一块砖
/*
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*y2015-08-11 07:08

63 楼

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*d2015-08-11 07:08

64 楼

多谢指出错误。。。还是要多检查啊。
/*
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*n2015-08-11 07:08

65 楼

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*d2015-08-11 07:08

66 楼

看来是我的算法有错了，再仔细想想