s*****i
发帖数: 32 | 1 Given a byte array, which is an encoding of characters. Here is the rule:
a. If the first bit of a byte is 0, that byte stands for a one-byte
character
b. If the first bit of a byte is 1, that byte and its following byte
together stand for a two-byte character
Now implement a function to decide if the last character is a one-byte
character or a two-byte character
Constraint: You must scan the byte array from the end to the start.
Otherwise it will be very trivial. |
s****e
发帖数: 275 | 2 这有算法吗
int count = 0;
for(int i = n - 2; i 〉= 0 && firstBitIs1(a［i］); --i) ++count;
return cout & 1;
返回0表示是1字节，否则2字节
[发表自未名空间手机版 - m.mitbbs.com] |
x****g
发帖数: 1512 | 3 窃以为这不是一道好的面试题。
不能挖掘被面者的优缺点。
一定是弱老印出的？呵呵。 |
T******e
发帖数: 157 | 4 感觉有点像机器人走格子，用一个map记录，避免重复走 |
D****t
发帖数: 17 | 5 没有那么简单，所以是你弱 :-)
bool IsLastOneByteChar(unsigned char * bytes, int len)
{
int leadCount = 0;
len--;
bool lastByteIsLead = bytes[len] & 0x80;
while(len > 0)
{
if (bytes[len] & 0x80) leadCount++;
if (!(bytes[len] & 0x80)) break;
}
if (leadCount/2 == 0)
{
if (lastByteIsLead)
return true; //second byte of a 2-byte char
else
return false; //single byte char;
}
else
{
if (lastByteIsLead)
throw new Exception("invalid string");
else
return true; //second byte of a 2-byte char
}
}
【在 x****g 的大作中提到】
: 窃以为这不是一道好的面试题。
: 不能挖掘被面者的优缺点。
: 一定是弱老印出的？呵呵。
|
D****t
发帖数: 17 | 6 while(len > 0) 应该更正为 while(len >= 0) |
x****g
发帖数: 1512 | 7 你也是6666的老id啊.....
题目本身的简单或者复杂并不是我说的好题或者坏题。（虽然这题本身确实偏简单。）
题不好是指这个题本身能考量的东西多不多。
有没有逐步提升的变化和约束。
这么说吧，他出了这题，你10分钟写了以下答案。
他还能干啥？
你可以考虑怎么简化你的代码。
2楼的和你一样。除了少一句就可以判断的非法罢了，呵呵。
【在 D****t 的大作中提到】
: 没有那么简单，所以是你弱 :-)
: bool IsLastOneByteChar(unsigned char * bytes, int len)
: {
: int leadCount = 0;
: len--;
: bool lastByteIsLead = bytes[len] & 0x80;
: while(len > 0)
: {
: if (bytes[len] & 0x80) leadCount++;
: if (!(bytes[len] & 0x80)) break;
|
g*****g
发帖数: 212 | 8 Agree 这个算法。
解释一下：
从后向前，如果某一位是0了
那么可以肯定，0后面的不会是2 bytes的第二位。
因为后面都是1，也就是说，0后面的那位必然是2 bytes的第一位。
这个问题就是数有多少个1，如果1是奇数，那么这个就是2bytes的第二位，
否者1byte
【在 s****e 的大作中提到】
: 这有算法吗
: int count = 0;
: for(int i = n - 2; i 〉= 0 && firstBitIs1(a［i］); --i) ++count;
: return cout & 1;
: 返回0表示是1字节，否则2字节
: [发表自未名空间手机版 - m.mitbbs.com]
|
t**8
发帖数: 4527 | 9 how about
1xxxxxxx 0xxxxxxx 1xxxxxxx 1xxxxxxx
this is a valid 2 two-byte character
【在 g*****g 的大作中提到】
: Agree 这个算法。
: 解释一下：
: 从后向前，如果某一位是0了
: 那么可以肯定，0后面的不会是2 bytes的第二位。
: 因为后面都是1，也就是说，0后面的那位必然是2 bytes的第一位。
: 这个问题就是数有多少个1，如果1是奇数，那么这个就是2bytes的第二位，
: 否者1byte
|
x****g
发帖数: 1512 | 10 没问题.
本题的关键就是从后往前看到第一个0开始的点是个断点.
无论那个0开头自己解释自己还是跟它前面的那个走,(不可能跟后面走)
都不影响0开头的后面的那个是个起始字节这个结论.
所以就变成了奇偶问题了.
【在 t**8 的大作中提到】
: how about
: 1xxxxxxx 0xxxxxxx 1xxxxxxx 1xxxxxxx
: this is a valid 2 two-byte character
|
b*******d
发帖数: 750 | 11
maybe I'm wrong, but what about:
1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
odd number of "1", but the last character is a 2-byte character.
1xxxxxxx 0xxxxxxx 1xxxxxxx 0xxxxxxx
even number of "1", but the last character is still a 2-byte character.
【在 x****g 的大作中提到】
: 没问题.
: 本题的关键就是从后往前看到第一个0开始的点是个断点.
: 无论那个0开头自己解释自己还是跟它前面的那个走,(不可能跟后面走)
: 都不影响0开头的后面的那个是个起始字节这个结论.
: 所以就变成了奇偶问题了.
|
x****g
发帖数: 1512 | 12 从倒数第二位开始数到第一个0开头的数之间的1开头的个数。
不是全部1的个数......
你这个俩case一样都是：
3个和1个.
因为连续的1必然2个一组。所以奇数决定了最后是2字节含结束。
【在 b*******d 的大作中提到】
:
: maybe I'm wrong, but what about:
: 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
: odd number of "1", but the last character is a 2-byte character.
: 1xxxxxxx 0xxxxxxx 1xxxxxxx 0xxxxxxx
: even number of "1", but the last character is still a 2-byte character.
|
b*******d
发帖数: 750 | 13 dah, rite.
was confused by why it could count all "1"s..
【在 x****g 的大作中提到】
: 从倒数第二位开始数到第一个0开头的数之间的1开头的个数。
: 不是全部1的个数......
: 你这个俩case一样都是：
: 3个和1个.
: 因为连续的1必然2个一组。所以奇数决定了最后是2字节含结束。
|
