w****x
发帖数: 2483 | 1 //Print strings with certain prefix in a sorted string array
void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
OUT int& index1, int& index2);
void PrintComPrefix(const char* strs[], int n, const char* szPre)
{
assert(strs && szPre && n > 0);
const char* p = szPre;
int nIndex1 = 0;
int nIndex2 = n-1;
while (*p != 0 && nIndex1 >= 0)
{
GetIndex(strs, nIndex1, nIndex2, *p, p-szPre, nIndex1, nIndex2);
p++;
}
if (nIndex1 >= 0 && nIndex2 >= nIndex1)
{
for (int i = nIndex1; i <= nIndex2; i++)
cout<
}
else cout<<"No string contain this orefix"<
}
void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
OUT int& index1, int& index2)
{
if (nBeg < 0 || nEnd < nBeg || nPos < 0)
{
index1 = index2 = -1;
return;
}
//left boundary
int s = nBeg;
int e = nEnd;
index1 = -1;
while (s <= e)
{
int nMid = (s + e)/2;
if (strs[nMid][nPos] == chr && (nMid == nBeg ||
strs[nMid][nPos] != strs[nMid-1][nPos]))
{
index1 = nMid;
break;
}
else if (strs[nMid][nPos] > chr || strs[nMid][nPos] == chr)
e = nMid - 1;
else s = nMid + 1;
}
//right boundary
s = nBeg;
e = nEnd;
index2 = -1;
while (s <= e)
{
int nMid = (s + e)/2;
if (strs[nMid][nPos] == chr && (nMid == nEnd ||
strs[nMid][nPos] != strs[nMid+1][nPos]))
{
index2 = nMid;
break;
}
else if (strs[nMid][nPos] < chr || strs[nMid][nPos] == chr)
s = nMid + 1;
else e = nMid - 1;
}
} |
z****h
发帖数: 164 | 2 private void printstringwithprefix(String[] ss, String prefix) {
if(ss == null) return;
if(prefix == null || prefix.isEmpty()) return;
int low = 0;
int high = ss.length -1;
for(int i = 0; i< prefix.length() && low <= high; i++)
{
int mid = (low+high)/2;
if(i >= ss[mid].length())
{
return;
}
if(ss[mid].charAt(i) < prefix.charAt(i))
low = mid + 1;
else if(ss[mid].charAt(i) > prefix.charAt(i))
high = mid -1;
else // ==
{
low = mid;
high = mid;
while(low> 0 && ss[low - 1].charAt(i) == prefix.charAt(i))
--low;
while(high < ss.length -1 && ss[high + 1].charAt(i) ==
prefix.charAt(i))
++high;
}
}
if(low > high)
return;
for(int i = low; i <= high; i++)
Helper.println(ss[i]);
} |
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 4 这是zhangchi面经里的题吧？应该就是binary search吧。 |
w****x
发帖数: 2483 | 5
没啥trick, 就是binary search.
现在的题都没啥太难得, 就是考binary search的变种和编程的细节.
不过这题白板写说实话真心不容易
【在 p*****2 的大作中提到】
: 这是zhangchi面经里的题吧？应该就是binary search吧。
|
p*****2
发帖数: 21240 | 6
找两边的boundary能不能合并一下？做个sub function?
【在 w****x 的大作中提到】
:
: 没啥trick, 就是binary search.
: 现在的题都没啥太难得, 就是考binary search的变种和编程的细节.
: 不过这题白板写说实话真心不容易
|
l*****a
发帖数: 14598 | 7 把题说清楚点吧
是数组所有string的common prefix?
【在 w****x 的大作中提到】
: //Print strings with certain prefix in a sorted string array
: void GetIndex(const char* strs[], int nBeg, int nEnd, char chr, int nPos,
: OUT int& index1, int& index2);
: void PrintComPrefix(const char* strs[], int n, const char* szPre)
: {
: assert(strs && szPre && n > 0);
: const char* p = szPre;
: int nIndex1 = 0;
: int nIndex2 = n-1;
: while (*p != 0 && nIndex1 >= 0)
|
w****x
发帖数: 2483 | 8
其实还真能合, 写这个程序的时候这里就很别扭, 不过算了, 麻烦死了
【在 p*****2 的大作中提到】
:
: 找两边的boundary能不能合并一下？做个sub function?
|
p*****2
发帖数: 21240 | 9
呵呵。F家BS是必考的。这道题也差不多算很难的了。我有时间也得练练。这两天太累
，没心情做题。看你做的很开心呀。
【在 w****x 的大作中提到】
:
: 其实还真能合, 写这个程序的时候这里就很别扭, 不过算了, 麻烦死了
|
w****x
发帖数: 2483 | 10
感情受挫折了, 心烦做题玩, 每天都不知道该干啥, 难受死了.
一天也就两道题, 算起来一共就不到一小时, 短的半小时.
【在 p*****2 的大作中提到】
:
: 呵呵。F家BS是必考的。这道题也差不多算很难的了。我有时间也得练练。这两天太累
: ，没心情做题。看你做的很开心呀。
|
|
|
y**********u
发帖数: 6366 | 11 比我强
我发现我不光水平差，而且对cs完全没兴趣，书一看5页就想上youtube
太累
【在 w****x 的大作中提到】
:
: 感情受挫折了, 心烦做题玩, 每天都不知道该干啥, 难受死了.
: 一天也就两道题, 算起来一共就不到一小时, 短的半小时.
|
p*****2
发帖数: 21240 | 12
这么强？5页？我一般就看半页。
【在 y**********u 的大作中提到】
: 比我强
: 我发现我不光水平差，而且对cs完全没兴趣，书一看5页就想上youtube
:
: 太累
|
p*****2
发帖数: 21240 | 13 写了一个练练手。
// assume prefix exists
int Find(String[] words, String prefix, boolean left)
{
int l = 0;
int r = words.length - 1;
while (l < r)
{
int m = left ? l + (r - l) / 2 : l + (r - l + 1) / 2;
String s = words[m];
if (s.length() > prefix.length())
s = s.substring(0, prefix.length());
if (s.compareTo(prefix) < 0)
{
l = m + 1;
}
else if (s.compareTo(prefix) > 0)
{
r = m - 1;
}
else
{
if (left)
{
r = m;
}
else
{
l = m;
}
}
}
return l;
} |
w****x
发帖数: 2483 | 14
bug, while里是<=
【在 p*****2 的大作中提到】
: 写了一个练练手。
: // assume prefix exists
: int Find(String[] words, String prefix, boolean left)
: {
: int l = 0;
: int r = words.length - 1;
: while (l < r)
: {
: int m = left ? l + (r - l) / 2 : l + (r - l + 1) / 2;
: String s = words[m];
|
p*****2
发帖数: 21240 | 15
我怎么觉得＝＝的时候就可以退出了？我是assume prefix是存在的。
【在 w****x 的大作中提到】
:
: bug, while里是<=
|
w****x
发帖数: 2483 | 16
要是数组只有一个, 而且这个满足条件, 你的程序直接跳出来找不到了
【在 p*****2 的大作中提到】
:
: 我怎么觉得＝＝的时候就可以退出了？我是assume prefix是存在的。
|
p*****2
发帖数: 21240 | 17
String[] ss = new String[]
{ "aaa", "abc", "abcd", "abcde", "bbb" };
out.println(Find(ss, "abcde", true));
out.println(Find(ss, "abcde", false));
o我的程序返回3
【在 w****x 的大作中提到】
:
: 要是数组只有一个, 而且这个满足条件, 你的程序直接跳出来找不到了
|
z****h
发帖数: 164 | 18 为啥一定要找分两次找ｌｅｆｔ／ｒｉｇｈｔ？
遇到ｍ＝＝ｐｒｅｆｉｘ的时候，两边扩展一下找到边界不好吗？ |
p*****2
发帖数: 21240 | 19
那就是O(n)e了。
【在 z****h 的大作中提到】
: 为啥一定要找分两次找ｌｅｆｔ／ｒｉｇｈｔ？
: 遇到ｍ＝＝ｐｒｅｆｉｘ的时候，两边扩展一下找到边界不好吗？
|
w****x
发帖数: 2483 | 20
没仔细看你程序, 你试试数组就一个string: abcdef 找prefix "abc"能找到就成
【在 p*****2 的大作中提到】
:
: 那就是O(n)e了。
|
|
|
p*****2
发帖数: 21240 | 21
恩。返回的0.
【在 w****x 的大作中提到】
:
: 没仔细看你程序, 你试试数组就一个string: abcdef 找prefix "abc"能找到就成
|
t********e
发帖数: 143 | 22
没错，我总是搞不清最后几数。差不多4个case:
1. search for a number.
2. search for insert index.
3. search for lower bound of a range.
4. search for upper bound of range.
【在 w****x 的大作中提到】
:
: 没仔细看你程序, 你试试数组就一个string: abcdef 找prefix "abc"能找到就成
|
z****h
发帖数: 164 | 23 不是从头找。是二分找到一个相等值后，再左右两边扩展找左右边界。ｏ（ｌｇｎ +k
) k ＝有相同ｐｒｅｆｉｘ的ｓｔｒｉｎｇ的个数。
【在 p*****2 的大作中提到】
:
: 恩。返回的0.
|
z****h
发帖数: 164 | 24 int m = left ? l + (r - l) / 2 : l + (r - l + 1) / 2;
是为啥？
【在 p*****2 的大作中提到】
: 写了一个练练手。
: // assume prefix exists
: int Find(String[] words, String prefix, boolean left)
: {
: int l = 0;
: int r = words.length - 1;
: while (l < r)
: {
: int m = left ? l + (r - l) / 2 : l + (r - l + 1) / 2;
: String s = words[m];
|
p*****2
发帖数: 21240 | 25
+k
k跟n没什么区别。时间复杂度一样。
【在 z****h 的大作中提到】
: 不是从头找。是二分找到一个相等值后，再左右两边扩展找左右边界。ｏ（ｌｇｎ +k
: ) k ＝有相同ｐｒｅｆｉｘ的ｓｔｒｉｎｇ的个数。
|
p*****2
发帖数: 21240 | 26
不然会有死循环
【在 z****h 的大作中提到】
: int m = left ? l + (r - l) / 2 : l + (r - l + 1) / 2;
: 是为啥？
|
z****h
发帖数: 164 | 27 有道理
【在 p*****2 的大作中提到】
:
: 不然会有死循环
|
