大脸实习两轮电面

ghostpuppy · 2017-12-16 07:14:27

changyue5230 发表于 2017-12-15 18:11
是不是1都得遍历一遍吧

地图上每个点不管0/1都遍历一次,所以时间复杂度mn
如果在原来地图上标记,空间复杂度就是栈最坏情况的大小

Variable · 2017-12-16 07:22:53

求问楼主求股票最大利润那个题是最基础那个还是某个变种啊？就是算单次交易最大的利润还是所有可能的交易利润还是有cooling down的那种啊？

manmankan · 2017-12-16 07:35:39

ghostpuppy 发表于 2017-12-16 07:03
在原来的地图上修改1为0,这个地方是没有额外空间需要的.我说的O(max(n,m))指的是dfs的时候递归栈的空间

...

会不会出现DFS一次遍历所有点的情况呢，这样会有mn个压栈操作

ghostpuppy · 2017-12-16 07:55:21

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

ghostpuppy · 2017-12-16 07:57:26

manmankan 发表于 2017-12-15 18:35
会不会出现DFS一次遍历所有点的情况呢，这样会有mn个压栈操作

正常dfs代码总有一个遍历的顺序比如说:上下左右,这么来最多走n或者m就到边出栈了,哪有你强行蛇皮走位遍历强行mn个点的...你要是这么设计最坏情况也不是不可以,写个螺旋或者s形dfs

changyue5230 · 2017-12-16 08:02:04

Variable 发表于 2017-12-16 07:22
求问楼主求股票最大利润那个题是最基础那个还是某个变种啊？就是算单次交易最大的利润还是所有可能的交易 ...

单次交易不加手续费

manmankan · 2017-12-16 23:24:51

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

ghostpuppy · 2017-12-16 23:49:23

manmankan 发表于 2017-12-16 10:24
public class Solution {

private int n;

worst case 是Omn 没错辣

大脸 实习 两轮电面