Q**F 发帖数: 995 | 1 1. 二维matrix,含0,1。 1是障碍。
00011
11100
从左上角出发到右下角, 可以往上,往下,往右移动。
把1变成0,使得你可以从左上角到右下角。
求最小的变化数字。
2。 两个区间,左闭右开。数字可以是整数或者浮点,
要你判断两个区间是否相交。
特殊例子需要你自己定义。 |
s***c 发帖数: 639 | 2 patpat
第二题是有什么坑么?
【在 Q**F 的大作中提到】 : 1. 二维matrix,含0,1。 1是障碍。 : 00011 : 11100 : 从左上角出发到右下角, 可以往上,往下,往右移动。 : 把1变成0,使得你可以从左上角到右下角。 : 求最小的变化数字。 : 2。 两个区间,左闭右开。数字可以是整数或者浮点, : 要你判断两个区间是否相交。 : 特殊例子需要你自己定义。
|
Q**F 发帖数: 995 | 3 我也不知道,那个面试的一直说这不对,那不对。
【在 s***c 的大作中提到】 : patpat : 第二题是有什么坑么?
|
y******s 发帖数: 92 | 4 第一题怎么解决?能往上一下子就复杂了
【在 Q**F 的大作中提到】 : 1. 二维matrix,含0,1。 1是障碍。 : 00011 : 11100 : 从左上角出发到右下角, 可以往上,往下,往右移动。 : 把1变成0,使得你可以从左上角到右下角。 : 求最小的变化数字。 : 2。 两个区间,左闭右开。数字可以是整数或者浮点, : 要你判断两个区间是否相交。 : 特殊例子需要你自己定义。
|
Q**F 发帖数: 995 | 5 我准备用recursive的,然后那个面试的一直说这也不对那也不对,当时真想直接挂电
话。
给人满满的负能量 |
h**i 发帖数: 12 | 6 我觉得第一题可以用类似 BFS 的解法搞。 先把从起点能走到的所有0都找到,之后找
和这些0相邻的1,记下改变为1,之后再找这些层外边的1,记下改变为2,直到找到右
下角。
第二题,感觉 没什么难度。 莫非有啥大坑?
三种情况
1)
----
----
2)
--
------
3)
-----
-----
求提示有哪些坑? |
Q**F 发帖数: 995 | 7 他一直提到,
开区间的数字不能用来作比较。
【在 h**i 的大作中提到】 : 我觉得第一题可以用类似 BFS 的解法搞。 先把从起点能走到的所有0都找到,之后找 : 和这些0相邻的1,记下改变为1,之后再找这些层外边的1,记下改变为2,直到找到右 : 下角。 : 第二题,感觉 没什么难度。 莫非有啥大坑? : 三种情况 : 1) : ---- : ---- : 2) : --
|
w********5 发帖数: 54 | 8 这是第几轮电面?还是onsite?
【在 Q**F 的大作中提到】 : 1. 二维matrix,含0,1。 1是障碍。 : 00011 : 11100 : 从左上角出发到右下角, 可以往上,往下,往右移动。 : 把1变成0,使得你可以从左上角到右下角。 : 求最小的变化数字。 : 2。 两个区间,左闭右开。数字可以是整数或者浮点, : 要你判断两个区间是否相交。 : 特殊例子需要你自己定义。
|
M**********l 发帖数: 68 | 9 第一题不是标准的最短路径吗?dijkastra就可以了吧。 |
b*****n 发帖数: 618 | 10 breadth first search就可以了,每次把相邻能到达的0都放到queue里面就行 |
|
|
M**********l 发帖数: 68 | 11 如果旁边都是1怎么办?
【在 b*****n 的大作中提到】 : breadth first search就可以了,每次把相邻能到达的0都放到queue里面就行
|
b*****n 发帖数: 618 | 12 旁边都是1的话就不用放额外的,下一层再处理旁边的1,queue里面存当前最短能到的
所有点,不管是1还是0 |
b*****n 发帖数: 618 | 13 backtracking?没懂什么意思,你是说用DFS? |
Q**F 发帖数: 995 | |
h****e 发帖数: 2125 | 15 太狠了。
【在 Q**F 的大作中提到】 : 这个是店面
|
h****e 发帖数: 2125 | 16 你好像是拿过FLG offer的吧,连backtracking都不知道??
【在 b*****n 的大作中提到】 : backtracking?没懂什么意思,你是说用DFS?
|
b*****n 发帖数: 618 | 17 上面一直都在讨论的是BFS,你老一句没头没脑的backtracking,估计根本没仔细看就
找个机会来喷而已,爽了么?
这个题目上面已经说了不能用recursion,所以我猜意思是不能用DFS,而且我确实不懂
backtracking跟我们之前讨论的有什么关系,所以你能不能说说你的解法让我学习一下?
【在 h****e 的大作中提到】 : 你好像是拿过FLG offer的吧,连backtracking都不知道??
|
x******r 发帖数: 3489 | 18 not onsite?
distaining him.
【在 Q**F 的大作中提到】 : 我准备用recursive的,然后那个面试的一直说这也不对那也不对,当时真想直接挂电 : 话。 : 给人满满的负能量
|
h****e 发帖数: 2125 | 19 谁说不能用recursion?你丫到底懂不懂backtracking?唧唧歪歪废话真特么多。
下?
【在 b*****n 的大作中提到】 : 上面一直都在讨论的是BFS,你老一句没头没脑的backtracking,估计根本没仔细看就 : 找个机会来喷而已,爽了么? : 这个题目上面已经说了不能用recursion,所以我猜意思是不能用DFS,而且我确实不懂 : backtracking跟我们之前讨论的有什么关系,所以你能不能说说你的解法让我学习一下?
|
h****e 发帖数: 2125 | 20 可以complain,但是一般只有在其他面试者说你好的情况下才可能有用。电面估计戏不
大。
【在 x******r 的大作中提到】 : not onsite? : distaining him.
|
|
|
b*****n 发帖数: 618 | 21 我用backtracking没有你出神入化,感觉做这个题目不如BFS
你上个backtracking的解法吧,看看能不能比BFS更好
你要就是想喷我可以专门开贴,讨论题目就是讨论题目,不欢迎我可以不来。
【在 h****e 的大作中提到】 : 谁说不能用recursion?你丫到底懂不懂backtracking?唧唧歪歪废话真特么多。 : : 下?
|
h****e 发帖数: 2125 | 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*****1 发帖数: 6807 | 23 作为一个面试官,想挂你基本就是这样找茬的,真的很无聊
我就是这样被小印搞的,不过倒是学会以后怎么对付小印烙印
希望找到工作当面试官多多让我面他们
【在 Q**F 的大作中提到】 : 我准备用recursive的,然后那个面试的一直说这也不对那也不对,当时真想直接挂电 : 话。 : 给人满满的负能量
|
s********l 发帖数: 998 | 24 如果没有0了 都被1堵住了 怎么办?
【在 b*****n 的大作中提到】 : breadth first search就可以了,每次把相邻能到达的0都放到queue里面就行
|
b*****n 发帖数: 618 | 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*****n 发帖数: 618 | 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*******o 发帖数: 4773 | 27 第一题,不就是所有路径中含1最少的那个路径,1的个数吗? |
i*******e 发帖数: 114 | 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********l 发帖数: 998 | 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********l 发帖数: 998 | 30 为什么不能比呢?
可以< > 这个数啊~
【在 Q**F 的大作中提到】 : 他一直提到, : 开区间的数字不能用来作比较。
|
|
|
n******n 发帖数: 12088 | 31 第一题还可以向上?
【在 Q**F 的大作中提到】 : 1. 二维matrix,含0,1。 1是障碍。 : 00011 : 11100 : 从左上角出发到右下角, 可以往上,往下,往右移动。 : 把1变成0,使得你可以从左上角到右下角。 : 求最小的变化数字。 : 2。 两个区间,左闭右开。数字可以是整数或者浮点, : 要你判断两个区间是否相交。 : 特殊例子需要你自己定义。
|
l******s 发帖数: 3045 | |
j**********0 发帖数: 20 | 33 Good!
【在 h**i 的大作中提到】 : 我觉得第一题可以用类似 BFS 的解法搞。 先把从起点能走到的所有0都找到,之后找 : 和这些0相邻的1,记下改变为1,之后再找这些层外边的1,记下改变为2,直到找到右 : 下角。 : 第二题,感觉 没什么难度。 莫非有啥大坑? : 三种情况 : 1) : ---- : ---- : 2) : --
|
b***e 发帖数: 1419 | 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***e 发帖数: 1419 | 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*****n 发帖数: 618 | 36 看来我又没说清楚。。
不是priority queue呀,优化过后已经变成宽度优先搜索了,FIFO queue就行了,我的
解确实是O(n)的。
可能思路跟你的不太一样?能稍微说一下吗
【在 b***e 的大作中提到】 : 这个可以,但是复杂度是O(n*log(n)). 你那个queue是个priority queue, 每次找最 : 小要log(n). 这题是有O(n)解的。 : : 1
|
b***e 发帖数: 1419 | 37 hmmm,纯bfs貌似不行。如果是single source最短路算法,每次应该是从队列里取当前
的最小值继续展开,而不是简单的fifo。你无法保证队列里的第一个值总是最小的。你
这个优化我还没理解。
从另外一个角度看,你这个解法完全可以解决允许向左走的问题。
我原本的想法是从右往左逐列dp.
【在 b*****n 的大作中提到】 : 看来我又没说清楚。。 : 不是priority queue呀,优化过后已经变成宽度优先搜索了,FIFO queue就行了,我的 : 解确实是O(n)的。 : 可能思路跟你的不太一样?能稍微说一下吗
|
h****e 发帖数: 2125 | 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*****c 发帖数: 21 | 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; i
for(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*******e 发帖数: 114 | 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****e 发帖数: 2125 | 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*****n 发帖数: 618 | 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**F 发帖数: 995 | 43 是不是我的题目没有说清楚?
第一题,只是一个2 x M 的矩阵,只含有0,1. 1是障碍物。 在每个cell的时候,只能
往右,往上和往下走,不能往左走。
如果左上角(0,0)能够找到一条路径直接到(1,m-1), 那么就不需要把任何1变成0
, 返回0.
如果不能从左上角到达右下角, 从所有的可能的路径中找到一条路径,这条路径上需
要把1变成0 的数目是最少的, 使得左上角可以到达右下角。 |
b*****n 发帖数: 618 | 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*****n 发帖数: 618 | 45 你的题目叙述应该没问题,大家理解的都是一个意思。
0
【在 Q**F 的大作中提到】 : 是不是我的题目没有说清楚? : 第一题,只是一个2 x M 的矩阵,只含有0,1. 1是障碍物。 在每个cell的时候,只能 : 往右,往上和往下走,不能往左走。 : 如果左上角(0,0)能够找到一条路径直接到(1,m-1), 那么就不需要把任何1变成0 : , 返回0. : 如果不能从左上角到达右下角, 从所有的可能的路径中找到一条路径,这条路径上需 : 要把1变成0 的数目是最少的, 使得左上角可以到达右下角。
|
Q**F 发帖数: 995 | 46 是的,否则就是一道简单的题目了。
【在 n******n 的大作中提到】 : 第一题还可以向上?
|
Q**F 发帖数: 995 | 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*****n 发帖数: 618 | 48 生搬硬套的是你吧?
路径的cost就一定是走几步?
我们讨论的你最好别看懂,还是用你那个牛逼做法做吧,这题很明显应该是用你那个牛
逼做法就对了
【在 h****e 的大作中提到】 : 你们这些人好像都不看题目,就是拿自己见过的生搬硬套。 : : = : =
|
h****e 发帖数: 2125 | 49 瞧你这傻逼样
【在 b*****n 的大作中提到】 : 生搬硬套的是你吧? : 路径的cost就一定是走几步? : 我们讨论的你最好别看懂,还是用你那个牛逼做法做吧,这题很明显应该是用你那个牛 : 逼做法就对了
|
s********l 发帖数: 998 | 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********l 发帖数: 998 | 51 lz说的矩阵 只有2行~
你的解法应该适合于很多行
要是就2行的话 dp就可以了把~
【在 b*****n 的大作中提到】 : 是这个意思,跟我的想法基本一样 : 路径的cost指的是需要把多少个1变成0,这样的话其实从一个点出发能到的所有0的点 : 跟这个点的cost是一样的,所以可以直接放到queue里面。 : : = : =
|
b*****n 发帖数: 618 | 52 确实没看到,我按照n × m做的
【在 s********l 的大作中提到】 : lz说的矩阵 只有2行~ : 你的解法应该适合于很多行 : 要是就2行的话 dp就可以了把~
|
b***e 发帖数: 1419 | 53 谢谢ifyoucode解释。 这回明白了,你这个有些取巧,因为每个点的值都是1,你的
priority queue里最多有两个不同的值,所以取最小是O(1)。如果每个点的值是任意整
数你这个就O(n)不了了。dp的话仍然可以O(n)。
【在 b*****n 的大作中提到】 : 是这个意思,跟我的想法基本一样 : 路径的cost指的是需要把多少个1变成0,这样的话其实从一个点出发能到的所有0的点 : 跟这个点的cost是一样的,所以可以直接放到queue里面。 : : = : =
|
h****e 发帖数: 2125 | 54 承认自己傻逼了吧?
【在 b*****n 的大作中提到】 : 确实没看到,我按照n × m做的
|
b*****n 发帖数: 618 | 55 " 二维matrix,含0,1。 1是障碍。
00011
11100
从左上角出发到右下角, 可以往上,往下,往右移动。
把1变成0,使得你可以从左上角到右下角。
求最小的变化数字。"
这是原来的描述,二维matrix,所以我觉得是m×n
我题都没看懂傻逼了,你牛逼你继续喷吧,你还可以继续用你牛逼的backtracking来解
这个只有两行的matrix
【在 h****e 的大作中提到】 : 承认自己傻逼了吧?
|
b***e 发帖数: 1419 | 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**F 发帖数: 995 | 57 大牛们不要吵架了。
【在 b*****n 的大作中提到】 : " 二维matrix,含0,1。 1是障碍。 : 00011 : 11100 : 从左上角出发到右下角, 可以往上,往下,往右移动。 : 把1变成0,使得你可以从左上角到右下角。 : 求最小的变化数字。" : 这是原来的描述,二维matrix,所以我觉得是m×n : 我题都没看懂傻逼了,你牛逼你继续喷吧,你还可以继续用你牛逼的backtracking来解 : 这个只有两行的matrix
|
o********r 发帖数: 79 | 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*****5 发帖数: 1920 | 59 BFS所有路径,一路加过去,然后记下到终点的时候,最小的和。
放个map,坐标为Key,value为到这个坐标的最小值 |
d********m 发帖数: 101 | 60 LZ第2题看不明白啊,能详细说下不
【在 Q**F 的大作中提到】 : 1. 二维matrix,含0,1。 1是障碍。 : 00011 : 11100 : 从左上角出发到右下角, 可以往上,往下,往右移动。 : 把1变成0,使得你可以从左上角到右下角。 : 求最小的变化数字。 : 2。 两个区间,左闭右开。数字可以是整数或者浮点, : 要你判断两个区间是否相交。 : 特殊例子需要你自己定义。
|
|
|
c***t 发帖数: 50 | 61 第一题:
应该就是BFS加染色就行了。
第二题:
这题考点在哪?难道是说有可能一个区间是整型和另一个是浮点区间比较?为啥开区间
的数字不能用来比较? |
p******d 发帖数: 63 | 62 用普通dp只考虑向下和向右移动就可以,因为所有cost都是非负数,所以对任何一列来
说,cost从下往上递增,所以向上移动可以忽略。 |
n**d 发帖数: 26 | 63 已经看不懂dp了 = =
第一题我会用flood fill + m×n 空间 |