首页 > 试题广场 >

折纸问题

[编程题]折纸问题

热度指数：9511 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

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

测试样例：

返回：["down"]

算法知识视频讲解

Python

TimeMac

Python简单解法：（非递归）（需要有可变数组实现）
折n次为n-1次的折痕结果中左右依次插入‘down’和‘up’
例如：
n=1：['down']
n=2：['down', 'down', 'up']
n=3：['down', 'down', 'up', 'down', 'down', 'up', 'up']
从前往后插缝隙就是先插‘down’，下一个插‘up’
我是从后往前插入缝隙就是先插‘up’，后插入‘down’

class FoldPaper:
    def foldPaper(self, n):
        result = ['down']
        for i in range(n-1):
            for j in range(len(result),-1,-1):
                if j & 1:
                    result.insert(j,'up')
                else:
                    result.insert(j,'down')
        return result

编辑于 2018-10-14 23:41:27 回复(0)

Python

离疏

 # -*- coding:utf-8 -*-
#折痕其实是二叉树结构。该二叉树的特点是：根节点是下，每一个节点的左节点是下，右节点是上，该二叉树的中序遍历即为答案
class FoldPaper:
    def foldPaper(self, n):
        res=[]
        def midTraversal(n, postion):#使用中序遍历
            if n == 0:
                return
            midTraversal(n - 1, "left")
            if postion == "left":
                res.append("down")
            else:
                res.append("up")
            midTraversal(n - 1, "right")
        midTraversal(n,"left")
        return res

编辑于 2018-08-22 16:30:31 回复(0)

Python

华科平凡

python极其简单的解法，使用中序遍历。

class FoldPaper:
    def foldPaper(self, n):
        res = []
        def midTraversal(n, postion):
            if n == 0:
                return
            midTraversal(n - 1, "left")
            if postion == "left":
                res.append("down")
            else:
                res.append("up")
            midTraversal(n - 1, "right")

        midTraversal(n,"left")
        return res

发表于 2017-09-12 11:09:38 回复(1)