BoP——1.3摞饼问题

问题很简单了,就是大小不同的盘子,摞在一次。如果通过反转,达到盘子最终上到下,为从小到大的顺序。
要求时,不能单独拿。一次必须是上面的几个一起反转。

摞饼

方法一

最简单的方法,就是,冒泡的思想,我们先找最大的,然后反转到顶部,然后再反转到地步。重复。
但是,反转次数过多。

方法二

凡是这种什么最少几次,啥的。几乎都可以使用广度优先搜索解决。
我们以最终状态为起点(序好的状态),然后去遍历每一种反转的情况到起始状态(未排序状态)。
这里就涉及到如何记录这种盘子的状态。如果都是十个,那么使用一个很大的数来表示,不然就只能使用容器了,比较容器。
而且广度优先搜索得到的翻转步骤一定是最少的。

方法三

编程之美中使用的也是类似的方法,但他居然使用的是深度优先搜索。并且没有记录已经反转过的状态,这样不可避免的,会重复。所以使用最大的反转次数(2n)来返回上一步(预判断,进入某个状态的时候,先判断是否可能大于2n,如果大于直接return)。
其预判的标准的是,当前状态乱序的次数+当前已反转的次数<2n。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 从三月份找实习到现在,面了一些公司,挂了不少,但最终还是拿到小米、百度、阿里、京东、新浪、CVTE、乐视家的研发岗...
    时芥蓝阅读 43,025评论 11 349
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 180,425评论 25 708
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 137,173评论 19 139
  • |(管道的两边没有空格) 通过管道把前一个命令的输出交给后一个命令继续处理 find seq==sequence...
    养码哥阅读 299评论 0 1
  • 排行榜需求:根据分数进行排序,分数相同时根据时间并列排序。根据分数排序很容易实现: 分数$value相同时,根据时...
    wuxuan94阅读 11,605评论 1 1

友情链接更多精彩内容