狗家店面过经

【全程无bq】
上来直接开始做题

给了一个n x n 的matrix with unique Integer,

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

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

本来想着凉了,结果过两天被告知good news。。


求大米！！！


补充内容 (2022-03-12 23:27 +8:00):
每一次只能和相邻的数字swap.

OliG0002 发表于 2022-3-20 21:13
请问这题是要求最少的swap路径吗？

Queue每次存进去N*N*4个组合来BFS 太暴力了吧，如果是求任意可行的s ...

一开始题目没有要求，经过clarify之后要求最短路径。
是的，时间和空间复杂度都很高

匿名者 发表于 2022-3-12 09:04
对的。queue每次存进去N*N*4个组合进去，然后无限叠加 (visited除外）,但感觉面试官喜欢这个solution就跟 ...

这复杂度是n^2*n!吧，有点高啊

pleasespeak 发表于 2022-3-11 21:56
请问BFS是什么思路呀

我自己define一个class来存list of move还有matrix的现状,然后用了一个genMoves来return当前matrix所有possible的move，再一个个放进queue里面就好了。

请问BFS是什么思路呀

同问，能解释一下思路吗

同问，只能想到merge sort的解法

匿名者 发表于 2022-3-12 07:23
同问，只能想到merge sort的解法

噢。。每一次只能和相邻的数字swap。 漏了不好意思

匿名用户 发表于 2022-03-12 07:23:51
同问，只能想到merge sort的解法

懂了，就是每一行先找到最小值，坐标放进PQ里，然后BFS

匿名者 发表于 2022-3-12 07:30
懂了，就是每一行先找到最小值，坐标放进PQ里，然后BFS

Not sure if that works.. 每一个数字都可以上下左右互换。e.g input有可能是
[[9,8,7],
[6,5,4],  
[3,2,1]]

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

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

楼主所说的BFS好像是state space 里的BFS而不是matrix本身的BFS？

然后每交换一步，新的swap able pairs 可以直接O(1)生成? 这个queue不会爆炸么