google/youtube onsite面经 3/14/2018

第四题用DFS不是好办法，你需要将target word几乎每个位置都要尝试缩小几次，显得暴力而复杂。
比较好的办法是将target word和字典里的word都转成类似a2b4c8的形式，这样两者比较起来就很方便了。

第二题的做法：遍历上边界和下边界，这是o(N^2)，然后将中间的部分按纵向累加起来，问题就转换为转换为在这个上下界范围内求一维的maximum sum subarray，用经典kadane算法，o(N)。

wisdompeak2 发表于 2018-10-4 14:30
第四题用DFS不是好办法，你需要将target word几乎每个位置都要尝试缩小几次，显得暴力而复杂。
比较好的办 ...

能否具体一些

legendks 发表于 2018-4-4 03:23
神特么是哈密尔顿，烙印也是厉害，哈密尔顿一个NPC的问题。。。这个题其实是二分图的最小加权完美匹配，有N ...

请问POJ上有没有和这个类似的题目可以看看，始终不知道怎么把它想成一个二分图

bucuobucuo

還要多學習謝謝分享

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

legendks 发表于 2018-4-4 03:23
神特么是哈密尔顿，烙印也是厉害，哈密尔顿一个NPC的问题。。。这个题其实是二分图的最小加权完美匹配，有N ...

是啊，可以用munkres-agriosm来做，On^3的复杂度