G********r
发帖数: 9 | 1 比较久之前T家的面试,结果就不共享了,只贡献题目，可能给面Machine Learning方向
的有些帮助。
电面1.
（1）一些统计的问题，二项分布，大数定理，抛硬币做概率转换
(2) （写程序）用stack实现queue
电面2.
（1） Trending tweats的算法设计；tweat topic的提取；
（2）（写程序）输入一个程序源文件，写一个程序去掉所以有的comment
Onsite:
(1). （a）(写程序)两个字符串的最大公共字串
（b （puzzle）game: the interviewee is an oracle of a function "bool f(
int, int, int)", that is, the interviewer can provide three numbers as input
, then the interviewee can give the TRUE/FALSE answer. Play the game and
find the precise definition for the function.
(2). (a) some fundamental concept for machine learning (precision, recall,
ROC curve)
(b)(写程序)爬楼梯的题，valid single-step move is 2^k (always starting
from the first floor). Given a target floor n, output the best strategy to
reach it.
(3). (a) some system design question regarding news feed
（b）(写程序)reservoir sampling
(4). (a) (写程序)coding multiplication of 2 matrix
(b) (写程序)coding multiplication of a list of matrix
(5). （讨论）new feature to Twitter; trending design (again), some related
statistical model; linear regression 101; recursively use 1-feature linear
regression and the complexity discussion.
(6). （讨论）Machine Learning feature engineering for Twitter Ads; formula
and implementation of boost tree machine learning method; how to use
parallel computing to speed up training process; some discussion on
convergence speed. |
c********t
发帖数: 5706 | 2 赞！多谢分享！
Onsite:
(1). （a）(写程序)两个字符串的最大公共字串
需要优化的算法吗？还是brute force就可以？
（b （puzzle）game: the interviewee is an oracle of a function "bool f(
int, int, int)", that is, the interviewer can provide three numbers as input
, then the interviewee can give the TRUE/FALSE answer. Play the game and
find the precise definition for the function.
不会做啊，试很多很多triple,然后找规律？
(b)(写程序)爬楼梯的题，valid single-step move is 2^k (always starting
from the first floor). Given a target floor n, output the best strategy to
reach it.
是用二进制，算吗？比如 5=101= 2^0+2^2 |
z***e
发帖数: 209 | |
d*****y
发帖数: 1365 | 4 爬楼梯: 比如23楼,你可以先到8楼,再到7楼,再到23楼,只要三次,用二进制表示的话要4
次.
f(
input
【在 c********t 的大作中提到】
: 赞！多谢分享！
: Onsite:
: (1). （a）(写程序)两个字符串的最大公共字串
: 需要优化的算法吗？还是brute force就可以？
: （b （puzzle）game: the interviewee is an oracle of a function "bool f(
: int, int, int)", that is, the interviewer can provide three numbers as input
: , then the interviewee can give the TRUE/FALSE answer. Play the game and
: find the precise definition for the function.
: 不会做啊，试很多很多triple,然后找规律？
: (b)(写程序)爬楼梯的题，valid single-step move is 2^k (always starting
|
c********t
发帖数: 5706 | 5 哦，原来如此. 我做做试试。
要4
【在 d*****y 的大作中提到】
: 爬楼梯: 比如23楼,你可以先到8楼,再到7楼,再到23楼,只要三次,用二进制表示的话要4
: 次.
:
: f(
: input
|
c********t
发帖数: 5706 | 6 先弄了个recursion的，DP应该效率更好。
public int step(int n) {
if (n < 1)
return 0;
if (isPow(n))
return 1;
int count = 0, m=n;
while (m > 0) {
m /= 2;
count++;
}
return Math.min(1 + step(n - (int) Math.pow(2, count - 1)),
1 + step((int) Math.pow(2, count) - n));
}
boolean isPow(int n) {
while (n % 2 == 0)
n /= 2;
return n == 1;
}
要4
【在 d*****y 的大作中提到】
: 爬楼梯: 比如23楼,你可以先到8楼,再到7楼,再到23楼,只要三次,用二进制表示的话要4
: 次.
:
: f(
: input
|
d*****y
发帖数: 1365 | 7 我觉得这题应该用BFS
)-
【在 c********t 的大作中提到】
: 先弄了个recursion的，DP应该效率更好。
: public int step(int n) {
: if (n < 1)
: return 0;
: if (isPow(n))
: return 1;
: int count = 0, m=n;
: while (m > 0) {
: m /= 2;
: count++;
|
c********t
发帖数: 5706 | 8 下楼呢？可以往右或往上走？
【在 d*****y 的大作中提到】
: 我觉得这题应该用BFS
:
: )-
|
d*****y
发帖数: 1365 | 9 我说错了,其实BFS就行了.如果a = b + 2^k or a = b-2^k,这两点之间有一个edge,按
照这个关系可以建一个graph
其实还要考虑这个target是不是在最顶楼,如果不在最顶楼,还有可能爬到顶楼再爬下来.
【在 c********t 的大作中提到】
: 下楼呢？可以往右或往上走？
|
c********t
发帖数: 5706 | 10 你写一个BFS的吧。我用DFS做的。
还有顶楼条件啊，就当无限高吧。
来.
【在 d*****y 的大作中提到】
: 我说错了,其实BFS就行了.如果a = b + 2^k or a = b-2^k,这两点之间有一个edge,按
: 照这个关系可以建一个graph
: 其实还要考虑这个target是不是在最顶楼,如果不在最顶楼,还有可能爬到顶楼再爬下来.
|
|
|
G********r
发帖数: 9 | 11
brute force应该不行吧，我直接写了suffix tree的solution。
f(
input
是的，最后的解好像是如果a
【在 c********t 的大作中提到】
: 赞！多谢分享！
: Onsite:
: (1). （a）(写程序)两个字符串的最大公共字串
: 需要优化的算法吗？还是brute force就可以？
: （b （puzzle）game: the interviewee is an oracle of a function "bool f(
: int, int, int)", that is, the interviewer can provide three numbers as input
: , then the interviewee can give the TRUE/FALSE answer. Play the game and
: find the precise definition for the function.
: 不会做啊，试很多很多triple,然后找规律？
: (b)(写程序)爬楼梯的题，valid single-step move is 2^k (always starting
|
c********t
发帖数: 5706 | 12 好佩服能当场写suffix tree的，我猜你已经是Ter了。
function可以对 a b c，做各种运算，比较。a
出吧。
【在 G********r 的大作中提到】
:
: brute force应该不行吧，我直接写了suffix tree的solution。
: f(
: input
: 是的，最后的解好像是如果a
|
w****x
发帖数: 2483 | 13
这个对吗？？
【在 c********t 的大作中提到】
: 先弄了个recursion的，DP应该效率更好。
: public int step(int n) {
: if (n < 1)
: return 0;
: if (isPow(n))
: return 1;
: int count = 0, m=n;
: while (m > 0) {
: m /= 2;
: count++;
|
w****x
发帖数: 2483 | 14
BFS??
这个不是搜索，是最短路径吧， dijikstra
【在 d*****y 的大作中提到】
: 我觉得这题应该用BFS
:
: )-
|
w****x
发帖数: 2483 | 15 vector getJumpSteps(int nCur, int nMaxStep)
{
vector vec;
if (nCur <= 0 || nMaxStep < nCur)
return vec;
int flg = 1;
while (nCur + flg <= nMaxStep)
{
vec.push_back(nCur + flg);
flg = (flg << 1);
}
flg = 1;
while (nCur - flg > 0)
{
vec.push_back(nCur - flg);
flg = (flg << 1);
}
return vec;
}
int getMinStep(int n, int nMaxStep)
{
if (n <= 0 || nMaxStep < n)
return -1;
int* rec = new int[nMaxStep+1];
for (int i = 0; i <= nMaxStep; i++)
rec[i] = -1;
queue que;
que.push(1);
rec[1] = 0;
while (!que.empty())
{
int nCur = que.front();
que.pop();
vector vec = getJumpSteps(nCur, nMaxStep);
for (int i = 0; i < vec.size(); i++)
{
int des = vec[i];
if (rec[des] < 0 || rec[des] > rec[nCur] + 1)
{
rec[des] = rec[nCur] + 1;
que.push(des);
}
}
}
int nRet = rec[n];
delete[] rec;
return nRet;
} |
p*****2
发帖数: 21240 | 16
大牛咋还没转java呢？
【在 w****x 的大作中提到】
: vector getJumpSteps(int nCur, int nMaxStep)
: {
: vector vec;
: if (nCur <= 0 || nMaxStep < nCur)
: return vec;
: int flg = 1;
: while (nCur + flg <= nMaxStep)
: {
: vec.push_back(nCur + flg);
: flg = (flg << 1);
|
w****x
发帖数: 2483 | 17
工程是VC的
【在 p*****2 的大作中提到】
:
: 大牛咋还没转java呢？
|
p*****2
发帖数: 21240 | 18
你这是做的第几题？
【在 w****x 的大作中提到】
:
: 工程是VC的
|
w****x
发帖数: 2483 | 19
第213题
【在 p*****2 的大作中提到】
:
: 你这是做的第几题？
|
p*****2
发帖数: 21240 | 20
我是说上边第几题？我想看看。
【在 w****x 的大作中提到】
:
: 第213题
|
|
|
w****x
发帖数: 2483 | 21
爬楼梯那题，这题出的很有水平！
【在 p*****2 的大作中提到】
:
: 我是说上边第几题？我想看看。
|
p*****2
发帖数: 21240 | 22
这题DP不行吗？
【在 c********t 的大作中提到】
: 好佩服能当场写suffix tree的，我猜你已经是Ter了。
: function可以对 a b c，做各种运算，比较。a: 出吧。
|
w****x
发帖数: 2483 | 23
dijkstra就算DP啊
【在 p*****2 的大作中提到】
:
: 这题DP不行吗？
|
p*****2
发帖数: 21240 | 24
就是BFS吧。扫到0就可以了。
【在 w****x 的大作中提到】
:
: dijkstra就算DP啊
|
p*****2
发帖数: 21240 | 25
我说的suffix tree那题。
【在 w****x 的大作中提到】
:
: dijkstra就算DP啊
|
p*****2
发帖数: 21240 | 26
来.
就是BFS
【在 d*****y 的大作中提到】
: 我说错了,其实BFS就行了.如果a = b + 2^k or a = b-2^k,这两点之间有一个edge,按
: 照这个关系可以建一个graph
: 其实还要考虑这个target是不是在最顶楼,如果不在最顶楼,还有可能爬到顶楼再爬下来.
|
d**********x
发帖数: 4083 | 27 我感觉还是用二进制。但是是把n拆成a - b的形式
首先要证明的是，不需要有两次重复的相同的k，因为可以用一次k+1替换，然后类推。
然后我们要得到的是a和b中的"1"尽量少。我的想法是，对于a中每串连续的、超过1位
的1，将其换成10..00 - 1的形式。
这样，对于23 = 10111 = 11000 - 1 = 100000 - 1001，是三次
但是要考虑转化后再成为连续的1的问题，举例：
110111 = 111000 - 1 = 1000000 - 1001
110111 = 1001000 - 10001，是多了一次的
所以需要从低位开始处理，逐串转化。
大家帮我看看这个想法有没有问题吧。
要4
bool
【在 d*****y 的大作中提到】
: 爬楼梯: 比如23楼,你可以先到8楼,再到7楼,再到23楼,只要三次,用二进制表示的话要4
: 次.
:
: f(
: input
|
p*****2
发帖数: 21240 | 28 def solve(n:Int):Int={
val isPow=(n:Int)=>{var m=n;while(m%2==0) m/=2;m==1}
val visited=new Array[Boolean](n+1)
val queue=new Queue[Int]
queue+=n
visited(n)=true
var count=1
var distance=0
while(!queue.isEmpty){
while(count>0){
val curr=queue.dequeue
if(curr==0) return distance
for(i<-0 until n if !visited(i) && isPow((curr-i).abs)){
queue+=i
visited(i)=true
}
count-=1
}
count=queue.length
distance+=1
}
-1
} |
a***o
发帖数: 1182 | 29 二爷介绍一下算法?
DFS不行吗?
【在 p*****2 的大作中提到】
: def solve(n:Int):Int={
: val isPow=(n:Int)=>{var m=n;while(m%2==0) m/=2;m==1}
: val visited=new Array[Boolean](n+1)
: val queue=new Queue[Int]
: queue+=n
: visited(n)=true
: var count=1
: var distance=0
:
: while(!queue.isEmpty){
|
p*****2
发帖数: 21240 | 30
DFS也可以。不过效率没有BFS高而已。
【在 a***o 的大作中提到】
: 二爷介绍一下算法?
: DFS不行吗?
|
|
|
d**********x
发帖数: 4083 | 31 应该没问题，和coldknight的程序在2-10000之内做了对比，结果完全一致。他的
nMaxStep我设置为了2 * target，不知道会不会引起问题。
在纸面上也做了不太严格的证明。。这样复杂度就是O(logn)。
对比程序：（前半部分还是coldknight的）
#include
#include
#include
using namespace std;
vector getJumpSteps(int nCur, int nMaxStep)
{
vector vec;
if (nCur <= 0 || nMaxStep < nCur)
return vec;
int flg = 1;
while (nCur + flg <= nMaxStep)
{
vec.push_back(nCur + flg);
flg = (flg << 1);
}
flg = 1;
while (nCur - flg > 0)
{
vec.push_back(nCur - flg);
flg = (flg << 1);
}
return vec;
}
int getMinStep(int n, int nMaxStep)
{
if (n <= 0 || nMaxStep < n)
return -1;
int* rec = new int[nMaxStep+1];
for (int i = 0; i <= nMaxStep; i++)
rec[i] = -1;
queue que;
que.push(1);
rec[1] = 0;
while (!que.empty())
{
int nCur = que.front();
que.pop();
vector vec = getJumpSteps(nCur, nMaxStep);
for (int i = 0; i < vec.size(); i++)
{
int des = vec[i];
if (rec[des] < 0 || rec[des] > rec[nCur] + 1)
{
rec[des] = rec[nCur] + 1;
que.push(des);
}
}
}
int nRet = rec[n];
delete[] rec;
return nRet;
}
int getMinSteps(int target) {
if (target <= 0) {
return -1;
}
target--;
int steps = 0;
int cont_ones = 0;
while(target > 0) {
int lsb = target & 1;
target >>= 1;
if (lsb == 0) {
if (cont_ones <= 1) {
steps += cont_ones;
cont_ones = 0;
} else {
steps += 1;
cont_ones = 1;
}
} else {
cont_ones++;
}
}
if (cont_ones > 1) {
steps += 2;
} else {
steps += cont_ones;
}
return steps;
}
int main() {
int same = 0;
int diff = 0;
for (int i = 2; i < 10000; ++i) {
if (getMinStep(i, i * 2) == getMinSteps(i)) {
same++;
} else {
diff++;
cout << "diff: " << i << endl;
}
}
cout << "same: " << same << " diff: " << diff << endl;
return 0;
}
【在 d**********x 的大作中提到】
: 我感觉还是用二进制。但是是把n拆成a - b的形式
: 首先要证明的是，不需要有两次重复的相同的k，因为可以用一次k+1替换，然后类推。
: 然后我们要得到的是a和b中的"1"尽量少。我的想法是，对于a中每串连续的、超过1位
: 的1，将其换成10..00 - 1的形式。
: 这样，对于23 = 10111 = 11000 - 1 = 100000 - 1001，是三次
: 但是要考虑转化后再成为连续的1的问题，举例：
: 110111 = 111000 - 1 = 1000000 - 1001
: 110111 = 1001000 - 10001，是多了一次的
: 所以需要从低位开始处理，逐串转化。
: 大家帮我看看这个想法有没有问题吧。
|
w****x
发帖数: 2483 | 32
哪家快一些？
【在 d**********x 的大作中提到】
: 应该没问题，和coldknight的程序在2-10000之内做了对比，结果完全一致。他的
: nMaxStep我设置为了2 * target，不知道会不会引起问题。
: 在纸面上也做了不太严格的证明。。这样复杂度就是O(logn)。
: 对比程序：（前半部分还是coldknight的）
: #include
: #include
: #include
: using namespace std;
: vector getJumpSteps(int nCur, int nMaxStep)
: {
|
d**********x
发帖数: 4083 | 33 你猜。。
我只要扫描一遍数字的binary表示。
【在 w****x 的大作中提到】
:
: 哪家快一些？
|
a***o
发帖数: 1182 | 34 如果没给nMaxStep, BFS就做不了了吧?
怎么证明nMaxStep <= 2*target?
【在 d**********x 的大作中提到】
: 应该没问题，和coldknight的程序在2-10000之内做了对比，结果完全一致。他的
: nMaxStep我设置为了2 * target，不知道会不会引起问题。
: 在纸面上也做了不太严格的证明。。这样复杂度就是O(logn)。
: 对比程序：（前半部分还是coldknight的）
: #include
: #include
: #include
: using namespace std;
: vector getJumpSteps(int nCur, int nMaxStep)
: {
|
d**********x
发帖数: 4083 | 35 我是从我那个算法的角度考虑得到的2*target。。。
严格证明还是挺头疼的，我再想想。
【在 a***o 的大作中提到】
: 如果没给nMaxStep, BFS就做不了了吧?
: 怎么证明nMaxStep <= 2*target?
|
a***o
发帖数: 1182 | 36 恩,扫一遍那个比较好理解
【在 d**********x 的大作中提到】
: 我是从我那个算法的角度考虑得到的2*target。。。
: 严格证明还是挺头疼的，我再想想。
|
c***s
发帖数: 192 | 37 我觉得是对的，有一个Non-adjacent form（NAF）的东西就是这个题目的答案。
http://en.wikipedia.org/wiki/Non-adjacent_form#cite_ref-gecc_1-
所以这个题的复杂度O(logN).
【在 d**********x 的大作中提到】
: 我感觉还是用二进制。但是是把n拆成a - b的形式
: 首先要证明的是，不需要有两次重复的相同的k，因为可以用一次k+1替换，然后类推。
: 然后我们要得到的是a和b中的"1"尽量少。我的想法是，对于a中每串连续的、超过1位
: 的1，将其换成10..00 - 1的形式。
: 这样，对于23 = 10111 = 11000 - 1 = 100000 - 1001，是三次
: 但是要考虑转化后再成为连续的1的问题，举例：
: 110111 = 111000 - 1 = 1000000 - 1001
: 110111 = 1001000 - 10001，是多了一次的
: 所以需要从低位开始处理，逐串转化。
: 大家帮我看看这个想法有没有问题吧。
|
d**********x
发帖数: 4083 | 38 Orz...
【在 c***s 的大作中提到】
: 我觉得是对的，有一个Non-adjacent form（NAF）的东西就是这个题目的答案。
: http://en.wikipedia.org/wiki/Non-adjacent_form#cite_ref-gecc_1-
: 所以这个题的复杂度O(logN).
|
w****x
发帖数: 2483 | 39
我靠，这个思路太强了，大牛以前做竞赛的？
【在 d**********x 的大作中提到】
: 我感觉还是用二进制。但是是把n拆成a - b的形式
: 首先要证明的是，不需要有两次重复的相同的k，因为可以用一次k+1替换，然后类推。
: 然后我们要得到的是a和b中的"1"尽量少。我的想法是，对于a中每串连续的、超过1位
: 的1，将其换成10..00 - 1的形式。
: 这样，对于23 = 10111 = 11000 - 1 = 100000 - 1001，是三次
: 但是要考虑转化后再成为连续的1的问题，举例：
: 110111 = 111000 - 1 = 1000000 - 1001
: 110111 = 1001000 - 10001，是多了一次的
: 所以需要从低位开始处理，逐串转化。
: 大家帮我看看这个想法有没有问题吧。
|
p*****2
发帖数: 21240 | 40
他初中就玩电脑了，高中就竞赛了。世界级水平。
【在 w****x 的大作中提到】
:
: 我靠，这个思路太强了，大牛以前做竞赛的？
|
|
|
d**********x
发帖数: 4083 | 41 没搞过。。。思路跳跃了一下而已。。
经常会跳错。。。
【在 w****x 的大作中提到】
:
: 我靠，这个思路太强了，大牛以前做竞赛的？
|
f*****e
发帖数: 2992 | 42 我都想到了，关键是有没有严格的proof啊？
【在 w****x 的大作中提到】
:
: 我靠，这个思路太强了，大牛以前做竞赛的？
|
p*****2
发帖数: 21240 | 43
你也是大牛呀。
【在 f*****e 的大作中提到】
: 我都想到了，关键是有没有严格的proof啊？
|
d**********x
发帖数: 4083 | 44 看上面那位给出的NAF，再找找相关的定理之类，我觉得靠谱
【在 f*****e 的大作中提到】
: 我都想到了，关键是有没有严格的proof啊？
|
f*****e
发帖数: 2992 | 45 过奖了，我也是看了前面的讨论才想到的。
【在 p*****2 的大作中提到】
:
: 你也是大牛呀。
|
p*****2
发帖数: 21240 | 46
这样呀。我没看讨论，直接看题想到BFS
【在 f*****e 的大作中提到】
: 过奖了，我也是看了前面的讨论才想到的。
|
w****x
发帖数: 2483 | 47
丢人了，BFS都没想到
【在 p*****2 的大作中提到】
:
: 这样呀。我没看讨论，直接看题想到BFS
|
p*****2
发帖数: 21240 | 48
你是什么算法？dijstra吗？也差不多。
【在 w****x 的大作中提到】
:
: 丢人了，BFS都没想到
|
w****x
发帖数: 2483 | 49
哎呀，我基础太差了，dijkstra是在权重不一样的情况下用的，BFS就可以了，丢死人
了
【在 p*****2 的大作中提到】
:
: 你是什么算法？dijstra吗？也差不多。
|
p*****2
发帖数: 21240 | 50
是这样的。
【在 w****x 的大作中提到】
:
: 哎呀，我基础太差了，dijkstra是在权重不一样的情况下用的，BFS就可以了，丢死人
: 了
|
|
|
c********t
发帖数: 5706 | 51 DP可以做(写程序)两个字符串的最大公共字串。我觉得比写suffix tree容易些。
【在 p*****2 的大作中提到】
:
: 是这样的。
|
h*******e
发帖数: 1377 | 52 suffix tree大概多少行啊，从来没写过。 suffix array有大约25行如果背还好背点
。
【在 c********t 的大作中提到】
: DP可以做(写程序)两个字符串的最大公共字串。我觉得比写suffix tree容易些。
|
p*****2
发帖数: 21240 | 53
感觉面试用DP更好。
【在 c********t 的大作中提到】
: DP可以做(写程序)两个字符串的最大公共字串。我觉得比写suffix tree容易些。
|
f*****e
发帖数: 2992 | 54 suffix tree能做出来吗？那个是连续的吧？
【在 c********t 的大作中提到】
: DP可以做(写程序)两个字符串的最大公共字串。我觉得比写suffix tree容易些。
|
d**********x
发帖数: 4083 | 55 恩，这是俩不同的问题。。
【在 f*****e 的大作中提到】
: suffix tree能做出来吗？那个是连续的吧？
|
c********t
发帖数: 5706 | 56 为什么BFS效率高？
我感觉我的DFS那个加了greedy. 如果能加上三个优化。
1.用bit方法做。 23= （10000+100+10+1） or (100000-1000-1)
2. 每次用binary search在bit上来找 k, 使得2^（k-1）< n <= 2^k。
3.还有isPow(n)这个函数有O(1)解法。
这样综合起来应该是最快解法。
【在 p*****2 的大作中提到】
:
: 感觉面试用DP更好。
|
f*********m
发帖数: 726 | 57 二哥能说说这个bfs的思路吗？
【在 p*****2 的大作中提到】
:
: 感觉面试用DP更好。
|
p*****2
发帖数: 21240 | 58
23楼是目标，我们认为distance是0
那么distance为1的是哪些？就是跟23的差是2的倍数的值，比如
23-22=1 Yes
23-21 =2 Yes
23-19 =4 Yes
把distance为1的放到queue里。
然后找distance为2的，找到0为止
我的算法只是demo，里边几个地方都需要优化的。但是基本这个意思。第一个0找到就
是最短路径。而一般dfs要找全才可以得出最短。上边dfs我还没看为什么更优。
【在 f*********m 的大作中提到】
: 二哥能说说这个bfs的思路吗？
|
a***o
发帖数: 1182 | 59 二爷如果不知道最高的层数的话,
假设是无限楼层,bfs是不是没法做了?
要证明不超过target*2?
【在 p*****2 的大作中提到】
:
: 23楼是目标，我们认为distance是0
: 那么distance为1的是哪些？就是跟23的差是2的倍数的值，比如
: 23-22=1 Yes
: 23-21 =2 Yes
: 23-19 =4 Yes
: 把distance为1的放到queue里。
: 然后找distance为2的，找到0为止
: 我的算法只是demo，里边几个地方都需要优化的。但是基本这个意思。第一个0找到就
: 是最短路径。而一般dfs要找全才可以得出最短。上边dfs我还没看为什么更优。
|
c********t
发帖数: 5706 | 60 你这个bfs有问题吧，
还应该考虑吧
24-23=1
25-23=2
27-23=4
。
。
。
看看楼上devilphonix的bfs吧
【在 p*****2 的大作中提到】
:
: 23楼是目标，我们认为distance是0
: 那么distance为1的是哪些？就是跟23的差是2的倍数的值，比如
: 23-22=1 Yes
: 23-21 =2 Yes
: 23-19 =4 Yes
: 把distance为1的放到queue里。
: 然后找distance为2的，找到0为止
: 我的算法只是demo，里边几个地方都需要优化的。但是基本这个意思。第一个0找到就
: 是最短路径。而一般dfs要找全才可以得出最短。上边dfs我还没看为什么更优。
|
|
|
S******0
发帖数: 71 | 61 改成BFS了
//each time can jump up or down 2^k steps, find fewest jumping step,
//always start from the first step
vector getJumpSteps(int nCur, int nMaxStep)
{
vector vec;
if (nCur <= 0 || nMaxStep < nCur)
return vec;
int flg = 1;
while (nCur + flg <= nMaxStep)
{
vec.push_back(nCur + flg);
flg = (flg << 1);
}
flg = 1;
while (nCur - flg > 0)
{
vec.push_back(nCur - flg);
flg = (flg << 1);
}
return vec;
}
int getMinStep(int n, int nMaxStep)
{
if (n <= 0 || nMaxStep < n)
return -1;
queue que;
que.push(1);
set rec;
int nCurNum = 1;
int nNextNum = 0;
int nCurLev = 0;
while (!que.empty())
{
int nCur = que.front();
rec.insert(nCur);
que.pop();
nCurNum--;
vector vec = getJumpSteps(nCur, nMaxStep);
for (int i = 0; i < vec.size(); i++)
{
if (vec[i] == n)
return nCurLev+1;
if (rec.find(vec[i]) == rec.end())
{
que.push(vec[i]);
nNextNum++;
}
}
if (nCurNum == 0)
{
nCurLev++;
nCurNum = nNextNum;
nNextNum = 0;
}
}
return -1;
} |
p*****2
发帖数: 21240 | 62
无限楼层最差的话也是第一个2^n大于target的吧？不可能比这个大还更优吧？
【在 a***o 的大作中提到】
: 二爷如果不知道最高的层数的话,
: 假设是无限楼层,bfs是不是没法做了?
: 要证明不超过target*2?
|
p*****2
发帖数: 21240 | 63
无所谓吧。本来就是说个思路。
【在 c********t 的大作中提到】
: 你这个bfs有问题吧，
: 还应该考虑吧
: 24-23=1
: 25-23=2
: 27-23=4
: 。
: 。
: 。
: 看看楼上devilphonix的bfs吧
|
