phynix 封 happyfe 在 Money 版 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

phynix 封 happyfe 在 Money 版

phynix 封 happyfe 在 Money 版# Money - 海外理财

i*s2012-02-11 08:02

1 楼

前几天同学google电面回来，遇到两道题，想跟大家讨论一下。ps: 后天本人也要电面
了，求祝福～
题：
1. 给你一组排序好的double类型的数组，怎样求出某个数出现的次数。
2. 给你一个dictionary, 里面存着n个字符串，再给你一个字符串，请问有多少种方法
划分这个字符串，使得每个字符串都在dictionary中。

p*x2012-02-11 08:02

2 楼

【以下文字转载自 Notice 讨论区】
发信人: deliver (自动发信系统), 信区:
标题: phynix 封 happyfe 在 Money 版
发信站: BBS 未名空间站自动发信系统 (Fri Feb 10 23:47:11 2012)
【此篇文章是由自动发信系统所张贴】
由于 happyfe 在 Money 版的滥发广告行为，
被暂时取消在本版的发文权力 14 天。
版主:phynix
Fri Feb 10 23:47:08 2012

f*g2012-02-11 08:02

3 楼

1. 有Binary Search可以找到元素第一次出现的位置。
以当前位置为始，再做找元素出现最后一次的位置的Binary Search
如果这个数量不多，就Linear。
只是有一点不明白，为什么要double，这是要考什么呢？
不能直接==？

i*s2012-02-11 08:02

4 楼

可能是想考察比较double时不能直接用==吧，要用一个误差e来比较两个数，比如(a-b)
< e之类的。还有用binary search一次不能保证找到的一定是第一次出现的位置吧，
还是得要找多次，求分析

【在 f***g 的大作中提到】

: 1. 有Binary Search可以找到元素第一次出现的位置。
: 以当前位置为始，再做找元素出现最后一次的位置的Binary Search
: 如果这个数量不多，就Linear。
: 只是有一点不明白，为什么要double，这是要考什么呢？
: 不能直接==？

P*l2012-02-11 08:02

5 楼

bless!
1. binary search for a range.
Remember to use the previous result.
2. I think it is correct to use DP. But your method will count result
multiple times.
example:
dictionary : aaa, bb, cc, aaabb, bbcc.
word: aaa, bb, cc.

V*i2012-02-11 08:02

6 楼

For the first one, do three binary searches. My code as follows. It is easy
to combine three binary searches into one routines through a flag, I wrote
this way for clearance.
int binary_search(int* num, int left, int right, int K) {
// find any pos such that num[pos] == K
if (left > right) return -1;
int mid = (left+right)/2;
if (K == num[mid]) return mid;
if (K < num[mid]) return binary_search(num, left, mid-1, K);
else return binary_search(num, mid+1, right, K);
}
int binary_search_l(int* num, int left, int right, int K) {
// find pos such that num[pos] < K && num[pos+1] == K
if (left > right) return -1;
int mid = (left+right)/2;
if (K == num[mid+1] && K > num[mid]) return mid;
if (K == num[mid]) return binary_search_l(num, left, mid-1, K);
else return binary_search_l(num, mid+1, right, K);
}
int binary_search_r(int* num, int left, int right, int K) {
// find pos such that num[pos] == K && num[pos+1] > K
if (left > right) return -1;
int mid = (left+right)/2;
if (K == num[mid-1] && K < num[mid]) return mid;
if (K == num[mid]) return binary_search_r(num, mid+1, right, K);
else return binary_search_r(num, left, mid-1, K);
}
int find_K(int* num, int N, int K) {
int pos = binary_search(num, 0, N-1, K);
int left_bound, right_bound;
if (pos == 0) left_bound = 0;
else left_bound = binary_search_l(num, 0, pos-1, K);
if (pos == N-1) right_bound = N-1;
else right_bound = binary_search_r(num, pos+1, N-1, K);
return right_bound-1-(left_bound+1)+1;
}

binary
worse

【在 i******s 的大作中提到】

: 前几天同学google电面回来，遇到两道题，想跟大家讨论一下。ps: 后天本人也要电面
: 了，求祝福～
: 题：
: 1. 给你一组排序好的double类型的数组，怎样求出某个数出现的次数。
: 2. 给你一个dictionary, 里面存着n个字符串，再给你一个字符串，请问有多少种方法
: 划分这个字符串，使得每个字符串都在dictionary中。

j*a2012-02-11 08:02

7 楼

第二题看不懂...能讲讲啥意思马？
楼上为啥3次binary search阿？？ Don't get what's going on...

f*g2012-02-11 08:02

8 楼

没有试验，但是觉得两次就够了

V*i2012-02-11 08:02

9 楼

For the second problem, it is correct to use DP.
But I think the correct formula should be T(n) = \sum_{i=1}^(n-1)(T(i)*H(i+1
, n)), here T(n) the number of partitions for string (1,n), H(i+1, n) if 1
of string (i+1, n) is in dict and 0 if string (i+1, n) is not.

binary
worse

【在 i******s 的大作中提到】

i*s2012-02-11 08:02

10 楼

你的解法应该是对的，基于这个写了如下C++代码
/*
* Author: Shengzhe Yao
* Date: 08 Nov 2010
*/
#include
#include
#include
#include
using namespace std;
// T(n) = \sum_{i=1}^{n-1} (T(i) * H(i+1))
int findAllStr(const set &dict, char *str,
int end, int *lookup_table) {
if (lookup_table[end] > 0)
return lookup_table[end];
int total = 0;
for (int i=1; i < end; ++i) {
char *substr = (str+i+1);

if (dict.find(substr) != dict.end()) {
char tmp = str[i+1];
str[i+1] = '\0'; // To use default set comparator
if (dict.find(str) != dict.end()) {
// calculate all split ways between position 0 to i
total= findAllStr(dict, str, i, lookup_table);
}
str[i+1] = tmp;
}
}

if ((dict.find(str) != dict.end())) {
++total;
}
lookup_table[end] = total;
return total;
}
int main(int argc, char *argv[]) {
set dict;
dict.insert("a");
dict.insert("aa");
dict.insert("aaa");
dict.insert("aaaa");

char str[] = "aaaa";
int lookup_table[100];
for (int i=0; i < 100; ++i)
lookup_table[i] = -1;
printf("Total combination is: %d\n",
findAllStr(dict, str, strlen(str), lookup_table));
for (int i=0; i < 10; ++i)
printf("%d, ", lookup_table[i]);
printf("\n");
return 0;
}

s*n2012-02-11 08:02

11 楼

can you write a bp program? really hard to me.
looks to me just a bfs or DFS searching with dictionary graph is enough. use
a static/global counter to count when you reach the end of the target
string.
foreach string S in D
{
if S prefix match T && T-S > null
recursively call on T - S, D
if T-s is null,
count++;
}
of caz, a trie or prefix tree can speed up the searching.

+1

【在 V*****i 的大作中提到】

: For the second problem, it is correct to use DP.
: But I think the correct formula should be T(n) = \sum_{i=1}^(n-1)(T(i)*H(i+1
: , n)), here T(n) the number of partitions for string (1,n), H(i+1, n) if 1
: of string (i+1, n) is in dict and 0 if string (i+1, n) is not.
:
: binary
: worse

j*a2012-02-11 08:02

12 楼

能解释一下第二题是什么意思吗？看不懂？

binary
worse

【在 i******s 的大作中提到】

i*s2012-02-11 08:02

13 楼

Thanks for pointing out the mistake !

【在 P********l 的大作中提到】

: bless!
: 1. binary search for a range.
: Remember to use the previous result.
: 2. I think it is correct to use DP. But your method will count result
: multiple times.
: example:
: dictionary : aaa, bb, cc, aaabb, bbcc.
: word: aaa, bb, cc.

i*s2012-02-11 08:02

14 楼

就是有一个字典dict，里面有若干字符串。现在输入一个字符串str, 将str分成若干个
子串，要求每个子串都在dict中，问这样的切分方法有几种？

【在 j****a 的大作中提到】

: 能解释一下第二题是什么意思吗？看不懂？
:
: binary
: worse

j*u2012-02-11 08:02

15 楼

1. two binary search
2. 可否用prefix tree？
for (int i = 0; i < str.lengh, ++i)
{
match str[i..k1], [k1+1..k2]...in prefix-tree until str.length-1,
continue if any match fails;
++count;
}

binary
worse

【在 i******s 的大作中提到】

r*u2012-02-11 08:02

16 楼

第二题，你的递归公式，把str分成A，B俩部分后，A继续会被划分，所以有重复。
end是str结尾的position，
F(i)是从i到end的划分个数，那么
F(i) = sum_{k = 1 to end-i} | F(i+k), if str[i, i+k-1] is a valid word.
| 0. Otherwise
对每个A，which is a valid word，划分B，然后加一起.

binary
worse

【在 i******s 的大作中提到】

V*i2012-02-11 08:02

17 楼

There is no need to pass Dictionary and lookup table, use global variable or
use class. My solution as follows:
#include
#include
#include
#include
using namespace std;
// T(n) = \sum_{i=1}^{n-1} (T(i) * H(i+1))
const int MAXSIZE = 100;
class find_str {
private:
set dict;
int lookup_table[MAXSIZE];
public:
find_str(set &d) {
dict = d;
for (int i=0; i}
int findAllStr(const string &str, int pos) {
if (lookup_table[pos] != -1)
return lookup_table[pos];
int total = 0;
for (size_t i=1; i <= pos; ++i) {
string substr = str.substr(i, pos-i+1);
if (dict.find(substr) != dict.end())
total += findAllStr(str, i-1);
}
if (dict.find(str.substr(0, pos+1)) != dict.end()) ++total;
lookup_table[pos] = total;
return total;
}
};
int main(int argc, char *argv[]) {
set dict;
dict.insert("aaa");
dict.insert("bb");
dict.insert("cc");
dict.insert("aaabb");
dict.insert("bbcc");
find_str f(dict);
string str = "aaabbcc";
printf("Total combination is: %d\n", f.findAllStr(str, str.length()-
1));
return 0;
}
【
在 ipodfans (jojo) 的大作中提到: 】

b*n2012-02-11 08:02

18 楼

第一题可以参考std::equal_range()的实现
就是套用std::lower_bound()和std::upper_bound()

A*H2012-02-11 08:02

19 楼

#q2
#include
#include
using namespace std;
int partition_count(map dict, string words) {
int count = 0;
if (dict[words])
count++;

for (int i=1, n=words.size(); iif (dict[words.substr(0, i)])
count += partition_count(dict, words.substr(i, n-i));
}
return count;
}
int main() {
map dict;
dict["aaa"] = true;
dict["bb"] = true;
dict["cc"] = true;
dict["aaabb"] = true;
dict["bbcc"] = true;
string words = "aaabbcc";
cout<< partition_count(dict, words) << endl;
return 1;
}