首页 > 试题广场 >

折纸问题

[编程题]折纸问题
  • 热度指数:9596 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

请把纸条竖着放在桌⼦上,然后从纸条的下边向上⽅对折,压出折痕后再展 开。此时有1条折痕,突起的⽅向指向纸条的背⾯,这条折痕叫做“下”折痕 ;突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折,对折N次。请从上到下计算出所有折痕的⽅向。

给定折的次数n,请返回从上到下的折痕的数组,若为下折痕则对应元素为"down",若为上折痕则为"up".

测试样例:
1
返回:["down"]
头像 重生之我要当分子
发表于 2025-01-01 15:50:39
解题思路 这是一个折纸问题,可以发现每次折叠会产生规律性的折痕。通过观察可以发现: 每次折叠后,中间是"下"折痕 上半部分是上次折痕的顺序 下半部分是上次折痕的相反顺序 关键点: 每次折叠的折痕数是2^n-1 可以用二叉树表示折痕关系 中序遍历得到从上到下的顺序 左子树都是 展开全文

问题信息

难度:
79条回答 27875浏览

热门推荐

通过挑战的用户

查看代码
折纸问题