狗哥热乎乎备考被店面

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

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

求过求大米！

Zpeace 发表于 2018-10-27 09:15
reflection principle for follow up. same as ways to reach (xmax, 2h)

这种做法不一定对
原题中给了坐标系范围，如果人家maxy都没有2h大怎么办？而且我谨慎怀疑这个reflection principle放在这是不是正确
真正保险的方法，应该是将matrix缩小为(maxx, h-1)，求走到(xmax, 0)的方法数，然后用原答案减去这个方法数即可

分享一个follow up的答法
y = h，我们就把原矩形切割成 一个小矩形 小矩形的高度为 h - 1
count(原矩形)  - count(y = h - 1) 即得到我们要的答案
因为一旦超过了h 怎么样都会碰到h这条边

Zpeace 发表于 2018-10-28 20:36
坐标范围只要保证有 h 就好吧？reflection principle只是假想对称一下，没有要真走过去。

我理解的镜像，是可以将原来结果中的某一类步骤，映射到新的一类步骤中去
假如说走到(maxx, 0)，那么可以知道，向左走和向右走的步数一定是一样多的，而且因为越过了h，所以可以知道steps to right > h and steps to left > h
那么如何将向左的步骤映射到向右？选出来的向左的步骤应该少于h，那该选哪些步映射呢？所以肯定不是唯一映射的
我实际写了程序，如果你按照我前面提到的方法写一遍，再按照映射的方法写一遍，对比一下会发现两者结果不一样，而且maxy与h差的越大结果差的越多，就是因为maxy越大，越过h这条线之后可以向右走的越多，相应的向左走的也就越多，映射越不准确。

lz，请问第一题是不是类似lc62？

感谢分享，第一题最近经常看见。问一下最早就是一个bfs，followup怎么答？

吟游诗人刘小翠 发表于 2018-10-26 23:36
lz，请问第一题是不是类似lc62？

有一点像

请问背靠背是每场只做一题吗？

reflection principle for follow up. same as ways to reach (xmax, 2h)

同好奇，follow up咋答

求问第一题follow  up