c**********r
发帖数: 472 | 1 Given a string of sorted integers, e.g. "1 52 69 456789 994546566";
and a a number e.g. 69.
You need to tell if it is in the input, e.g. 69=>true.
Write the code using the fastest algorithm. |
h**********l
发帖数: 6342 | 2 这个binary search阿
上次那个谁说过
【在 c**********r 的大作中提到】
: Given a string of sorted integers, e.g. "1 52 69 456789 994546566";
: and a a number e.g. 69.
: You need to tell if it is in the input, e.g. 69=>true.
: Write the code using the fastest algorithm.
|
l*****a
发帖数: 14598 | 3 string to integer array
need extra memory...
what will you know if there no extra memory?
【在 h**********l 的大作中提到】
: 这个binary search阿
: 上次那个谁说过
|
h**********l
发帖数: 6342 | 4 为什么要转成 int array?
直接 string比就完了阿
本来就不用extra memory
【在 l*****a 的大作中提到】
: string to integer array
: need extra memory...
: what will you know if there no extra memory?
|
l*****a
发帖数: 14598 | 5 string比就是KMP吧？
似乎有序的条件用不上
【在 h**********l 的大作中提到】
: 为什么要转成 int array?
: 直接 string比就完了阿
: 本来就不用extra memory
|
w****x
发帖数: 2483 | 6
binary search啦, 其实乱七八糟的逻辑挺多的
【在 l*****a 的大作中提到】
: string比就是KMP吧？
: 似乎有序的条件用不上
|
h**********l
发帖数: 6342 | 7 binary search 长的那个string
想象空格把长string 分成 一个array of strings
最坏还是 M*N, 平均 N*logM,
用 suffix tree可以 N+M最坏，N+logM平均
【在 l*****a 的大作中提到】
: string比就是KMP吧？
: 似乎有序的条件用不上
|
w****x
发帖数: 2483 | 8
binary search想想好像得计算字符串长度, 也没什么意义
【在 h**********l 的大作中提到】
: binary search 长的那个string
: 想象空格把长string 分成 一个array of strings
: 最坏还是 M*N, 平均 N*logM,
: 用 suffix tree可以 N+M最坏，N+logM平均
|
h**********l
发帖数: 6342 | 9 对于长的，log一下，速度还是可以的
match的话，那个linear，没法避免，用另外的datastructure，可以存下来后O（1）查
【在 w****x 的大作中提到】
:
: binary search想想好像得计算字符串长度, 也没什么意义
|
w****x
发帖数: 2483 | 10
我的意思是你一开始还得计算大字符串的长度, 要不咋二分
【在 h**********l 的大作中提到】
: 对于长的，log一下，速度还是可以的
: match的话，那个linear，没法避免，用另外的datastructure，可以存下来后O（1）查
|
|
|
h**********l
发帖数: 6342 | 11 c++ size() 是 o(1)，hoho
【在 w****x 的大作中提到】
:
: 我的意思是你一开始还得计算大字符串的长度, 要不咋二分
|
w****x
发帖数: 2483 | 12
那得假设你知道长度的情况下才二分, string那种包起来的
【在 h**********l 的大作中提到】
: c++ size() 是 o(1)，hoho
|
h**********l
发帖数: 6342 | 13 考点是 二分，别太挑剔吗
一些corner cases
不然， 你直接 return strstr()。。。。。。 一行
面试的人疯掉来的
【在 w****x 的大作中提到】
:
: 那得假设你知道长度的情况下才二分, string那种包起来的
|
l*****a
发帖数: 14598 | 14 不是挑剔
你需要给别人说明白你的算法
如果你明白了，面世官不明白
你觉得你能过吗？
【在 h**********l 的大作中提到】
: 考点是 二分，别太挑剔吗
: 一些corner cases
: 不然， 你直接 return strstr()。。。。。。 一行
: 面试的人疯掉来的
|
w****x
发帖数: 2483 | 15 考点是2分也得假设知道字符串长度啊, 不知道数一遍每啥意义啊, 还得遍历一遍 |
j********e
发帖数: 1192 | 16 M是数组string的长度吧？
用binary search，最坏也不是M*N，也是N*logM.每次分割，不会有unbalance
的情况。
不知道你suffix tree怎么弄到N+logM.
【在 h**********l 的大作中提到】
: binary search 长的那个string
: 想象空格把长string 分成 一个array of strings
: 最坏还是 M*N, 平均 N*logM,
: 用 suffix tree可以 N+M最坏，N+logM平均
|
h**********l
发帖数: 6342 | 17 行。。。。假设知道长度
【在 l*****a 的大作中提到】
: 不是挑剔
: 你需要给别人说明白你的算法
: 如果你明白了，面世官不明白
: 你觉得你能过吗？
|
h**********l
发帖数: 6342 | 18 最坏，大string就一个数，你当然要遍历一遍拉，你再想想
【在 j********e 的大作中提到】
: M是数组string的长度吧？
: 用binary search，最坏也不是M*N，也是N*logM.每次分割，不会有unbalance
: 的情况。
:
: 不知道你suffix tree怎么弄到N+logM.
|
t**********h
发帖数: 2273 | 19 数组上用二分得到logn是由于数组有random access，可以直接从start跳mid或者last
跳mid，你这个不转的前提上，怎么跳呢？一个一个判定再移过去，那么这个就不是
logN了。
而且，用空格当做分割时可以，但是两个空格之间的数字占的char个数不同，怎样再判
定了第一个数字之后，知道后面第3，第4个数字的下标是多少呢？
没想通怎样做到你描述的复杂度。详细解释细吧
【在 h**********l 的大作中提到】
: binary search 长的那个string
: 想象空格把长string 分成 一个array of strings
: 最坏还是 M*N, 平均 N*logM,
: 用 suffix tree可以 N+M最坏，N+logM平均
|
w****x
发帖数: 2483 | 20
last
那这题也没啥考点啊, 2分也没啥效果, 这题没意思
【在 t**********h 的大作中提到】
: 数组上用二分得到logn是由于数组有random access，可以直接从start跳mid或者last
: 跳mid，你这个不转的前提上，怎么跳呢？一个一个判定再移过去，那么这个就不是
: logN了。
: 而且，用空格当做分割时可以，但是两个空格之间的数字占的char个数不同，怎样再判
: 定了第一个数字之后，知道后面第3，第4个数字的下标是多少呢？
: 没想通怎样做到你描述的复杂度。详细解释细吧
|
|
|
M*****a
发帖数: 2054 | 21 这题显然可以bs啊
把字符串切开两半之后，从切开点向两边找空格
last
【在 t**********h 的大作中提到】
: 数组上用二分得到logn是由于数组有random access，可以直接从start跳mid或者last
: 跳mid，你这个不转的前提上，怎么跳呢？一个一个判定再移过去，那么这个就不是
: logN了。
: 而且，用空格当做分割时可以，但是两个空格之间的数字占的char个数不同，怎样再判
: 定了第一个数字之后，知道后面第3，第4个数字的下标是多少呢？
: 没想通怎样做到你描述的复杂度。详细解释细吧
|
t**********h
发帖数: 2273 | 22 你怎么知道本次该在那一个下标位置切这一刀呢？这刀切完后，怎找空格？如果是一个
一个下标move过去的话，那么就不是logN了啊。
牛人，写个程序吧，教导下我们菜鸟
【在 M*****a 的大作中提到】
: 这题显然可以bs啊
: 把字符串切开两半之后，从切开点向两边找空格
:
: last
|
t**********h
发帖数: 2273 | 23 如果在每一次的查找中，不能skip掉一些下标的话，而必须一个一个下标来判定，那么
和直接线性查找比，有什么优势呢？
【在 t**********h 的大作中提到】
: 你怎么知道本次该在那一个下标位置切这一刀呢？这刀切完后，怎找空格？如果是一个
: 一个下标move过去的话，那么就不是logN了啊。
: 牛人，写个程序吧，教导下我们菜鸟
|
M*****a
发帖数: 2054 | 24 没说让你必须log N啊
只是说要快
你要是整个输入就一个int,没有空格，那怎么log n?
【在 t**********h 的大作中提到】
: 你怎么知道本次该在那一个下标位置切这一刀呢？这刀切完后，怎找空格？如果是一个
: 一个下标move过去的话，那么就不是logN了啊。
: 牛人，写个程序吧，教导下我们菜鸟
|
t**********h
发帖数: 2273 | 25 那线性搞，算法最简单，然后O（n），你这样二分搞，优势在哪里呢？时间复杂度更优？
【在 M*****a 的大作中提到】
: 没说让你必须log N啊
: 只是说要快
: 你要是整个输入就一个int,没有空格，那怎么log n?
|
M*****a
发帖数: 2054 | 26 时间复杂度最差O(n)
优？
【在 t**********h 的大作中提到】
: 那线性搞，算法最简单，然后O（n），你这样二分搞，优势在哪里呢？时间复杂度更优？
|
I*I
发帖数: 618 | 27 1. strstr肯定不行，不光要match string，还要match大小。
2. 也不用二分，
3. 有O(N)算法
【在 c**********r 的大作中提到】
: Given a string of sorted integers, e.g. "1 52 69 456789 994546566";
: and a a number e.g. 69.
: You need to tell if it is in the input, e.g. 69=>true.
: Write the code using the fastest algorithm.
|
t**********h
发帖数: 2273 | 28 那和线性搞比，没优势啊，逻辑还很复杂。。。
【在 M*****a 的大作中提到】
: 时间复杂度最差O(n)
:
: 优？
|
h**********l
发帖数: 6342 | 29 qsort最差还o（n)呢
你说qsort没优势？
【在 t**********h 的大作中提到】
: 那和线性搞比，没优势啊，逻辑还很复杂。。。
|
w****x
发帖数: 2483 | |
|
|
t**********h
发帖数: 2273 | 31 问题是这题二分的最优的时间复杂度是多少呢？如果也是O（n），那么就没优势了，刚
才我的表述有问题，嗯
【在 h**********l 的大作中提到】
: qsort最差还o（n)呢
: 你说qsort没优势？
|
s*******f
发帖数: 1114 | 32 i think it is a good quiz for its messy code.
【在 w****x 的大作中提到】
: 我怀疑是不是面试官脑袋短路了出了个昏题
|
s*******f
发帖数: 1114 | 33 //回报本版，码遍本版
//Given a string of sorted integers, e.g. "1 52 69 456789 994546566";
//and a a number e.g. 69.
//You need to tell if it is in the input, e.g. 69=>true.
//strlen is O(n), don't use C style string for O(log n), suppose
//the string is friendly without lots of blank.
void GetWordPos(const char *mid, const char *left, const char *right, const
char **pstart, const char **pend){
while (isspace(*mid))
++mid;
*pstart = mid;
while (*pstart >= left && !isspace(**pstart))
--(*pstart);
if (isspace(**pstart))
++(*pstart);
*pend = mid;
while (*pend < right && !isspace(**pend))
++(*pend);
}
int StrCmp(const char *numstr, int numlen, const char *pstart, const char *
pend){
int len = pend - pstart;
if (numlen < len){
return -1;
} else if (numlen > len){
return 1;
} else {
while (*numstr && *numstr == *pstart){
++numstr;
++pstart;
}
if (!*numstr){
return 0;
} else if (*numstr < *pstart){
return -1;
} else {
return 1;
}
}
}
void IntToStr(int num, char *numstr, int *numlen){
//todo
return;
}
bool SearchString(const char *str, int num){
if (!str)
return false;
int len = strlen(str);
int left = 0;
int right = len;
char numstr[128];
int numlen = 0;
IntToStr(num, numstr, &numlen);
while (left < right){
int mid = left + (right - left) / 2;
const char *pstart, *pend;
GetWordPos(str + mid, str + left, str + right, &pstart, &pend);
int ret = StrCmp(numstr, numlen, pstart, pend);
if (ret == 0){
return true;
} else if (ret < 0){
right = pstart - 1 - str;
} else {
left = pend + 1 - str;
}
}
return false;
} |
l*****a
发帖数: 14598 | 34 店面你能把这些搞出来？
const
【在 s*******f 的大作中提到】
: //回报本版，码遍本版
: //Given a string of sorted integers, e.g. "1 52 69 456789 994546566";
: //and a a number e.g. 69.
: //You need to tell if it is in the input, e.g. 69=>true.
: //strlen is O(n), don't use C style string for O(log n), suppose
: //the string is friendly without lots of blank.
: void GetWordPos(const char *mid, const char *left, const char *right, const
: char **pstart, const char **pend){
: while (isspace(*mid))
: ++mid;
|
Z*****Z
发帖数: 723 | 35 用两个pointer扫描并且tokenize那个长string，如果token大小不match直接跳过，mat
ch了再逐位比较，成么
其实也不用match大小，就是tokenize+比较就是线性算法吧。
【在 I*I 的大作中提到】
: 1. strstr肯定不行，不光要match string，还要match大小。
: 2. 也不用二分，
: 3. 有O(N)算法
|
v****c
发帖数: 29 | 36 你看了n+1个字符还没看到空格，你不就知道他比那个数大了吗？
所以binary search的话O(n log m)是够了的
每次花O(n)时间寻找空格和比较大小（空格没找到说明比当前数字大）
【在 h**********l 的大作中提到】
: 最坏，大string就一个数，你当然要遍历一遍拉，你再想想
|
j********e
发帖数: 1192 | 37 整个string就是一个大数，也不需要遍历一遍。
例如从中点开始，不是空格，往前走N个，往后走N个，就知道当前数肯定
比目标数大了，然后就跳去1/4位置。
你再想想？
最坏，大string就一个数，你当然要遍历一遍拉，你再想想
【在 h**********l 的大作中提到】
: 最坏，大string就一个数，你当然要遍历一遍拉，你再想想
|
s*******f
发帖数: 1114 | 38 i didn't take long time.
just coding. remember do help function later
【在 l*****a 的大作中提到】
: 店面你能把这些搞出来？
:
: const
|
t**i
发帖数: 314 | 39 如果string中的integer是以空格间隔的话，下面是我的想法，大牛给看看可不可行
1. 把目标integer 转换成string s
2. 求s在原string str 中的index
3.1 （java里）如果返回-1，return false
3.2 如果返回一个正数，如果str这个index之前和s.length之后的那个字符都是空格就
return true,否则return false.
因为是sorted的，所以只需要检测第一个substring即可。
这个，我不会算复杂度。。。 |
d****o
发帖数: 1055 | 40 /*
curInt
curStr
flag=1
*/
Answer; time. O(n) space O(1)
bool findInput(string in, int target){
string s = intToString(target);
int i=0;
int flag=1;
int curInt=0;
while(i
if(in[i]!=' '&&flag==1){
curInt = curInt*10+(in[i]-'0');
} else if(in[i]!=' '&&flag==0){
curInt= in[i]-'0';
i++;
} else if(in[i]==' '&&flag==1){
if(curInt==target) return true;
else if(curInt>target) return false;
else {
curInt=0;
flag=0;
}
} else{
curInt=0;
flag=0;
}
i++;
}
if(i==in.size()){
if(curInt==target) return true;
else if(curInt>target) return false;
}
return false;
} |
|
|
d****o
发帖数: 1055 | 41 Time average O(lgn) worst O(n)
int findSubInt(string in,int mid,int& subBegin,int& subEnd){
subBegin=mid;
subEnd=mid;
while(in[subBegin]!=' '){
subBegin--;
}
if(in[subBegin]==' ') subBegin++;
while(in[subEnd]!=' '){
subEnd++;
}
if(in[subEnd]==' ') subEnd--;
string subStr = in.substr(subBegin,subEnd-subBegin+1);
return atoi(subStr.c_str());
}
bool findInt(string in, int target){
int begin =0;
int end = in.size();
while(begin<=end){
long long mid = (begin+end)/2;
while(mid>=0&&in[mid]==' '){
mid--;
}
if(mid<0){
begin=(begin+end)/2+1;
continue;
} else if(in[mid]!=' '){
int subBegin=0;
int subEnd=0;
int subInt = findSubInt(in,mid,subBegin,subEnd);
if(subInt>target){
end=subBegin-1;
continue;
} else if(subInt==target) return true;
else {
begin=subEnd+1;
continue;
}
}
}
return false;
}
【在 c**********r 的大作中提到】
: Given a string of sorted integers, e.g. "1 52 69 456789 994546566";
: and a a number e.g. 69.
: You need to tell if it is in the input, e.g. 69=>true.
: Write the code using the fastest algorithm.
|
n****r
发帖数: 120 | 42 C语言的话，就就假设字符串长度已知，C++和JAVA取字符串长度O(1)
既然已知长度，取中值，如果不是空格，则延中值向两边拓展，取到中间的数，
然后选取一侧继续。
可以这样二分吧！ |
j********x
发帖数: 2330 | 43 直接binary search，pivot处的字符串（如果正好是空格，就左移或者右移一位）按照
数字直接比较就行，不需要考虑是整数还是字符串，反正最后总是能缩到一个点上。。。
【在 l*****a 的大作中提到】
: string比就是KMP吧？
: 似乎有序的条件用不上
|
e****e
发帖数: 418 | 44
。。
Agree. Here is my code in Java.
public boolean isFind(String s, int n) {
int mid = s.length() / 2;
char midChar = s.charAt( mid );
if ( midChar == ' ' )
return isFind( s.substring( 0, mid ), n ) || isFind( s.
substring( mid + 1, s.length() ), n );
int rightMostLetterIdx = findRightMostLetterIndex( s, mid );
int leftMostLetterIdx = findLeftMostLetterIndex( s, mid );
String midNum = s.substring( leftMostLetterIdx, rightMostLetterIdx +
1 );
int midNumInt = Integer.parseInt(midNum);
if ( midNumInt == n )
return true;
if ( midNumInt < n && rightMostLetterIdx < s.length() - 2 )
return isFind( s.substring(rightMostLetterIdx + 2, s.length() ),
n );
if ( midNumInt > n && leftMostLetterIdx > 1 )
return isFind( s.substring(0, leftMostLetterIdx -1 ), n );
return false;
}
public int findRightMostLetterIndex(String s, int rightMostLetterIdx) {
while ( s.charAt( rightMostLetterIdx ) != ' ' && rightMostLetterIdx
< s.length() - 1 )
rightMostLetterIdx++;
if ( rightMostLetterIdx < s.length() - 1 )
rightMostLetterIdx--;
return rightMostLetterIdx;
}
public int findLeftMostLetterIndex(String s, int leftMostLetterIdx) {
while ( s.charAt( leftMostLetterIdx ) != ' ' && leftMostLetterIdx >
0 )
leftMostLetterIdx--;
if ( leftMostLetterIdx > 0 )
leftMostLetterIdx++;
return leftMostLetterIdx;
}
【在 j********x 的大作中提到】
: 直接binary search，pivot处的字符串（如果正好是空格，就左移或者右移一位）按照
: 数字直接比较就行，不需要考虑是整数还是字符串，反正最后总是能缩到一个点上。。。
|
