google面经（挂了） - 未名空间MITBBS历史存档

Q*F2015-07-10 07:07

1 楼

1. 二维matrix，含0，1。 1是障碍。
00011
11100
从左上角出发到右下角，可以往上，往下，往右移动。
把1变成0，使得你可以从左上角到右下角。
求最小的变化数字。
2。两个区间，左闭右开。数字可以是整数或者浮点，
要你判断两个区间是否相交。
特殊例子需要你自己定义。

s*c2015-07-10 07:07

2 楼

patpat
第二题是有什么坑么？

【在 Q**F 的大作中提到】

: 1. 二维matrix，含0，1。 1是障碍。
: 00011
: 11100
: 从左上角出发到右下角，可以往上，往下，往右移动。
: 把1变成0，使得你可以从左上角到右下角。
: 求最小的变化数字。
: 2。两个区间，左闭右开。数字可以是整数或者浮点，
: 要你判断两个区间是否相交。
: 特殊例子需要你自己定义。

Q*F2015-07-10 07:07

3 楼

我也不知道，那个面试的一直说这不对，那不对。

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

: patpat
: 第二题是有什么坑么？

y*s2015-07-10 07:07

4 楼

第一题怎么解决？能往上一下子就复杂了

【在 Q**F 的大作中提到】

: 1. 二维matrix，含0，1。 1是障碍。
: 00011
: 11100
: 从左上角出发到右下角，可以往上，往下，往右移动。
: 把1变成0，使得你可以从左上角到右下角。
: 求最小的变化数字。
: 2。两个区间，左闭右开。数字可以是整数或者浮点，
: 要你判断两个区间是否相交。
: 特殊例子需要你自己定义。

Q*F2015-07-10 07:07

5 楼

我准备用recursive的，然后那个面试的一直说这也不对那也不对，当时真想直接挂电
话。
给人满满的负能量

h*i2015-07-10 07:07

6 楼

我觉得第一题可以用类似 BFS 的解法搞。先把从起点能走到的所有0都找到，之后找
和这些0相邻的1，记下改变为1，之后再找这些层外边的1，记下改变为2，直到找到右
下角。
第二题，感觉没什么难度。莫非有啥大坑？
三种情况
1）
----
----
2）
--
------
3）
-----
-----
求提示有哪些坑？

Q*F2015-07-10 07:07

7 楼

他一直提到，
开区间的数字不能用来作比较。

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

: 我觉得第一题可以用类似 BFS 的解法搞。先把从起点能走到的所有0都找到，之后找
: 和这些0相邻的1，记下改变为1，之后再找这些层外边的1，记下改变为2，直到找到右
: 下角。
: 第二题，感觉没什么难度。莫非有啥大坑？
: 三种情况
: 1）
: ----
: ----
: 2）
: --

w*52015-07-10 07:07

8 楼

这是第几轮电面？还是onsite？

【在 Q**F 的大作中提到】

: 1. 二维matrix，含0，1。 1是障碍。
: 00011
: 11100
: 从左上角出发到右下角，可以往上，往下，往右移动。
: 把1变成0，使得你可以从左上角到右下角。
: 求最小的变化数字。
: 2。两个区间，左闭右开。数字可以是整数或者浮点，
: 要你判断两个区间是否相交。
: 特殊例子需要你自己定义。

M*l2015-07-10 07:07

9 楼

第一题不是标准的最短路径吗？dijkastra就可以了吧。

b*n2015-07-10 07:07

10 楼

breadth first search就可以了，每次把相邻能到达的0都放到queue里面就行

M*l2015-07-10 07:07

11 楼

如果旁边都是1怎么办？

【在 b*****n 的大作中提到】

: breadth first search就可以了，每次把相邻能到达的0都放到queue里面就行

b*n2015-07-10 07:07

12 楼

旁边都是1的话就不用放额外的，下一层再处理旁边的1，queue里面存当前最短能到的
所有点，不管是1还是0

b*n2015-07-10 07:07

13 楼

backtracking？没懂什么意思，你是说用DFS？

Q*F2015-07-10 07:07

14 楼

这个是店面

h*e2015-07-10 07:07

15 楼

太狠了。

【在 Q**F 的大作中提到】

: 这个是店面

h*e2015-07-10 07:07

16 楼

你好像是拿过FLG offer的吧，连backtracking都不知道？？

【在 b*****n 的大作中提到】

: backtracking？没懂什么意思，你是说用DFS？

b*n2015-07-10 07:07

17 楼

上面一直都在讨论的是BFS，你老一句没头没脑的backtracking，估计根本没仔细看就
找个机会来喷而已，爽了么？
这个题目上面已经说了不能用recursion，所以我猜意思是不能用DFS，而且我确实不懂
backtracking跟我们之前讨论的有什么关系，所以你能不能说说你的解法让我学习一下？

【在 h****e 的大作中提到】

: 你好像是拿过FLG offer的吧，连backtracking都不知道？？

x*r2015-07-10 07:07

18 楼

not onsite？
distaining him.

【在 Q**F 的大作中提到】

: 我准备用recursive的，然后那个面试的一直说这也不对那也不对，当时真想直接挂电
: 话。
: 给人满满的负能量

h*e2015-07-10 07:07

19 楼

谁说不能用recursion？你丫到底懂不懂backtracking？唧唧歪歪废话真特么多。

下？

【在 b*****n 的大作中提到】

: 上面一直都在讨论的是BFS，你老一句没头没脑的backtracking，估计根本没仔细看就
: 找个机会来喷而已，爽了么？
: 这个题目上面已经说了不能用recursion，所以我猜意思是不能用DFS，而且我确实不懂
: backtracking跟我们之前讨论的有什么关系，所以你能不能说说你的解法让我学习一下？

h*e2015-07-10 07:07

20 楼

可以complain，但是一般只有在其他面试者说你好的情况下才可能有用。电面估计戏不
大。

【在 x******r 的大作中提到】

: not onsite？
: distaining him.

b*n2015-07-10 07:07

21 楼

我用backtracking没有你出神入化，感觉做这个题目不如BFS
你上个backtracking的解法吧，看看能不能比BFS更好
你要就是想喷我可以专门开贴，讨论题目就是讨论题目，不欢迎我可以不来。

【在 h****e 的大作中提到】

: 谁说不能用recursion？你丫到底懂不懂backtracking？唧唧歪歪废话真特么多。
:
: 下？

h*e2015-07-10 07:07

22 楼

这题一看让你把1变0，自然就是考backtracking。三个方向：dirs = {{0,-1},{0,1},{
1,0}}，当前coordinate要loop through这三个方向。如果新坐标的值是1的话，就要先
变成0同时total变化数量加一，然后call recursive method。在recursive call之后
你还得把新坐标变回1，再try下一个方向。
懂了？

【在 b*****n 的大作中提到】

: 我用backtracking没有你出神入化，感觉做这个题目不如BFS
: 你上个backtracking的解法吧，看看能不能比BFS更好
: 你要就是想喷我可以专门开贴，讨论题目就是讨论题目，不欢迎我可以不来。

w*12015-07-10 07:07

23 楼

作为一个面试官，想挂你基本就是这样找茬的，真的很无聊
我就是这样被小印搞的，不过倒是学会以后怎么对付小印烙印
希望找到工作当面试官多多让我面他们

【在 Q**F 的大作中提到】

: 我准备用recursive的，然后那个面试的一直说这也不对那也不对，当时真想直接挂电
: 话。
: 给人满满的负能量

s*l2015-07-10 07:07

24 楼

如果没有0了都被1堵住了怎么办？

【在 b*****n 的大作中提到】

: breadth first search就可以了，每次把相邻能到达的0都放到queue里面就行

b*n2015-07-10 07:07

25 楼

要求的是最小值，你这个要是不同路径最小值变化了还要更新。
比如这种情况
0 1 0
0 0 0
你要求最右上角的这个0，必须把所有路径都知道才能知道最小值
给个时间复杂度分析吧，能不能比BFS好

,{

【在 h****e 的大作中提到】

: 这题一看让你把1变0，自然就是考backtracking。三个方向：dirs = {{0,-1},{0,1},{
: 1,0}}，当前coordinate要loop through这三个方向。如果新坐标的值是1的话，就要先
: 变成0同时total变化数量加一，然后call recursive method。在recursive call之后
: 你还得把新坐标变回1，再try下一个方向。
: 懂了？

b*n2015-07-10 07:07

26 楼

这个题目转化一下，就是一个图里求最短路径。
如果A和B相邻，那么A和B之间有一条边相连，假如B是1，那么从A到B的边weight就是1
，否则weight是0，所以最基本的想法就是dijkstra
不过这个是可以优化成breadth first search的，如果知道一个值为1的点的最短路径
，那么从这个点出发BFS/DFS可以到达的所有0的点其实跟这个点的最短路径是一样的，
所以可以直接把这些点放到queue里面就行了，breadth first search的当前queue里面
是当前最短路径的所有点，这样一层一层遍历就行。时间复杂度O(n)，n是矩阵的大小

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

: 如果没有0了都被1堵住了怎么办？

z*o2015-07-10 07:07

27 楼

第一题，不就是所有路径中含1最少的那个路径，1的个数吗？

i*e2015-07-10 07:07

28 楼

请问你backtracking的时间复杂度多少？假设 n x n 的空间。
BFS的话，每个iteration 处理某一个单一cost的所有cell。每层之后cost + 1.
时间复杂度可以 O(n^2)，因为每个cell只处理一遍。

,{

【在 h****e 的大作中提到】

: 这题一看让你把1变0，自然就是考backtracking。三个方向：dirs = {{0,-1},{0,1},{
: 1,0}}，当前coordinate要loop through这三个方向。如果新坐标的值是1的话，就要先
: 变成0同时total变化数量加一，然后call recursive method。在recursive call之后
: 你还得把新坐标变回1，再try下一个方向。
: 懂了？

s*l2015-07-10 07:07

29 楼

有道理这个解法好！

1

【在 b*****n 的大作中提到】

: 这个题目转化一下，就是一个图里求最短路径。
: 如果A和B相邻，那么A和B之间有一条边相连，假如B是1，那么从A到B的边weight就是1
: ，否则weight是0，所以最基本的想法就是dijkstra
: 不过这个是可以优化成breadth first search的，如果知道一个值为1的点的最短路径
: ，那么从这个点出发BFS/DFS可以到达的所有0的点其实跟这个点的最短路径是一样的，
: 所以可以直接把这些点放到queue里面就行了，breadth first search的当前queue里面
: 是当前最短路径的所有点，这样一层一层遍历就行。时间复杂度O(n)，n是矩阵的大小

s*l2015-07-10 07:07

30 楼

为什么不能比呢？
可以< > 这个数啊~

【在 Q**F 的大作中提到】

: 他一直提到，
: 开区间的数字不能用来作比较。

n*n2015-07-10 07:07

31 楼

第一题还可以向上？

【在 Q**F 的大作中提到】

: 1. 二维matrix，含0，1。 1是障碍。
: 00011
: 11100
: 从左上角出发到右下角，可以往上，往下，往右移动。
: 把1变成0，使得你可以从左上角到右下角。
: 求最小的变化数字。
: 2。两个区间，左闭右开。数字可以是整数或者浮点，
: 要你判断两个区间是否相交。
: 特殊例子需要你自己定义。

l*s2015-07-10 07:07

32 楼

可以向上也理应可以向左吧？

j*02015-07-10 07:07

33 楼

Good!

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

: 我觉得第一题可以用类似 BFS 的解法搞。先把从起点能走到的所有0都找到，之后找
: 和这些0相邻的1，记下改变为1，之后再找这些层外边的1，记下改变为2，直到找到右
: 下角。
: 第二题，感觉没什么难度。莫非有啥大坑？
: 三种情况
: 1）
: ----
: ----
: 2）
: --

b*e2015-07-10 07:07

34 楼

这个可以，但是复杂度是O(n*log(n)). 你那个queue是个priority queue, 每次找最
小要log(n). 这题是有O(n)解的。

1

【在 b*****n 的大作中提到】

: 这个题目转化一下，就是一个图里求最短路径。
: 如果A和B相邻，那么A和B之间有一条边相连，假如B是1，那么从A到B的边weight就是1
: ，否则weight是0，所以最基本的想法就是dijkstra
: 不过这个是可以优化成breadth first search的，如果知道一个值为1的点的最短路径
: ，那么从这个点出发BFS/DFS可以到达的所有0的点其实跟这个点的最短路径是一样的，
: 所以可以直接把这些点放到queue里面就行了，breadth first search的当前queue里面
: 是当前最短路径的所有点，这样一层一层遍历就行。时间复杂度O(n)，n是矩阵的大小

b*e2015-07-10 07:07

35 楼

我懂了，你这个就是无脑brute force, 还是个0变1，1变0的脱了裤子放屁的太监解。
复杂度O(3^n). 你丫去google面试给这个人当场哄你出来，下面都没有了。
你下次不用码这么多字，多他妈累呀。你丫直接说自己是傻逼大家就秒懂了。

,{

【在 h****e 的大作中提到】

: 这题一看让你把1变0，自然就是考backtracking。三个方向：dirs = {{0,-1},{0,1},{
: 1,0}}，当前coordinate要loop through这三个方向。如果新坐标的值是1的话，就要先
: 变成0同时total变化数量加一，然后call recursive method。在recursive call之后
: 你还得把新坐标变回1，再try下一个方向。
: 懂了？

b*n2015-07-10 07:07

36 楼

看来我又没说清楚。。
不是priority queue呀，优化过后已经变成宽度优先搜索了，FIFO queue就行了，我的
解确实是O(n)的。
可能思路跟你的不太一样？能稍微说一下吗

【在 b***e 的大作中提到】

: 这个可以，但是复杂度是O(n*log(n)). 你那个queue是个priority queue, 每次找最
: 小要log(n). 这题是有O(n)解的。
:
: 1

b*e2015-07-10 07:07

37 楼

hmmm，纯bfs貌似不行。如果是single source最短路算法，每次应该是从队列里取当前
的最小值继续展开，而不是简单的fifo。你无法保证队列里的第一个值总是最小的。你
这个优化我还没理解。
从另外一个角度看，你这个解法完全可以解决允许向左走的问题。
我原本的想法是从右往左逐列dp.

【在 b*****n 的大作中提到】

: 看来我又没说清楚。。
: 不是priority queue呀，优化过后已经变成宽度优先搜索了，FIFO queue就行了，我的
: 解确实是O(n)的。
: 可能思路跟你的不太一样？能稍微说一下吗

h*e2015-07-10 07:07

38 楼

我看你是生搬硬套。这题哪里是最短路径了？比如下面例子：
0(A) 0(B) 0(C)
0(D) 1(E) 0(F)
假设括号里面是这个点的名字，从D到F的最短路径是变E为0然后D->E->F。但是如果是
变化最少，很明显应该是D->A->B->C>F

1

【在 b*****n 的大作中提到】

: 这个题目转化一下，就是一个图里求最短路径。
: 如果A和B相邻，那么A和B之间有一条边相连，假如B是1，那么从A到B的边weight就是1
: ，否则weight是0，所以最基本的想法就是dijkstra
: 不过这个是可以优化成breadth first search的，如果知道一个值为1的点的最短路径
: ，那么从这个点出发BFS/DFS可以到达的所有0的点其实跟这个点的最短路径是一样的，
: 所以可以直接把这些点放到queue里面就行了，breadth first search的当前queue里面
: 是当前最短路径的所有点，这样一层一层遍历就行。时间复杂度O(n)，n是矩阵的大小

x*c2015-07-10 07:07

39 楼

int minimumPathChange(vector> &pathMap)
{
int M = pathMap.size();
int N = pathMap[0].size();
int numV = M*N;
int w;

vector> adjList(M*N,vector());

for(int i=0; i{
for(int j=0; j{
if(i+1{
w = pathMap[i+1][j];
adjList[i*N+j].push_back(Edge((i+1)*N+j,w));
}
if(j+1{
w = pathMap[i][j+1];
adjList[i*N+j].push_back(Edge((i)*N+j+1,w));
}
if(i-1>=0)
{
w = pathMap[i-1][j];
adjList[i*N+j].push_back(Edge((i-1)*N+j,w));
}
}
}
vector shortestD(numV, INT_MAX);
shortestD[0] = 0;

for(int k=1; k<=numV-1; k++)
{
for(int i=0; ifor(int j=0; j{
int k = adjList[i][j].ver;
shortestD[k] = min(shortestD[k], shortestD[i]+adjList[i][j].
weight);
}
}

return shortestD[M*N-1];
}

i*e2015-07-10 07:07

40 楼

抛砖一下：
maintain two queues,
BFS 第一个iteration, 用queue 1, 只处理cost == 0 的所有cell, 把碰到的所有
cost = 1 的放到 queue 2
BFS 第2个iteration, 用queue 2, 只处理cost == 1的所有cell, 把碰到的所有cost =
2的防到queue1.
BFS 第3个iteration, 用queue 1, 只处理cost == 2的所有cell, 把碰到的所有cost =
3的放到queue2.
以此类推，直到 G 被碰到。
每个cell只被处理一遍， beanbum 应该是这个意思。

【在 b***e 的大作中提到】

: hmmm，纯bfs貌似不行。如果是single source最短路算法，每次应该是从队列里取当前
: 的最小值继续展开，而不是简单的fifo。你无法保证队列里的第一个值总是最小的。你
: 这个优化我还没理解。
: 从另外一个角度看，你这个解法完全可以解决允许向左走的问题。
: 我原本的想法是从右往左逐列dp.

h*e2015-07-10 07:07

41 楼

你们这些人好像都不看题目，就是拿自己见过的生搬硬套。

=
=

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

: 抛砖一下：
: maintain two queues,
: BFS 第一个iteration, 用queue 1, 只处理cost == 0 的所有cell, 把碰到的所有
: cost = 1 的放到 queue 2
: BFS 第2个iteration, 用queue 2, 只处理cost == 1的所有cell, 把碰到的所有cost =
: 2的防到queue1.
: BFS 第3个iteration, 用queue 1, 只处理cost == 2的所有cell, 把碰到的所有cost =
: 3的放到queue2.
: 以此类推，直到 G 被碰到。
: 每个cell只被处理一遍， beanbum 应该是这个意思。

b*n2015-07-10 07:07

42 楼

你先搞明白最短路径是什么再说吧
这里的路径长度是指"路径上1的个数"

【在 h****e 的大作中提到】

: 我看你是生搬硬套。这题哪里是最短路径了？比如下面例子：
: 0(A) 0(B) 0(C)
: 0(D) 1(E) 0(F)
: 假设括号里面是这个点的名字，从D到F的最短路径是变E为0然后D->E->F。但是如果是
: 变化最少，很明显应该是D->A->B->C>F
:
: 1

Q*F2015-07-10 07:07

43 楼

是不是我的题目没有说清楚？
第一题，只是一个2 x M 的矩阵，只含有0，1. 1是障碍物。在每个cell的时候，只能
往右，往上和往下走，不能往左走。
如果左上角（0，0）能够找到一条路径直接到（1，m-1), 那么就不需要把任何1变成0
，返回0.
如果不能从左上角到达右下角，从所有的可能的路径中找到一条路径，这条路径上需
要把1变成0 的数目是最少的，使得左上角可以到达右下角。

b*n2015-07-10 07:07

44 楼

是这个意思，跟我的想法基本一样
路径的cost指的是需要把多少个1变成0，这样的话其实从一个点出发能到的所有0的点
跟这个点的cost是一样的，所以可以直接放到queue里面。

=
=

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

: 抛砖一下：
: maintain two queues,
: BFS 第一个iteration, 用queue 1, 只处理cost == 0 的所有cell, 把碰到的所有
: cost = 1 的放到 queue 2
: BFS 第2个iteration, 用queue 2, 只处理cost == 1的所有cell, 把碰到的所有cost =
: 2的防到queue1.
: BFS 第3个iteration, 用queue 1, 只处理cost == 2的所有cell, 把碰到的所有cost =
: 3的放到queue2.
: 以此类推，直到 G 被碰到。
: 每个cell只被处理一遍， beanbum 应该是这个意思。

b*n2015-07-10 07:07

45 楼

你的题目叙述应该没问题，大家理解的都是一个意思。

0

【在 Q**F 的大作中提到】

: 是不是我的题目没有说清楚？
: 第一题，只是一个2 x M 的矩阵，只含有0，1. 1是障碍物。在每个cell的时候，只能
: 往右，往上和往下走，不能往左走。
: 如果左上角（0，0）能够找到一条路径直接到（1，m-1), 那么就不需要把任何1变成0
: ，返回0.
: 如果不能从左上角到达右下角，从所有的可能的路径中找到一条路径，这条路径上需
: 要把1变成0 的数目是最少的，使得左上角可以到达右下角。

Q*F2015-07-10 07:07

46 楼

是的，否则就是一道简单的题目了。

【在 n******n 的大作中提到】

: 第一题还可以向上？

Q*F2015-07-10 07:07

47 楼

给个代码实现。

=
=

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

: 抛砖一下：
: maintain two queues,
: BFS 第一个iteration, 用queue 1, 只处理cost == 0 的所有cell, 把碰到的所有
: cost = 1 的放到 queue 2
: BFS 第2个iteration, 用queue 2, 只处理cost == 1的所有cell, 把碰到的所有cost =
: 2的防到queue1.
: BFS 第3个iteration, 用queue 1, 只处理cost == 2的所有cell, 把碰到的所有cost =
: 3的放到queue2.
: 以此类推，直到 G 被碰到。
: 每个cell只被处理一遍， beanbum 应该是这个意思。

b*n2015-07-10 07:07

48 楼

生搬硬套的是你吧？
路径的cost就一定是走几步？
我们讨论的你最好别看懂，还是用你那个牛逼做法做吧，这题很明显应该是用你那个牛
逼做法就对了

【在 h****e 的大作中提到】

: 你们这些人好像都不看题目，就是拿自己见过的生搬硬套。
:
: =
: =

h*e2015-07-10 07:07

49 楼

瞧你这傻逼样

【在 b*****n 的大作中提到】

: 生搬硬套的是你吧？
: 路径的cost就一定是走几步？
: 我们讨论的你最好别看懂，还是用你那个牛逼做法做吧，这题很明显应该是用你那个牛
: 逼做法就对了

s*l2015-07-10 07:07

50 楼

只有2行啊？
我以为n x m矩阵
这样的话是不是dp就可以了~

0

【在 Q**F 的大作中提到】

: 是不是我的题目没有说清楚？
: 第一题，只是一个2 x M 的矩阵，只含有0，1. 1是障碍物。在每个cell的时候，只能
: 往右，往上和往下走，不能往左走。
: 如果左上角（0，0）能够找到一条路径直接到（1，m-1), 那么就不需要把任何1变成0
: ，返回0.
: 如果不能从左上角到达右下角，从所有的可能的路径中找到一条路径，这条路径上需
: 要把1变成0 的数目是最少的，使得左上角可以到达右下角。

s*l2015-07-10 07:07

51 楼

lz说的矩阵只有2行~
你的解法应该适合于很多行
要是就2行的话 dp就可以了把~

【在 b*****n 的大作中提到】

: 是这个意思，跟我的想法基本一样
: 路径的cost指的是需要把多少个1变成0，这样的话其实从一个点出发能到的所有0的点
: 跟这个点的cost是一样的，所以可以直接放到queue里面。
:
: =
: =

b*n2015-07-10 07:07

52 楼

确实没看到，我按照n × m做的

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

: lz说的矩阵只有2行~
: 你的解法应该适合于很多行
: 要是就2行的话 dp就可以了把~

b*e2015-07-10 07:07

53 楼

谢谢ifyoucode解释。这回明白了，你这个有些取巧，因为每个点的值都是1，你的
priority queue里最多有两个不同的值，所以取最小是O(1)。如果每个点的值是任意整
数你这个就O(n)不了了。dp的话仍然可以O(n)。

【在 b*****n 的大作中提到】

: 是这个意思，跟我的想法基本一样
: 路径的cost指的是需要把多少个1变成0，这样的话其实从一个点出发能到的所有0的点
: 跟这个点的cost是一样的，所以可以直接放到queue里面。
:
: =
: =

h*e2015-07-10 07:07

54 楼

承认自己傻逼了吧？

【在 b*****n 的大作中提到】

: 确实没看到，我按照n × m做的

b*n2015-07-10 07:07

55 楼

" 二维matrix，含0，1。 1是障碍。
00011
11100
从左上角出发到右下角，可以往上，往下，往右移动。
把1变成0，使得你可以从左上角到右下角。
求最小的变化数字。"
这是原来的描述，二维matrix，所以我觉得是m×n
我题都没看懂傻逼了，你牛逼你继续喷吧，你还可以继续用你牛逼的backtracking来解
这个只有两行的matrix

【在 h****e 的大作中提到】

: 承认自己傻逼了吧？

b*e2015-07-10 07:07

56 楼

这里是一个DP做法的全解释：
一般的题目是限定只能向下走和向右走，这样的话DP大家都是知道的，就是按逆对角刷
DP：
a(i,j) = min(cost(i,j+1) + a(i,j+1), cost(i+1,j) + a(i+1,j))
这个题目说可以向上走，使得为题复杂化了。但是只需改进DP方式仍然可以解决。这次
我们从右向左逐列刷DP。对于第j列，
for i = 1 to n, a_r(i,j) = cost(i,j+1) + a(i,j+1)
for i = 1 to n, a_u(i,j) = min(a_r(i,j), cost(i-1,j) + a_u(i-1,j))
for i = n to 1, a_d(i,j) = min(a_r(i,j), cost(i+1,j) + a_d(i+1,j))
for i = 1 to n, a(i,j) = min(a_r(i,j), a_u(i,j), a_d(i,j))
a_r(i,j)记录的是从i,j向右走的最佳方式。
a_u(i,j)记录的是从i,j向上走的最佳方式。
a_d(i,j)记录的是从i,j向下走的最佳方式。注意计算a_d的时候要从下往上，e.g. for
n to 1.
这样每个点只算了三次，整体复杂性依然是线性的。
这个加强版的DP可以解决普遍的问题，不局限于矩阵的值只能是0或1。

【在 b***e 的大作中提到】

: 谢谢ifyoucode解释。这回明白了，你这个有些取巧，因为每个点的值都是1，你的
: priority queue里最多有两个不同的值，所以取最小是O(1)。如果每个点的值是任意整
: 数你这个就O(n)不了了。dp的话仍然可以O(n)。

Q*F2015-07-10 07:07

57 楼

大牛们不要吵架了。

【在 b*****n 的大作中提到】

: " 二维matrix，含0，1。 1是障碍。
: 00011
: 11100
: 从左上角出发到右下角，可以往上，往下，往右移动。
: 把1变成0，使得你可以从左上角到右下角。
: 求最小的变化数字。"
: 这是原来的描述，二维matrix，所以我觉得是m×n
: 我题都没看懂傻逼了，你牛逼你继续喷吧，你还可以继续用你牛逼的backtracking来解
: 这个只有两行的matrix

o*r2015-07-10 07:07

58 楼

不要吵了。
我按beanbun的思路写了一遍，指教一下
typedef pair COORD;
void extend(COORD cur,
vector >& visited,
vector > matrix,
queue& current,
queue& next )
{
vector shift;
shift.push_back(make_pair(0,-1));
shift.push_back(make_pair(0,1));
shift.push_back(make_pair(1,0));
const int m = matrix.size();
const int n = matrix[0].size();
for(const auto s:shift)
{
int newx = s.first + cur.first;
int newy = s.second + cur.second;
if(newx>=0 && newx=0 && newy&&visited[newx][newy]==false) // not visted yet
{
if(matrix[newx][newy]== 0 )// not an obstacle
current.push(make_pair(newx,newy));
else
next.push(make_pair(newx,newy));
visited[newx][newy] = true;
}
}
}
int minChange(vector > matrix)
{
if(matrix.empty()) return -1;
const int m = matrix.size();
const int n = matrix[0].size();
vector > visited(m, vector(n,false));
queue current;
queue next;
current.push(make_pair(0,0));
int numChange = 0;
while(!current.empty())
{
while(!current.empty())
{
COORD cur = current.front();
current.pop();
if(cur.first == m-1 && cur.second == n-1)
return numChange; // arrive the bottom right;
extend(cur,visited,matrix,current,next);
}
numChange++;
swap(current, next);
}
return -1;
}

【在 Q**F 的大作中提到】

: 大牛们不要吵架了。

d*52015-07-10 07:07

59 楼

BFS所有路径，一路加过去，然后记下到终点的时候，最小的和。
放个map，坐标为Key，value为到这个坐标的最小值

d*m2015-07-10 07:07

60 楼

LZ第2题看不明白啊，能详细说下不

【在 Q**F 的大作中提到】

: 1. 二维matrix，含0，1。 1是障碍。
: 00011
: 11100
: 从左上角出发到右下角，可以往上，往下，往右移动。
: 把1变成0，使得你可以从左上角到右下角。
: 求最小的变化数字。
: 2。两个区间，左闭右开。数字可以是整数或者浮点，
: 要你判断两个区间是否相交。
: 特殊例子需要你自己定义。

c*t2015-07-10 07:07

61 楼

第一题：
应该就是BFS加染色就行了。
第二题：
这题考点在哪？难道是说有可能一个区间是整型和另一个是浮点区间比较？为啥开区间
的数字不能用来比较？

p*d2015-07-10 07:07

62 楼

用普通dp只考虑向下和向右移动就可以，因为所有cost都是非负数，所以对任何一列来
说，cost从下往上递增，所以向上移动可以忽略。

n*d2015-07-10 07:07

63 楼

已经看不懂dp了 = =
第一题我会用flood fill + m×n 空间