l****r
发帖数: 689 | 1 被recruiter 弄了连续面了2个组：
老印和中国人, 虽然国人不是主面试官，但是是不是的帮我一下，比如纠正我代码的
bug，但是说得不明显
1。查找2个单词的距离
/*
* Example:
* WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
"quick", "brown", "fox", "quick"));
* assert(finder.distance("fox","the") == 3);
* assert(finder.distance("quick", "fox") == 1);
*/
2. 洗牌 要求in-place
第二面：老印和abc
中间abc一直没有吭声过。。。貌似这个题很常见，我另外2个朋友电面都碰到了，原题
，大家好好准备，其实不难，就是edge容易忽略
* Return the smallest character that is strictly larger than the search
character,
* ['c', 'f', 'j', 'p', 'v'], 'a' => 'c' | g***j
发帖数: 1275 | 2 第二题就是leetcode 里面的“Search Insert Position”吧
",
【在 l****r 的大作中提到】
: 被recruiter 弄了连续面了2个组：
: 老印和中国人, 虽然国人不是主面试官，但是是不是的帮我一下，比如纠正我代码的
: bug，但是说得不明显
: 1。查找2个单词的距离
: /*
: * Example:
: * WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
: "quick", "brown", "fox", "quick"));
: * assert(finder.distance("fox","the") == 3);
: * assert(finder.distance("quick", "fox") == 1);
| l*****a
发帖数: 14598 | 3 你背题太严重
至少LZ没告诉你输入数组有序
【在 g***j 的大作中提到】
: 第二题就是leetcode 里面的“Search Insert Position”吧
:
: ",
| g***j
发帖数: 1275 | 4 如果没排序的，就scan一遍，相当于找max，没有point，另外给的例子排序了。
【在 l*****a 的大作中提到】
: 你背题太严重
: 至少LZ没告诉你输入数组有序
| k****f
发帖数: 19 | 5 1。查找2个单词的距离
请问除了建立一个对dict所有单词的hash表，有没有别的办法可以有o(1)的效率啊 | j**********3
发帖数: 3211 | | t*******e
发帖数: 274 | 7 你这个距离是指每个单词在list中的距离？看你的例子，list中有两个'quick'，但返
回的是1，所以还要必须是最短距离？ | l****r
发帖数: 689 | 8 单词的
：你这个距离是指每个单词在list中的距离还是两个单词中字母间的距离，从你的例子
上我看不太明白？
： | l*****p
发帖数: 11 | 9 洗牌就是52张牌，打乱顺序吗？还是有别的条件？谢谢～～ | l****r
发帖数: 689 | 10 嗯，打乱顺序，最后要求证明，为什么概率是一样的
：洗牌就是52张牌，打乱顺序吗？还是有别的条件？谢谢～～ | | | j**********3
发帖数: 3211 | 11 怎么证明？
【在 l****r 的大作中提到】
: 嗯，打乱顺序，最后要求证明，为什么概率是一样的
:
: ：洗牌就是52张牌，打乱顺序吗？还是有别的条件？谢谢～～
| l*****a
发帖数: 14598 | 12 第一章52种可能
第二章51种
一共52!种,全排列
【在 j**********3 的大作中提到】
: 怎么证明？
| h*******e
发帖数: 1377 | | l****r
发帖数: 689 | | m**s
发帖数: 61 | 15 第三个的原题 CC 上是这样描述的
http://www.careercup.com/question?id=5726366532108288
/**
* Return the smallest character that is strictly larger than the search
character,
* If no such character exists, return the smallest character in the array
* @param sortedStr : sorted list of letters, sorted in ascending order.
* @param c : character for which we are searching.
* Given the following inputs we expect the corresponding output:
* ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'
* ['c', 'f', 'j', 'p', 'v'], 'c' => 'f'
* ['c', 'f', 'j', 'p', 'v'], 'k' => 'p'
* ['c', 'f', 'j', 'p', 'v'], 'z' => 'c' // The wrap around case
* ['c', 'f', 'k'], 'f' => 'k'
* ['c', 'f', 'k'], 'c' => 'f'
* ['c', 'f', 'k'], 'd' => 'f'
*/
我参照了CC上的Java的solution，用C改写了一下，length是数组的长度。
大牛们能给看看,找找毛病吗？
char findNextChar(char[] list, int length, char target)
{
// target is not within the list, just return the 1st char
if (target < list[0] || target > list[length - 1])
return list[0];
int left = 0, right = length - 1;
char result = list[0];
while (left < right) {
int mid = (left + right)/ 2;
if (list[mid] == target) {
return list[mid+1];
}
else if (list[mid] < target) {
left = mid + 1;
}
else {
result = list[mid];
right = mid - 1;
}
}
return result;
}
",
【在 l****r 的大作中提到】
: 被recruiter 弄了连续面了2个组：
: 老印和中国人, 虽然国人不是主面试官，但是是不是的帮我一下，比如纠正我代码的
: bug，但是说得不明显
: 1。查找2个单词的距离
: /*
: * Example:
: * WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
: "quick", "brown", "fox", "quick"));
: * assert(finder.distance("fox","the") == 3);
: * assert(finder.distance("quick", "fox") == 1);
| l*****a
发帖数: 14598 | 16 char findNextChar(char[] list, int length, char target)
{
==>need error handling for list
// target is not within the list, just return the 1st char
if (target < list[0] || target > list[length - 1])
return list[0];
==> why return list[0] when target>
int left = 0, right = length - 1;
char result = list[0];
while (left < right) {
int mid = (left + right)/ 2;
==> overflow
if (list[mid] == target) {
return list[mid+1];
==>how about there are duplicate list[mid]
}
else if (list[mid] < target) {
left = mid + 1;
}
else {
result = list[mid];
==> why set result here
right = mid - 1;
}
}
return result;
} | m**s
发帖数: 61 | 17 char findNextChar(char[] list, int length, char target)
{
==>need error handling for list
[Agree]
// target is not within the list, just return the 1st char
if (target < list[0] || target > list[length - 1])
return list[0];
==> why return list[0] when target>
[题目要求的，for wrap case，return list中最小的character]
int left = 0, right = length - 1;
char result = list[0];
while (left < right) {
int mid = (left + right)/ 2;
==> overflow
[题目中说的是char array，不会overflow，不过我很喜欢你这个point]
if (list[mid] == target) {
return list[mid+1];
==>how about there are duplicate list[mid]
[题目中说的数组 "ascending order" 能否认为元素都是唯一的呢？]
}
else if (list[mid] < target) {
left = mid + 1;
}
else {
result = list[mid];
==> why set result here
[这里 list[mid] > target, 如果循环hit到这儿，继续更新result，越来越逼近最终
结果]
right = mid - 1;
}
}
return result;
} | l****s
发帖数: 75 | 18 //Linkedin: Return the smallest character that is strictly larger than the
search character
//http://www.careercup.com/question?id=5726366532108288
char findSmallestLargerChar(const vector & chars, char c)
{
if (chars.empty()) return ' | j*****n
发帖数: 23 | 19 貌似list = {'a','c'}, targe = 'b' 的时候不太对？
【在 m**s 的大作中提到】
: 第三个的原题 CC 上是这样描述的
: http://www.careercup.com/question?id=5726366532108288
: /**
: * Return the smallest character that is strictly larger than the search
: character,
: * If no such character exists, return the smallest character in the array
: * @param sortedStr : sorted list of letters, sorted in ascending order.
: * @param c : character for which we are searching.
: * Given the following inputs we expect the corresponding output:
: * ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'
| p*****2
发帖数: 21240 | 20
这样对吗？
char find2(char[] arr, char c){
assert(arr!=null && arr.length>0);
int s = 0, e = arr.length;
while(s
int mid=(s+e)/2;
if(arr[mid]<=c)
s=mid+1;
else
e=mid;
}
return e==arr.length?arr[0]:arr[e];
}
【在 m**s 的大作中提到】
: 第三个的原题 CC 上是这样描述的
: http://www.careercup.com/question?id=5726366532108288
: /**
: * Return the smallest character that is strictly larger than the search
: character,
: * If no such character exists, return the smallest character in the array
: * @param sortedStr : sorted list of letters, sorted in ascending order.
: * @param c : character for which we are searching.
: * Given the following inputs we expect the corresponding output:
: * ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'
| | | l*****a
发帖数: 14598 | 21 what is arr[0]
what will happen if there is no expect result in the array
这样对吗？
char find2(char[] arr, char c){
assert(arr!=null && arr.length>0);
int s = 0, e = arr.length;
while(s
int mid=(s+e)/2;
if(arr[mid]<=c)
s=mid+1;
else
e=mid;
}
return e==arr.length?arr[0]:arr[e];
} | p*****2
发帖数: 21240 | 22
给个例子？
【在 l*****a 的大作中提到】
: what is arr[0]
: what will happen if there is no expect result in the array
: 这样对吗？
: char find2(char[] arr, char c){
: assert(arr!=null && arr.length>0);
: int s = 0, e = arr.length;
: while(s: int mid=(s+e)/2;
: if(arr[mid]<=c)
: s=mid+1;
| l*****a
发帖数: 14598 | 23 ok,why use arr[0] when there is no expect result?
【在 p*****2 的大作中提到】
:
: 给个例子？
| y**********u
发帖数: 6366 | 24 I feel the result might be ambiguous in cases when all elements in arr are
larger than c and all elements in arr are smaller than c
【在 p*****2 的大作中提到】
:
: 给个例子？
| y**********u
发帖数: 6366 | 25 好难啊，去面肯定跪了。。。
",
【在 l****r 的大作中提到】
: 被recruiter 弄了连续面了2个组：
: 老印和中国人, 虽然国人不是主面试官，但是是不是的帮我一下，比如纠正我代码的
: bug，但是说得不明显
: 1。查找2个单词的距离
: /*
: * Example:
: * WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
: "quick", "brown", "fox", "quick"));
: * assert(finder.distance("fox","the") == 3);
: * assert(finder.distance("quick", "fox") == 1);
| y**********u
发帖数: 6366 | 26 这个语言很酷啊，二爷最近又在学什么语言啊？
array
【在 p*****2 的大作中提到】
:
: 给个例子？
| p*****2
发帖数: 21240 | 27 * If no such character exists, return the smallest character in the array
【在 l*****a 的大作中提到】
: ok,why use arr[0] when there is no expect result?
| l*****a
发帖数: 14598 | 28 传说中的c语言，你们小年轻估计都没用过把
【在 y**********u 的大作中提到】
: 这个语言很酷啊，二爷最近又在学什么语言啊？
:
: array
| d****3
发帖数: 123 | 29 请问第一题需要考虑输入的单词是同一个词语么？ 比如fox fox | j**********3
发帖数: 3211 | | | | p*********j
发帖数: 47 | 31 小弟写的代码，麻烦大牛们帮忙修改下，多谢！
public static char findNextChar(char[] list, char target) {
if (list == null || list.length == 0) {
return ' ';
}
// for wrap case，return list中最小的char
if (target < list[0] || target > list[list.length - 1]) {
return list[0];
}
int start = 0;
int end = list.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (list[mid] == target) {
return list[mid + 1];
} else if (list[mid] < target) {
start = mid;
} else {
end = mid;
}
}
/*
* start , end 和 target的三个相对位置
*
* (t) s____(t)_____e (t)
*/
if (list[start] > target) {
return list[start];
} else {
if (list[end] > target) {
return list[end];
} else {
return list[0];
}
}
} | l****r
发帖数: 689 | 32 被recruiter 弄了连续面了2个组：
老印和中国人, 虽然国人不是主面试官，但是是不是的帮我一下，比如纠正我代码的
bug，但是说得不明显
1。查找2个单词的距离
/*
* Example:
* WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
"quick", "brown", "fox", "quick"));
* assert(finder.distance("fox","the") == 3);
* assert(finder.distance("quick", "fox") == 1);
*/
2. 洗牌 要求in-place
第二面：老印和abc
中间abc一直没有吭声过。。。貌似这个题很常见，我另外2个朋友电面都碰到了，原题
，大家好好准备，其实不难，就是edge容易忽略
* Return the smallest character that is strictly larger than the search
character,
* ['c', 'f', 'j', 'p', 'v'], 'a' => 'c' | g***j
发帖数: 1275 | 33 第二题就是leetcode 里面的“Search Insert Position”吧
",
【在 l****r 的大作中提到】
: 被recruiter 弄了连续面了2个组：
: 老印和中国人, 虽然国人不是主面试官，但是是不是的帮我一下，比如纠正我代码的
: bug，但是说得不明显
: 1。查找2个单词的距离
: /*
: * Example:
: * WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
: "quick", "brown", "fox", "quick"));
: * assert(finder.distance("fox","the") == 3);
: * assert(finder.distance("quick", "fox") == 1);
| l*****a
发帖数: 14598 | 34 你背题太严重
至少LZ没告诉你输入数组有序
【在 g***j 的大作中提到】
: 第二题就是leetcode 里面的“Search Insert Position”吧
:
: ",
| g***j
发帖数: 1275 | 35 如果没排序的，就scan一遍，相当于找max，没有point，另外给的例子排序了。
【在 l*****a 的大作中提到】
: 你背题太严重
: 至少LZ没告诉你输入数组有序
| k****f
发帖数: 19 | 36 1。查找2个单词的距离
请问除了建立一个对dict所有单词的hash表，有没有别的办法可以有o(1)的效率啊 | j**********3
发帖数: 3211 | | t*******e
发帖数: 274 | 38 你这个距离是指每个单词在list中的距离？看你的例子，list中有两个'quick'，但返
回的是1，所以还要必须是最短距离？ | l****r
发帖数: 689 | 39 单词的
：你这个距离是指每个单词在list中的距离还是两个单词中字母间的距离，从你的例子
上我看不太明白？
： | l*****p
发帖数: 11 | 40 洗牌就是52张牌，打乱顺序吗？还是有别的条件？谢谢～～ | | | l****r
发帖数: 689 | 41 嗯，打乱顺序，最后要求证明，为什么概率是一样的
：洗牌就是52张牌，打乱顺序吗？还是有别的条件？谢谢～～ | j**********3
发帖数: 3211 | 42 怎么证明？
【在 l****r 的大作中提到】
: 嗯，打乱顺序，最后要求证明，为什么概率是一样的
:
: ：洗牌就是52张牌，打乱顺序吗？还是有别的条件？谢谢～～
| l*****a
发帖数: 14598 | 43 第一章52种可能
第二章51种
一共52!种,全排列
【在 j**********3 的大作中提到】
: 怎么证明？
| h*******e
发帖数: 1377 | | l****r
发帖数: 689 | | m**s
发帖数: 61 | 46 第三个的原题 CC 上是这样描述的
http://www.careercup.com/question?id=5726366532108288
/**
* Return the smallest character that is strictly larger than the search
character,
* If no such character exists, return the smallest character in the array
* @param sortedStr : sorted list of letters, sorted in ascending order.
* @param c : character for which we are searching.
* Given the following inputs we expect the corresponding output:
* ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'
* ['c', 'f', 'j', 'p', 'v'], 'c' => 'f'
* ['c', 'f', 'j', 'p', 'v'], 'k' => 'p'
* ['c', 'f', 'j', 'p', 'v'], 'z' => 'c' // The wrap around case
* ['c', 'f', 'k'], 'f' => 'k'
* ['c', 'f', 'k'], 'c' => 'f'
* ['c', 'f', 'k'], 'd' => 'f'
*/
我参照了CC上的Java的solution，用C改写了一下，length是数组的长度。
大牛们能给看看,找找毛病吗？
char findNextChar(char[] list, int length, char target)
{
// target is not within the list, just return the 1st char
if (target < list[0] || target > list[length - 1])
return list[0];
int left = 0, right = length - 1;
char result = list[0];
while (left < right) {
int mid = (left + right)/ 2;
if (list[mid] == target) {
return list[mid+1];
}
else if (list[mid] < target) {
left = mid + 1;
}
else {
result = list[mid];
right = mid - 1;
}
}
return result;
}
",
【在 l****r 的大作中提到】
: 被recruiter 弄了连续面了2个组：
: 老印和中国人, 虽然国人不是主面试官，但是是不是的帮我一下，比如纠正我代码的
: bug，但是说得不明显
: 1。查找2个单词的距离
: /*
: * Example:
: * WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
: "quick", "brown", "fox", "quick"));
: * assert(finder.distance("fox","the") == 3);
: * assert(finder.distance("quick", "fox") == 1);
| l*****a
发帖数: 14598 | 47 char findNextChar(char[] list, int length, char target)
{
==>need error handling for list
// target is not within the list, just return the 1st char
if (target < list[0] || target > list[length - 1])
return list[0];
==> why return list[0] when target>
int left = 0, right = length - 1;
char result = list[0];
while (left < right) {
int mid = (left + right)/ 2;
==> overflow
if (list[mid] == target) {
return list[mid+1];
==>how about there are duplicate list[mid]
}
else if (list[mid] < target) {
left = mid + 1;
}
else {
result = list[mid];
==> why set result here
right = mid - 1;
}
}
return result;
} | m**s
发帖数: 61 | 48 char findNextChar(char[] list, int length, char target)
{
==>need error handling for list
[Agree]
// target is not within the list, just return the 1st char
if (target < list[0] || target > list[length - 1])
return list[0];
==> why return list[0] when target>
[题目要求的，for wrap case，return list中最小的character]
int left = 0, right = length - 1;
char result = list[0];
while (left < right) {
int mid = (left + right)/ 2;
==> overflow
[题目中说的是char array，不会overflow，不过我很喜欢你这个point]
if (list[mid] == target) {
return list[mid+1];
==>how about there are duplicate list[mid]
[题目中说的数组 "ascending order" 能否认为元素都是唯一的呢？]
}
else if (list[mid] < target) {
left = mid + 1;
}
else {
result = list[mid];
==> why set result here
[这里 list[mid] > target, 如果循环hit到这儿，继续更新result，越来越逼近最终
结果]
right = mid - 1;
}
}
return result;
} | l****s
发帖数: 75 | 49 //Linkedin: Return the smallest character that is strictly larger than the
search character
//http://www.careercup.com/question?id=5726366532108288
char findSmallestLargerChar(const vector & chars, char c)
{
if (chars.empty()) return ' | j*****n
发帖数: 23 | 50 貌似list = {'a','c'}, targe = 'b' 的时候不太对？
【在 m**s 的大作中提到】
: 第三个的原题 CC 上是这样描述的
: http://www.careercup.com/question?id=5726366532108288
: /**
: * Return the smallest character that is strictly larger than the search
: character,
: * If no such character exists, return the smallest character in the array
: * @param sortedStr : sorted list of letters, sorted in ascending order.
: * @param c : character for which we are searching.
: * Given the following inputs we expect the corresponding output:
: * ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'
| | | p*****2
发帖数: 21240 | 51
这样对吗？
char find2(char[] arr, char c){
assert(arr!=null && arr.length>0);
int s = 0, e = arr.length;
while(s
int mid=(s+e)/2;
if(arr[mid]<=c)
s=mid+1;
else
e=mid;
}
return e==arr.length?arr[0]:arr[e];
}
【在 m**s 的大作中提到】
: 第三个的原题 CC 上是这样描述的
: http://www.careercup.com/question?id=5726366532108288
: /**
: * Return the smallest character that is strictly larger than the search
: character,
: * If no such character exists, return the smallest character in the array
: * @param sortedStr : sorted list of letters, sorted in ascending order.
: * @param c : character for which we are searching.
: * Given the following inputs we expect the corresponding output:
: * ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'
| l*****a
发帖数: 14598 | 52 what is arr[0]
what will happen if there is no expect result in the array
这样对吗？
char find2(char[] arr, char c){
assert(arr!=null && arr.length>0);
int s = 0, e = arr.length;
while(s
int mid=(s+e)/2;
if(arr[mid]<=c)
s=mid+1;
else
e=mid;
}
return e==arr.length?arr[0]:arr[e];
} | p*****2
发帖数: 21240 | 53
给个例子？
【在 l*****a 的大作中提到】
: what is arr[0]
: what will happen if there is no expect result in the array
: 这样对吗？
: char find2(char[] arr, char c){
: assert(arr!=null && arr.length>0);
: int s = 0, e = arr.length;
: while(s: int mid=(s+e)/2;
: if(arr[mid]<=c)
: s=mid+1;
| l*****a
发帖数: 14598 | 54 ok,why use arr[0] when there is no expect result?
【在 p*****2 的大作中提到】
:
: 给个例子？
| y**********u
发帖数: 6366 | 55 I feel the result might be ambiguous in cases when all elements in arr are
larger than c and all elements in arr are smaller than c
【在 p*****2 的大作中提到】
:
: 给个例子？
| y**********u
发帖数: 6366 | 56 好难啊，去面肯定跪了。。。
",
【在 l****r 的大作中提到】
: 被recruiter 弄了连续面了2个组：
: 老印和中国人, 虽然国人不是主面试官，但是是不是的帮我一下，比如纠正我代码的
: bug，但是说得不明显
: 1。查找2个单词的距离
: /*
: * Example:
: * WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
: "quick", "brown", "fox", "quick"));
: * assert(finder.distance("fox","the") == 3);
: * assert(finder.distance("quick", "fox") == 1);
| y**********u
发帖数: 6366 | 57 这个语言很酷啊，二爷最近又在学什么语言啊？
array
【在 p*****2 的大作中提到】
:
: 给个例子？
| p*****2
发帖数: 21240 | 58 * If no such character exists, return the smallest character in the array
【在 l*****a 的大作中提到】
: ok,why use arr[0] when there is no expect result?
| l*****a
发帖数: 14598 | 59 传说中的c语言，你们小年轻估计都没用过把
【在 y**********u 的大作中提到】
: 这个语言很酷啊，二爷最近又在学什么语言啊？
:
: array
| d****3
发帖数: 123 | 60 请问第一题需要考虑输入的单词是同一个词语么？ 比如fox fox | | | j**********3
发帖数: 3211 | | p*********j
发帖数: 47 | 62 小弟写的代码，麻烦大牛们帮忙修改下，多谢！
public static char findNextChar(char[] list, char target) {
if (list == null || list.length == 0) {
return ' ';
}
// for wrap case，return list中最小的char
if (target < list[0] || target > list[list.length - 1]) {
return list[0];
}
int start = 0;
int end = list.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (list[mid] == target) {
return list[mid + 1];
} else if (list[mid] < target) {
start = mid;
} else {
end = mid;
}
}
/*
* start , end 和 target的三个相对位置
*
* (t) s____(t)_____e (t)
*/
if (list[start] > target) {
return list[start];
} else {
if (list[end] > target) {
return list[end];
} else {
return list[0];
}
}
} | f**********t
发帖数: 1001 | 63 class FileIter {
ifstream _fin;
static const size_t kBufLen = 1024;
char _buf[kBufLen];
public:
FileIter(const char *fname) {
_fin.open(fname);
}
bool hasNext() {
return !_fin.eof();
}
string next() {
_fin.getline(_buf, kBufLen);
return string(_buf, _buf + _fin.gcount());
}
};
void FileIterTest() {
FileIter fi("iter.cpp");
while (fi.hasNext()) {
cout << fi.next() << endl;
}
} | f**********t
发帖数: 1001 | 64 void shuffle(vector &vi) {
for (size_t i = 0; i < vi.size(); ++i) {
size_t k = rand() % (vi.size() - i);
swap(vi[i], vi[i + k]);
}
for_each(vi.begin(), vi.end(), [](int x) {
cout << x << ' ';
});
cout << endl;
}
/*
* Example:
* WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the",
"quick", "brown", "fox", "quick"));
* assert(finder.distance("fox","the") == 3);
* assert(finder.distance("quick", "fox") == 1);
*/
class WordDistanceFinder {
vector _vs;
public:
WordDistanceFinder(vector vs) : _vs(move(vs)) {}
size_t distance(string s1, string s2) {
size_t dist = UINT_MAX;
size_t i = 0;
while (i < _vs.size() && _vs[i] != s1 && _vs[i] != s2) {
++i;
}
if (i == _vs.size()) {
return dist;
}
size_t left = i;
size_t right = i;
while (++i < _vs.size()) {
if (_vs[i] == s1 || _vs[i] == s2) {
if (_vs[i] == _vs[left] && s1 != s2) {
left = i;
} else {
right = i;
break;
}
}
}
if (left == right) {
return dist;
}
dist = right - left;
while (++i < _vs.size()) {
if (_vs[i] == _vs[left]) {
dist = min(dist, i - right);
left = right;
right = i;
} else if (_vs[i] == _vs[right]) {
right = i;
}
}
return dist;
}
};
void WordDistanceFinderTest() {
WordDistanceFinder finder({"the", "quick", "brown", "fox", "quick", "fox"}
);
assert(finder.distance("fox", "the") == 3);
assert(finder.distance("quick", "fox") == 1);
cout << finder.distance("fox", "fox") << ' ' << finder.distance("the", "
the")
<< ' ' << finder.distance("the", "fox") << ' ' <<
finder.distance("fox", "quick") << endl;
} | f**********t
发帖数: 1001 | 65 // * Return the smallest character that is strictly larger than the search
character, * ['c', 'f', 'j', 'p', 'v'], 'a' => 'c'
char MinLarger(string s, char c) {
if (s.empty()) {
throw - 1;
}
size_t l = 0;
size_t r = s.size();
while (l < r) {
size_t m = (l + r) / 2;
if (c < s[m]) {
r = m;
} else {
l = m + 1;
}
}
if (l == s.size()) {
throw - 1;
} else {
return s[l];
}
}
void MinLargerTest() {
try {
cout << MinLarger("abcd", 'b') << ' ' << MinLarger("bb", 'a') << ' '
<< MinLarger("cfjpv", 'a') << ' ' << MinLarger("cfjpv", 'z') <<
endl;
} catch (int x) {
cout << x << endl;
}
} | p******e
发帖数: 14 | | c****8
发帖数: 76 | | w****a
发帖数: 710 | | c******t
发帖数: 391 | 69 找插入index感觉很像LC上找range那道题，如果照着findRightMostPosition的写法，
在算mid的时候取ceil就可以了，比如{a,b,c,c,c,d},二分查找c的结果是4，所以返回4
+1=5. 之前首尾大小判断一下，就能保证不overflow。
求拍 ^^
public static char findNextChar(char[] arr, char k){
int len = arr.length;
if(len==0) return ' '; //not sure if needed
if(k >= arr[len-1] || k < arr[0]) return arr[0];
int i = 0;
int j = len-1;
while( i < j){
int m = i+(j-i)/2+1; //get the *ceil* index of mid value in case
there are dups
if(arr[m] > k) j = m-1;
else i = m;
}
return arr[i+1];
} |
|
