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 空间 |
