谁能给个WM6.5下面的GPS下载吗？比如IGO啥的 - 未名空间MITBBS历史存档

谁能给个WM6.5下面的GPS下载吗？比如IGO啥的# PDA - 掌中宝

h*k2011-12-08 08:12

1 楼

平生第一次onsite，结果发挥失常，被KO。
第一个老题就出现了bug，严重影响了心情。这个bug是算法本身的问题，从来没有看到
大家提过。
题目是
在一个没有排序的数组里找两个数，它们的和等于给定的值。
我用的hash table的方法，就是扫描一遍，记录给定的值和当前的元素的差，存入hash
table。然后扫描第二编，判断这个值是不是已经存在于hash table中，如果是，输出。
上面的算法存在一个bug，如果数组中存在一个元素，它的值正好等于给定的值的一半
，这个元素会被输出。
第二个题是判断bst是不是合法，老题，我继续出错。
第三个题是Amazon的bar raiser问的。Amazon为了保证录取的人的质量，在每个on
site 面试中会派一个bar raiser进来，这个人一般不是想雇佣你的那个组的。他们在
获得bar raiser资格前，需要进行足够的培训。而且他们的意见非常重要，和hiring
manger的重要程度差不多，基本上具有一票否决权。所以大家以后面试Amazon，如果发
现谁不是要招你的那个组的，一定要小心。
题目是
有下列规律
0 -〉a
1 ->

d*o2011-12-08 08:12

2 楼

以前听女网友说男人爱听女人唱的歌，女人爱听男人唱的歌，我很不以为然。因为我虽
然欣赏女人唱的歌，但我更喜欢男人唱的歌，我可以投入进去，尽情地表达自己。后来
上网多了才发现，对大多数人来说这条定律是对的。喜欢我的女人几乎都把我想象成男
歌手对着她们深情歌唱，而喜欢我的男人则把我想象成女歌手对着他们如泣如诉。我有
一颗强悍的心，在我心中已经没有偶像了，所以更喜欢男人唱的歌；可大多数人都还是
需要偶像的，因而喜欢异性唱的歌，就好像偶像在关爱着他们。

c*n2011-12-08 08:12

3 楼

谢谢！

g*d2011-12-08 08:12

4 楼

//comft
第一个老题讨论过N回了,只有扫一遍.判断完后,加入hashtable.

d*o2011-12-08 08:12

5 楼

以前听女网友说男人爱听女人唱的歌，女人爱听男人唱的歌，我很不以为然。因为我虽
然欣赏女人唱的歌，但我更喜欢男人唱的歌，我可以投入进去，尽情地表达自己。后来
上网多了才发现，对大多数人来说这条定律是对的。喜欢我的女人几乎都把我想象成男
歌手对着她们深情歌唱，而喜欢我的男人则把我想象成女歌手对着他们如泣如诉。我有
一颗强悍的心，在我心中已经没有偶像了，所以更喜欢男人唱的歌；可大多数人都还是
需要偶像的，因而喜欢异性唱的歌，就好像偶像在关爱着他们。

u*n2011-12-08 08:12

6 楼

garmin mobile xt

M*52011-12-08 08:12

7 楼

最后一题感觉就是26进制转换

g*d2011-12-08 08:12

8 楼

第二道一定要判断左边最大的数第三道什么trick?

h*k2011-12-08 08:12

9 楼

只扫一遍如何做啊？

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

: //comft
: 第一个老题讨论过N回了,只有扫一遍.判断完后,加入hashtable.

M*52011-12-08 08:12

10 楼

第二题可以用recursion做

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

: 第二道一定要判断左边最大的数: 第三道什么trick?

h*k2011-12-08 08:12

11 楼

我一开始简单的把它等同于把一个10进制数转为26进制数，结果不是。
注意 26 -〉 AA 而不是BA

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

: 第二道一定要判断左边最大的数: 第三道什么trick?

g*d2011-12-08 08:12

12 楼

foreach number in array
{
if (hashtable.ContainsKey(k-number))
return true;
else
(hastable.Add(k);
}
return false;

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

: 只扫一遍如何做啊？

M*52011-12-08 08:12

13 楼

是aa啊，为啥要是ba

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

: 我一开始简单的把它等同于把一个10进制数转为26进制数，结果不是。
: 注意 26 -〉 AA 而不是BA

g*d2011-12-08 08:12

14 楼

相当于没有0的26进制 (1-26)?

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

: 我一开始简单的把它等同于把一个10进制数转为26进制数，结果不是。
: 注意 26 -〉 AA 而不是BA

M*52011-12-08 08:12

15 楼

好像是这个意思

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

: 相当于没有0的26进制 (1-26)?

h*k2011-12-08 08:12

16 楼

no, note that 0->a
26->aa, first A represents 1, and second A represents 0.

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

: 相当于没有0的26进制 (1-26)?

v*w2011-12-08 08:12

17 楼

pat
thanks for sharing
1，扫一遍就可以了，记录给定的值和当前的元素的差之前先看这个数在不在table里
3，10进制=〉26进制？有什么trick呢？

hash
出。

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

: 平生第一次onsite，结果发挥失常，被KO。
: 第一个老题就出现了bug，严重影响了心情。这个bug是算法本身的问题，从来没有看到
: 大家提过。
: 题目是
: 在一个没有排序的数组里找两个数，它们的和等于给定的值。
: 我用的hash table的方法，就是扫描一遍，记录给定的值和当前的元素的差，存入hash
: table。然后扫描第二编，判断这个值是不是已经存在于hash table中，如果是，输出。
: 上面的算法存在一个bug，如果数组中存在一个元素，它的值正好等于给定的值的一半
: ，这个元素会被输出。
: 第二个题是判断bst是不是合法，老题，我继续出错。

M*52011-12-08 08:12

18 楼

第一个a表示0（第一个字符），第二个也是一样的，都表示第一个字符，这样理解概念就一致了

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

: no, note that 0->a
: 26->aa, first A represents 1, and second A represents 0.

m*g2011-12-08 08:12

19 楼

it is indeed not easy to write this one.

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

: no, note that 0->a
: 26->aa, first A represents 1, and second A represents 0.

h*k2011-12-08 08:12

20 楼

是啊，我基本上就按照上面大家犯的错误一路错过来，在面试官的提示下一遍遍的改程
序。

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

: it is indeed not easy to write this one.

g*d2011-12-08 08:12

21 楼

我的惨痛教训是:
Interview exposed和careercup上面的每道题,要写N遍.不能只看N遍.简单道要想多想
加上限制条件.
现在的面试条件:一遍写出没有bug的时间最优解,然后再讨论空间最稳定解,加限制条件
最优解,thread-safe解,大数据量解,等等.

M*52011-12-08 08:12

22 楼

其实最后一道题不用那么复杂的，可以在需要处理的数字上加1，然后前面的26个数字
，每个数字加1，
比如
1->a
2->b
3->c
这样的话，如果是26的话，就相当于处理27，27/26=1....1
那么26实际上就表示成aa
27相当于28，28/26 = 1....2
那么27就表示成ab
我说的概念一致就是这个意思

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

: 是啊，我基本上就按照上面大家犯的错误一路错过来，在面试官的提示下一遍遍的改程
: 序。

M*52011-12-08 08:12

23 楼

其实也就相当于没有0的26进制，我觉得这个处理方法应该算是好理解，也好写code的

【在 M********5 的大作中提到】

: 其实最后一道题不用那么复杂的，可以在需要处理的数字上加1，然后前面的26个数字
: ，每个数字加1，
: 比如
: 1->a
: 2->b
: 3->c
: 这样的话，如果是26的话，就相当于处理27，27/26=1....1
: 那么26实际上就表示成aa
: 27相当于28，28/26 = 1....2
: 那么27就表示成ab

d*e2011-12-08 08:12

24 楼

我怎么觉得你说第一题的bug不是bug。

hash
出。

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

: 平生第一次onsite，结果发挥失常，被KO。
: 第一个老题就出现了bug，严重影响了心情。这个bug是算法本身的问题，从来没有看到
: 大家提过。
: 题目是
: 在一个没有排序的数组里找两个数，它们的和等于给定的值。
: 我用的hash table的方法，就是扫描一遍，记录给定的值和当前的元素的差，存入hash
: table。然后扫描第二编，判断这个值是不是已经存在于hash table中，如果是，输出。
: 上面的算法存在一个bug，如果数组中存在一个元素，它的值正好等于给定的值的一半
: ，这个元素会被输出。
: 第二个题是判断bst是不是合法，老题，我继续出错。

M*52011-12-08 08:12

25 楼

其实不是bug

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

: 我怎么觉得你说第一题的bug不是bug。
:
: hash
: 出。

h*k2011-12-08 08:12

26 楼

我的算法有bug。比如，如果给定的和是10，数组中只有一个5，以我的算法，第二遍扫
描到5，不能判断出数组中到底有多少个5。前面那个扫描一次的算法没有这个错误。

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

: 我怎么觉得你说第一题的bug不是bug。
:
: hash
: 出。

h*k2011-12-08 08:12

27 楼

那对于27*26，你的输出是多少？是AAA么？
这道题其实是使用了两种进制，最左边的位是27进制（0忽略掉，不用字符表示），其
他位都是26进制。
value = a_m* 26^(m) + ... + a_0; 0<= a_m <= 26, 0<=a_i <= 25 for 0<=iwhere m>= 2.
对于a_m, 0->不用输出，1->a, 2->b, ... 26->z,
对于a_i, 0->a, 1->b, ... 25->z

【在 M********5 的大作中提到】

: 其实最后一道题不用那么复杂的，可以在需要处理的数字上加1，然后前面的26个数字
: ，每个数字加1，
: 比如
: 1->a
: 2->b
: 3->c
: 这样的话，如果是26的话，就相当于处理27，27/26=1....1
: 那么26实际上就表示成aa
: 27相当于28，28/26 = 1....2
: 那么27就表示成ab

s*a2011-12-08 08:12

28 楼

27*26
27*26+1 % 26 = 1 =>A, left 27:
27%26 = 1 => A, left 1
1 => A
so it is AAA

h*k2011-12-08 08:12

29 楼

How about val=26*26+25?
val+1 % 26 = 0, which char will you use to represent it? According to rules,
val should be represented by ZZ

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

: 27*26
: 27*26+1 % 26 = 1 =>A, left 27:
: 27%26 = 1 => A, left 1
: 1 => A
: so it is AAA

D*h2011-12-08 08:12

30 楼

how about this. I test it seems ok.
#include
#include
using namespace std;
void num2alpha(int n){
vector vec;
vector::reverse_iterator it;
int i=n;
if(n==0)
vec.push_back('a');
else{
while(i>0){
vec.push_back('a'+n%26);
i=n/26;
n = n/26 -1;

}
}
for(it=vec.rbegin();it!=vec.rend();it++)
cout<cout<
}

H*r2011-12-08 08:12

31 楼

Is the job database related?
Here's the inverse problem:
http://programmerfindings.blogspot.com/2009/01/oracle-varchar-sequence-index-finder.html
Given the sequence, find the number...

hash
出。

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

: 平生第一次onsite，结果发挥失常，被KO。
: 第一个老题就出现了bug，严重影响了心情。这个bug是算法本身的问题，从来没有看到
: 大家提过。
: 题目是
: 在一个没有排序的数组里找两个数，它们的和等于给定的值。
: 我用的hash table的方法，就是扫描一遍，记录给定的值和当前的元素的差，存入hash
: table。然后扫描第二编，判断这个值是不是已经存在于hash table中，如果是，输出。
: 上面的算法存在一个bug，如果数组中存在一个元素，它的值正好等于给定的值的一半
: ，这个元素会被输出。
: 第二个题是判断bst是不是合法，老题，我继续出错。

s*t2011-12-08 08:12

32 楼

谢谢分享，
第三题确实有trick，编了一下，第一遍没有做到无bug。

hash
出。

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

: 平生第一次onsite，结果发挥失常，被KO。
: 第一个老题就出现了bug，严重影响了心情。这个bug是算法本身的问题，从来没有看到
: 大家提过。
: 题目是
: 在一个没有排序的数组里找两个数，它们的和等于给定的值。
: 我用的hash table的方法，就是扫描一遍，记录给定的值和当前的元素的差，存入hash
: table。然后扫描第二编，判断这个值是不是已经存在于hash table中，如果是，输出。
: 上面的算法存在一个bug，如果数组中存在一个元素，它的值正好等于给定的值的一半
: ，这个元素会被输出。
: 第二个题是判断bst是不是合法，老题，我继续出错。

g*d2011-12-08 08:12

33 楼

这个行吗?
if (n < 0)
return false;
if(n<=25)
v.push_back('a' + n);
else
{
while(n>25)
{
v.push_back('a' + n%26);
n = n / 26;
}
v.push_back('a' + n - 1);
}
或者
if (n < 0)
return false;
else
{
while(n>25)
{
v.push_back('a' + n%26);
n = n / 26;
}

if(v.isEmpty())
v.push_back('a' + n);
else
v.push_back('a' + n - 1);
}

q*12011-12-08 08:12

34 楼

mark

h*k2011-12-08 08:12

35 楼

好像不对，比如26*26->ZA，你的输出是AAA

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

: 这个行吗?
: if (n < 0)
: return false;
: if(n<=25)
: v.push_back('a' + n);
: else
: {
: while(n>25)
: {
: v.push_back('a' + n%26);

g*d2011-12-08 08:12

36 楼

明白了,还是需要Depth大作中的-1操作.

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

: 好像不对，比如26*26->ZA，你的输出是AAA

M*52011-12-08 08:12

37 楼

我提出的算法依然是没有问题的，只是需要加一个特殊情况，可能我先没有考虑，就是
余数为0的情况，
因为在我前面提到的表示方式中，0并没有用字母来表示，所以这一题还是有trick，只
不过我说的大体
思路也没有错
如果余数为0，那么这个数的表示方式肯定是
a1*26^1 + a2*26^2 + ... + an*26^n + 25
然后用这个数（原来的数）减去25，然后再依次除以26，把所有的系数算出来，最后加
上z就可以了
我说我的算法是正确的我其实是可以证明的，我可以想想把我的证明写上来
我觉得这应该是这种题目的基本解题思路

rules,

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

: How about val=26*26+25?
: val+1 % 26 = 0, which char will you use to represent it? According to rules,
: val should be represented by ZZ

M*52011-12-08 08:12

38 楼

其实这一题的trick就是前面那个美食家说的，它实际上是没有零的26进制

D*h2011-12-08 08:12

39 楼

这个没错
BDD 是 2*26*26+4*26+3

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

: 好像不对，比如26*26->ZA，你的输出是AAA

h*k2011-12-08 08:12

40 楼

不用证明，写个程序，然后做个循环，计算从0到28*26，比较一下输出是否对就可以了。BTW: 28*26应该是 ABA

【在 M********5 的大作中提到】

: 我提出的算法依然是没有问题的，只是需要加一个特殊情况，可能我先没有考虑，就是
: 余数为0的情况，
: 因为在我前面提到的表示方式中，0并没有用字母来表示，所以这一题还是有trick，只
: 不过我说的大体
: 思路也没有错
: 如果余数为0，那么这个数的表示方式肯定是
: a1*26^1 + a2*26^2 + ... + an*26^n + 25
: 然后用这个数（原来的数）减去25，然后再依次除以26，把所有的系数算出来，最后加
: 上z就可以了
: 我说我的算法是正确的我其实是可以证明的，我可以想想把我的证明写上来

b*y2011-12-08 08:12

41 楼

第三题当场很难作对啊，amazon这种不提前做真题看来拿不到Offer了。
我贴一个，大家给看看。
====================
#include
#include
using namespace std;
void num2str(int num) {
vector str;
int value;
bool first = true;
while(num != -1) {
value = num % 26;
str.push_back('a'+value);
num = num / 26 -1;
}
vector::reverse_iterator rit;
for ( rit=str.rbegin() ; rit < str.rend(); ++rit )
cout << *rit;
cout<}
int main() {
cout<

h*k2011-12-08 08:12

42 楼

cout<这个case好像有问题
AZZ = 1*27*26+25*26+25
BAA = 1*27*26+26*26=53*26
所以 bdd = 53*26+3*26+3 不是52*26+3*26+3

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

: 第三题当场很难作对啊，amazon这种不提前做真题看来拿不到Offer了。
: 我贴一个，大家给看看。
: ====================
: #include
: #include
: using namespace std;
: void num2str(int num) {
: vector str;
: int value;
: bool first = true;

M*52011-12-08 08:12

43 楼

28*26 + 1 /26 = 28....1->A
28/26 = 1...2->B
1/26 = 0 ...1->A
这个没错
一会忙完了写代码，测试了贴上来

了。BTW:
28*26应该是 ABA

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

: 不用证明，写个程序，然后做个循环，计算从0到28*26，比较一下输出是否对就可以了。BTW: 28*26应该是 ABA

j*l2011-12-08 08:12

44 楼

版上面经要多看，反反复复的老题要熟悉
http://www.mitbbs.com/article_t1/JobHunting/31649757_0_1.html
我第三次Amazon电面写的
bool has_num(int integers[], int n, int target)
{
if (integers == NULL || n < 2)
return false;
Hashtable table;
for (int i = 0; i < n; i++)
{
if (table.contains(target - integers[i])
return true;
table.add(integers[i]);
}
return false;
}

m*f2011-12-08 08:12

45 楼

扫描两遍本身就不对，应该是一遍每次在hash里面找sum-x吧

hash
出。

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

: 平生第一次onsite，结果发挥失常，被KO。
: 第一个老题就出现了bug，严重影响了心情。这个bug是算法本身的问题，从来没有看到
: 大家提过。
: 题目是
: 在一个没有排序的数组里找两个数，它们的和等于给定的值。
: 我用的hash table的方法，就是扫描一遍，记录给定的值和当前的元素的差，存入hash
: table。然后扫描第二编，判断这个值是不是已经存在于hash table中，如果是，输出。
: 上面的算法存在一个bug，如果数组中存在一个元素，它的值正好等于给定的值的一半
: ，这个元素会被输出。
: 第二个题是判断bst是不是合法，老题，我继续出错。

b*n2011-12-08 08:12

46 楼

修改了一下:
if (n < 0)
return false;
if(n<=25)
v.push_back('a' + n);
else
{
int i=n;
while(i>25)
{
v.push_back('a' + n%26);
n = n / 26;
i = n-1;
}
v.push_back('a' + i);
}
Test Cases:
3 -> D
25 -> Z
26 -> AA
51 -> AZ
52 -> BA
26*26 -> ZA
26*26+25 -> ZZ
1*26*26 -> AAA
2*26*26+3*26+3 -> BDD

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

: 这个行吗?
: if (n < 0)
: return false;
: if(n<=25)
: v.push_back('a' + n);
: else
: {
: while(n>25)
: {
: v.push_back('a' + n%26);

h*k2011-12-08 08:12

47 楼

bdd 不是 2*26*26+3*26+3，而是(27+26)*26+3*26+3

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

: 修改了一下:
: if (n < 0)
: return false;
: if(n<=25)
: v.push_back('a' + n);
: else
: {
: int i=n;
: while(i>25)
: {

P*t2011-12-08 08:12

48 楼

The 3rd one isn't any traditional number.
If you still use 10 to rewrite those number, you will find that:
0,
1,
...
9,
00,
01,
...
99,
000,
....
999
for digits=1, there will be 10 numbers. For digits=2, there will additional
100.
Therefore you first need to find how many digits you need to use to rewrite
the given number. it will be in some range of:
26^N < X < 26 ^ (N+1)
The you do X-26^N, and fill the rest digits.
Try this below:
#include
#include
using namespace std;
cons

b*y2011-12-08 08:12

49 楼

你的结果和我的一样，
============================
#include
#include
using namespace std;
void num2str(int num) {
vector str;
vector::reverse_iterator rit;
const int step = 3;
int value;
bool first = true;
while(num != -1) {
value = num % step;
str.push_back('a'+value);
num = num / step -1;
}
for (rit = str.rbegin(); rit < str.rend(); ++rit)
cout << *rit;
cout<}
int NumString() {
for (int i = 0;

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

: The 3rd one isn't any traditional number.
: If you still use 10 to rewrite those number, you will find that:
: 0,
: 1,
: ...
: 9,
: 00,
: 01,
: ...
: 99,

I*y2011-12-08 08:12

50 楼

这道题确实有些trick在里面。昨晚想了很长时间，下面的代码应该没有问题：
#include
#include
using namespace std;
deque n2s(int n)
{
std::deque s;
int j = n % 26 ;
n /=26;
s.push_front('A' + j);
while(n)
{
j = n % 26 ;
s.push_front('A' + (j + 25) % 26); // 这里j=1->a,...,0->z
n = n / 26;
if(j==0) // 这里j=0时需要调整，不然输出序列为YZ,AZA,AZB,...,AZZ,
AAA...
n -= 1;
}
return s;
}
int main()
{
int a = numeric_limits::max();
for(i

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

: bdd 不是 2*26*26+3*26+3，而是(27+26)*26+3*26+3

P*t2011-12-08 08:12

51 楼

Zan!

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

: 你的结果和我的一样，
: ============================
: #include
: #include
: using namespace std;
: void num2str(int num) {
: vector str;
: vector::reverse_iterator rit;
: const int step = 3;
: int value;

w*32011-12-08 08:12

52 楼

如果有重复呢?
找sum = 5
1,2,2,3
和
3,2,2,1 的输出会不同

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

: foreach number in array
: {
: if (hashtable.ContainsKey(k-number))
: return true;
: else
: (hastable.Add(k);
: }
: return false;

P*b2011-12-08 08:12

53 楼

amazon的题目那么多，咋做真题阿

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

: 第三题当场很难作对啊，amazon这种不提前做真题看来拿不到Offer了。
: 我贴一个，大家给看看。
: ====================
: #include
: #include
: using namespace std;
: void num2str(int num) {
: vector str;
: int value;
: bool first = true;

w*h2011-12-08 08:12

54 楼

好象第三题没有什么trick啊. 就是全组合的代数,
26^1 + 26^2 + 26^3 ...
各项对应string长度，所以算法很直接：第一步确定string长度N，第二步在给定N的集
合内把数字转成string,就是在26x26..x26的"矩阵"里计算每维的整数位置坐标（可以
取0, ..., 25）
///
/// num2str.cpp
///
#include
#include
const static char a = 'a';
const static int b = 26;
namespace MyNum2Str
{

long int pow(int a, int b)
{
long int a2b = 1;
for ( int i = 0; i < b; i++ )
a2b *= a;
return a2b;
}
int num2strlen ( int M )
{
// 第一步确定string长度
int N = 1, sum = 0;

t*j2011-12-08 08:12

55 楼

第一个楼上有人说过了。
第二个左遍历，若输出非但调递增序列，则invalid.

hash
出。

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

: 平生第一次onsite，结果发挥失常，被KO。
: 第一个老题就出现了bug，严重影响了心情。这个bug是算法本身的问题，从来没有看到
: 大家提过。
: 题目是
: 在一个没有排序的数组里找两个数，它们的和等于给定的值。
: 我用的hash table的方法，就是扫描一遍，记录给定的值和当前的元素的差，存入hash
: table。然后扫描第二编，判断这个值是不是已经存在于hash table中，如果是，输出。
: 上面的算法存在一个bug，如果数组中存在一个元素，它的值正好等于给定的值的一半
: ，这个元素会被输出。
: 第二个题是判断bst是不是合法，老题，我继续出错。

b*h2011-12-08 08:12

56 楼

来一个短一点的
string num2str(int n)
{
string ret(1, char(n%26+'a'));
n /= 26;
while(n > 0) {
ret = char((n-1)%26+'a') + ret;
n = (n-1)/26;
}
return ret;
}

w*h2011-12-08 08:12

57 楼

很好! 你这个方法妙在两点:
1) 从低位往高位算, 所以也能同时定字符长度, 我的方法从高位往低位算, 必须分两
步, 先定字符长度, 比较笨.
2) 更重要的是, 很好的利用了几何级数等形式的递归特点. 所以利用这个可以很容易
写递归的版本: string(n) = char(n) + string(n-1) (说到"短一点的", 呵呵)
#include
#include
std::string & num2strn( int n, std::string & s )
{
if ( n < 0 )
return s;
return num2strn( ( n / 26 - 1 ), s = char( 'a' + n % 26 ) + s );
}
几何级数增长很快, 所以递归堆栈调用也不会太深.

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

: 来一个短一点的
: string num2str(int n)
: {
: string ret(1, char(n%26+'a'));
: n /= 26;
: while(n > 0) {
: ret = char((n-1)%26+'a') + ret;
: n = (n-1)/26;
: }
: return ret;

w*h2011-12-08 08:12

58 楼

很好! 你这个方法妙在两点:
1) 从低位往高位算, 所以也能同时定字符长度, 我的方法从高位往低位算, 必须分两
步, 先定字符长度, 比较笨.
2) 更重要的是, 很好的利用了几何级数等形式的递归特点. 所以利用这个可以很容易
写递归的版本: string(n) = char(n) + string(n-1) (说到"短一点的", 呵呵)
#include
std::string & num2strn( int n, std::string & s )
{
if ( n < 0 )
return s;
return num2strn( ( n / 26 - 1 ), s = char( 'a' + n % 26 ) + s );
}
几何级数增长很快, 所以递归堆栈调用也不会太深.

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

: 来一个短一点的
: string num2str(int n)
: {
: string ret(1, char(n%26+'a'));
: n /= 26;
: while(n > 0) {
: ret = char((n-1)%26+'a') + ret;
: n = (n-1)/26;
: }
: return ret;

f*g2011-12-08 08:12

59 楼

第二题
如何处理相同元素？

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

: 第一个楼上有人说过了。
: 第二个左遍历，若输出非但调递增序列，则invalid.
:
: hash
: 出。

i*e2011-12-08 08:12

60 楼

你的解法很好！
也可以用递归，这样就可以直接打印，不需要储存空间。
因为递归本身就好比stack，这样就能从后到前的秩序把字符串显示出来。
void num2StrHelper(int n) {
if (n == 0) return;
num2StrHelper((n-1)/26);
cout << (char)('a'+(n-1)%26);
}
void num2str(int n) {
num2StrHelper(n/26);
cout << (char)('a'+n%26);
}
不知道大家有没有发现，其实这题如果改成:
1->A
2->B
...
27->AA
...
这题就会简单好多。因为直接把10进制转换成26进制就得了。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: 来一个短一点的
: string num2str(int n)
: {
: string ret(1, char(n%26+'a'));
: n /= 26;
: while(n > 0) {
: ret = char((n-1)%26+'a') + ret;
: n = (n-1)/26;
: }
: return ret;

w*x2011-12-08 08:12

61 楼

谢谢楼主分享. 刚才试着解了一下第三题, 犯了一个低级错误: 要先算remainder再算
quotient, 我一开始搞反了......
static char toChar(int number) {
return (char) (number % 26 + 97);
}

static void toBase26(int number) {
// do not handle negative number
if (number < 0) {
return;
}
char[] result = new char[1000];
int quotient = number;
int remainder = 0;
int i = 0;
do {
remainder = quotient % 26;
quotient = quotient / 26

n*n2011-12-08 08:12

62 楼

bst has duplicates?

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

: 第二题
: 如何处理相同元素？

n*n2011-12-08 08:12

63 楼

本质上还是，只是多一步映射转换：
y = x - 26^1 -26^2 - ... - 26^k >=0
然后将y转换成26进制，再将这个串补足leading zero即可。

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

: 我一开始简单的把它等同于把一个10进制数转为26进制数，结果不是。
: 注意 26 -〉 AA 而不是BA

n*n2011-12-08 08:12

64 楼

bst => in-order traversal sorted.
what is left traversal? in-order and post-order both visit left kid 1st.

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

: 第一个楼上有人说过了。
: 第二个左遍历，若输出非但调递增序列，则invalid.
:
: hash
: 出。

B*d2011-12-08 08:12

65 楼

很明显，这是一个放水型的面试，居然这样都被搞砸，实在不应该。

t*j2011-12-08 08:12

66 楼

就是中序遍历,in-order。不知道为啥，exposed那本书上好像叫左遍历。
不过我看的是中文版，可能翻译错了。

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

: bst => in-order traversal sorted.
: what is left traversal? in-order and post-order both visit left kid 1st.

i*e2011-12-08 08:12

67 楼

我觉得没有放水吧，问题都适中。
以客观的角度来看，LZ犯得错误都情有可原，更何况是LZ生平第一个on-site。再说第
一个问题就出现了bug，但不应让它影响之后的发挥。多累计面试经验就会好点的了。
不过面试就那么残忍，你只有一次机会证明你自己，而且面试官都已经assume你已有充
分准备。除非你是天才，不然多准备，多练习，多积累经验，对你面试绝对有大大的帮
助。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

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

: 很明显，这是一个放水型的面试，居然这样都被搞砸，实在不应该。

e*62011-12-08 08:12

68 楼

第三题感觉就是：个位数从0-25，其余位都是1-26；把十进制转换为26进制。特殊处理
个位即可。。
这么写应该就行：
stack mys;
mys.push('A'+val%26);
val/=26;
while(val){
val--;
mys.push('A'+val%26);
val/=26;
}
while(!mys.empty()){
cout<mys.pop();
}
cout<

b*g2011-12-08 08:12

69 楼

假设输入是n
n+1, 再转换10到26进制就是了.
1 -> A
27-> AA
注意,判断一下,最大int 值,直接输出就可以了.
否则再加1会溢出.

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

: 我一开始简单的把它等同于把一个10进制数转为26进制数，结果不是。
: 注意 26 -〉 AA 而不是BA

c*t2011-12-08 08:12

70 楼

你说的没错，我也是按这个思路。先加 1，然后 %，碰到0转换成z，没问题。
我写了个java 版本
/*
* convert
* 0->a
* 1 -> b
* 2 -> c
* 3 -> d
* ......
* 25 -> z
* 26 -> aa
* 27 -> ab
* ......
*/
public class ConvertIntToChar {

static String intToChar(int a) {
if (a < 0) return "";

a += 1;
StringBuilder output = new StringBuilder();
char theChar;

while (a > 0) {
if (a % 26 == 0) {
theChar = 'z';
} else {
theChar = (char) ((a-1) % 26 + 'a');
}
output.insert(0,theChar);
a= (a- 1)/26;
}
return output.toString();
}
/**
* @param args
*/
public static void main(String[] args) {
System.out.print("d:" + intToChar(3)+"\n");
System.out.print("z:" + intToChar(25)+"\n");
System.out.print("aa:" + intToChar(26)+"\n");
System.out.print("ab:" + intToChar(27)+"\n");
System.out.print("za:" + intToChar(26 * 26)+"\n");
System.out.print("zz:" + intToChar(26 * 26 + 25)+"\n");
System.out.print("aaa:" + intToChar(27 * 26)+"\n");
System.out.print("aba:" + intToChar(28 * 26)+"\n");
System.out.print("bcd:" + intToChar(2 * 26 * 26 + 3 * 26 + 3)+"\n");
System.out.print("bdd:" + intToChar(2 * 26 * 26 + 4 * 26 + 3)+"\n");
}
}
不过有个同学说得对，还要特殊处理最大整数，否则+1溢出。这个我还没做。

【在 M********5 的大作中提到】

: 其实最后一道题不用那么复杂的，可以在需要处理的数字上加1，然后前面的26个数字
: ，每个数字加1，
: 比如
: 1->a
: 2->b
: 3->c
: 这样的话，如果是26的话，就相当于处理27，27/26=1....1
: 那么26实际上就表示成aa
: 27相当于28，28/26 = 1....2
: 那么27就表示成ab

c*t2011-12-08 08:12

71 楼

关于我这个解法，有两个问题，哪位帮帮忙？
1.还要特殊处理最大整数，否则+1溢出，怎么做比较好？
2.我想改写成递归，想把结果存到String里，不知怎么改？

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

: 你说的没错，我也是按这个思路。先加 1，然后 %，碰到0转换成z，没问题。
: 我写了个java 版本
: /*
: * convert
: * 0->a
: * 1 -> b
: * 2 -> c
: * 3 -> d
: * ......
: * 25 -> z

q*82011-12-08 08:12

72 楼

那个第一个错误我也犯了，电面的时候，不过当场改了，在hashtable里存出现的次数
好像可以解决，因为貌似只有一半时候会出现这个bug。