P****d
发帖数: 137 | 1 两个问题都是很简单的，一个LEETCODE的ATOI，一个是CC150的字母压缩
ATOI（String转number)，我用Linear的方法做了，他不满意，要我改进（他明确说了
是改进速度）。。。说如果
他告诉我这个数的范围，比如0-3000，我可不可以改进，我想了半天还是觉得不管怎么
样我们还是得一个一个字符去CHECK啊，求教有啥好方法吗？
字母压缩就是比如abbbccddeefgh，转换为a1b3c2d2e2f1g1h1，我新建了一个输出数组
来输出的，他问我能不能改进一下在同一个数组里操作。。。。这个题没有办法在同一
个数组操作吧，因为1个字母也要count，这样不论从前面还是后面开始我们操作的过程
中，over write的数组的部分都可能是我们还没有操作过的字符。。。。
真是百思不得其解
两个题都做出来了，就是上面两个FOLLOW UP问题根本没法做，百思不得其解 |
S****e
发帖数: 127 | 2 1. Use the hashtable to cache the results. So all the subsequent
transformation is constant for the same string.
2. For the letter count whose count is 1, omit the number, so yes, you can
do it on place. |
J****3
发帖数: 427 | 3 第二题 意思是输入abc 输出还是abc吗？
【在 S****e 的大作中提到】
: 1. Use the hashtable to cache the results. So all the subsequent
: transformation is constant for the same string.
: 2. For the letter count whose count is 1, omit the number, so yes, you can
: do it on place.
|
w*******s
发帖数: 138 | 4 1. compute hash code of a string is O(n)
【在 S****e 的大作中提到】
: 1. Use the hashtable to cache the results. So all the subsequent
: transformation is constant for the same string.
: 2. For the letter count whose count is 1, omit the number, so yes, you can
: do it on place.
|
w*****e
发帖数: 931 | 5 关于第二题我是这么想的：
1. 因为单独一个字母也要count，可能使得输出串甚至比输入更长，所以需要明确保证
数组有足够的空间。
2. 可以先从做往右扫一遍，遇上单独一个字母不用管，否则计数update。比如
abbbccddeefgh最后变成ab3c2d2e2fgh.记住数目为1的字母总数，这道题里面是4.
3. 已经能知道输出字符串的总长，从右往左scan。
【在 P****d 的大作中提到】
: 两个问题都是很简单的，一个LEETCODE的ATOI，一个是CC150的字母压缩
: ATOI（String转number)，我用Linear的方法做了，他不满意，要我改进（他明确说了
: 是改进速度）。。。说如果
: 他告诉我这个数的范围，比如0-3000，我可不可以改进，我想了半天还是觉得不管怎么
: 样我们还是得一个一个字符去CHECK啊，求教有啥好方法吗？
: 字母压缩就是比如abbbccddeefgh，转换为a1b3c2d2e2f1g1h1，我新建了一个输出数组
: 来输出的，他问我能不能改进一下在同一个数组里操作。。。。这个题没有办法在同一
: 个数组操作吧，因为1个字母也要count，这样不论从前面还是后面开始我们操作的过程
: 中，over write的数组的部分都可能是我们还没有操作过的字符。。。。
: 真是百思不得其解
|
c********p
发帖数: 1969 | |
s*****c
发帖数: 753 | 7 Have you communicate with them your thoughts? What's their response?
For interview, a big no no is to think for 5 min and then give an negative
answer. Should always told them your line of thought.
【在 P****d 的大作中提到】
: 两个问题都是很简单的，一个LEETCODE的ATOI，一个是CC150的字母压缩
: ATOI（String转number)，我用Linear的方法做了，他不满意，要我改进（他明确说了
: 是改进速度）。。。说如果
: 他告诉我这个数的范围，比如0-3000，我可不可以改进，我想了半天还是觉得不管怎么
: 样我们还是得一个一个字符去CHECK啊，求教有啥好方法吗？
: 字母压缩就是比如abbbccddeefgh，转换为a1b3c2d2e2f1g1h1，我新建了一个输出数组
: 来输出的，他问我能不能改进一下在同一个数组里操作。。。。这个题没有办法在同一
: 个数组操作吧，因为1个字母也要count，这样不论从前面还是后面开始我们操作的过程
: 中，over write的数组的部分都可能是我们还没有操作过的字符。。。。
: 真是百思不得其解
|
s*******z
发帖数: 83 | 8 可以加速的：四个字节看作一个int，hash{0X39323332} = hash{"9232"} = 9232;这样
你一次可以match上四个字符。
第二个：
abcdddededddd => abcd3eded4? |
l*******g
发帖数: 82 | 9 第二题，a-z 一共26个，用一个byte的高5bits存a-z，用剩下的3bits作为计数。
两个问题都是很简单的，一个LEETCODE的ATOI，一个是CC150的字母压缩ATOI（String
转number)，我用Linear的方法做了，他不满意，要我改进（他明确说........
【在 P****d 的大作中提到】
: 两个问题都是很简单的，一个LEETCODE的ATOI，一个是CC150的字母压缩
: ATOI（String转number)，我用Linear的方法做了，他不满意，要我改进（他明确说了
: 是改进速度）。。。说如果
: 他告诉我这个数的范围，比如0-3000，我可不可以改进，我想了半天还是觉得不管怎么
: 样我们还是得一个一个字符去CHECK啊，求教有啥好方法吗？
: 字母压缩就是比如abbbccddeefgh，转换为a1b3c2d2e2f1g1h1，我新建了一个输出数组
: 来输出的，他问我能不能改进一下在同一个数组里操作。。。。这个题没有办法在同一
: 个数组操作吧，因为1个字母也要count，这样不论从前面还是后面开始我们操作的过程
: 中，over write的数组的部分都可能是我们还没有操作过的字符。。。。
: 真是百思不得其解
|
j***e
发帖数: 2428 | 10 nice
String
【在 l*******g 的大作中提到】
: 第二题，a-z 一共26个，用一个byte的高5bits存a-z，用剩下的3bits作为计数。
:
: 两个问题都是很简单的，一个LEETCODE的ATOI，一个是CC150的字母压缩ATOI（String
: 转number)，我用Linear的方法做了，他不满意，要我改进（他明确说........
|
r*c
发帖数: 167 | 11
不明白，用hash对单独一次的转换有什么可加速的?
【在 s*******z 的大作中提到】
: 可以加速的：四个字节看作一个int，hash{0X39323332} = hash{"9232"} = 9232;这样
: 你一次可以match上四个字符。
: 第二个：
: abcdddededddd => abcd3eded4?
|
s*******z
发帖数: 83 | 12 你不用for循环了，只用一次寻址操作。另外我觉得这里考察的不一定是只有四个字节
，那个可能是一个提示吧。 |
P****d
发帖数: 137 | 13 不是的，1也要放进去,所以我说是傻X问题
【在 w*****e 的大作中提到】
: 关于第二题我是这么想的：
: 1. 因为单独一个字母也要count，可能使得输出串甚至比输入更长，所以需要明确保证
: 数组有足够的空间。
: 2. 可以先从做往右扫一遍，遇上单独一个字母不用管，否则计数update。比如
: abbbccddeefgh最后变成ab3c2d2e2fgh.记住数目为1的字母总数，这道题里面是4.
: 3. 已经能知道输出字符串的总长，从右往左scan。
|
