折纸问题类似构建完全二叉树

╰半夏微凉° 2022-07-16 09:49 147阅读 0赞

折纸问题

*  热度指数：904时间限制：3秒空间限制：32768K
 *  本题知识点： [递归][Link 1]
 *  [ 算法知识视频讲解][Link 2]

## 题目描述 ##

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

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

测试样例：

1

返回：["down"]

类似构建完全二叉树：

n=1对应最后一次对折出现的折痕，n=n对应第一次对折位置在最中间的折痕

down

down up

down up down up

down up down up down up down up

import java.util.*;
    
    public class FoldPaper {
        public String[] foldPaper(int n) {
            // 折纸类似构建完全二叉树
            List<String> list = new LinkedList<String>();
            fold(n,list,"down");
            String[] rets = new String[(int)(Math.pow(2,n)-1)];
            return list.toArray(rets);
        }
        public static void fold(int n,List<String> list,String s){
            if(n!=0){
                fold(n-1,list,"down");
                list.add(s);
                fold(n-1,list,"up");
            }
        }
    }

[Link 1]: http://www.nowcoder.com/questionCenter?questionTypes=000100&mutiTagIds=591
[Link 2]: http://www.nowcoder.com/courses/1

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 java:二叉树（完全二叉树）

.二叉树节点：包括左子树，右子树。数据。 //二叉树节点类 private static class Node { ...

野性酷女/ 2024年04月17日 19:48/ 0 赞/ 101 阅读

相关二叉树一定是完全二叉树

一、树的概念及其结构 > 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，

朴灿烈づ我的快乐病毒、/ 2023年10月09日 18:59/ 0 赞/ 44 阅读

相关数据结构--二叉树、满二叉树、完全二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E3NzIz

╰+攻爆jí腚メ/ 2023年10月08日 09:22/ 0 赞/ 9 阅读

相关完全二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvbmRh

た入场券/ 2022年08月31日 14:25/ 0 赞/ 189 阅读

相关满二叉树与完全二叉树

满二叉树的特点: 叶子只能出现在最下一层非叶子结点的度一定是2 在同样深度的二叉树中,满二叉树的结点个数一定最多,同时叶子也是最多,下图就是满二叉树: ![20150

红太狼/ 2022年08月07日 14:34/ 0 赞/ 236 阅读

相关折纸问题类似构建完全二叉树

折纸问题热度指数：904时间限制：3秒空间限制：32768K 本题知识点： [递归][Link 1] [ 算法知识视频讲解][Link 2] 题目描述

╰半夏微凉°/ 2022年07月16日 09:49/ 0 赞/ 148 阅读

相关折纸问题

![20180401104610859][] 求解思路: ![20180401104631167][] //折纸问题 public cla

素颜马尾好姑娘i/ 2022年05月28日 07:27/ 0 赞/ 182 阅读

相关判断完全二叉树

完全二叉树的定义: 一棵二叉树，除了最后一层之外都是完全填充的，并且最后一层的叶子结点都在左边。 [https://baike.baidu.com/item/%E5%AE%8

本是古典何须时尚/ 2022年04月15日 00:52/ 0 赞/ 256 阅读

相关满二叉树和完全二叉树

满二叉树一棵深度为k，且有2^k-1个节点的树是满二叉树。另一种定义：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。这两种定义是等价的。

快来打我*/ 2022年02月25日 09:42/ 0 赞/ 295 阅读

相关二叉树、满二叉树、完全二叉树、平衡二叉树（AVL树）

二叉树： -------------------- 二叉树由节点（node）和边组成。节点分为根节点、父节点、子节点。二叉树是每个结点最多有两个子树的树结构。 ![

柔情只为你懂/ 2021年12月23日 23:37/ 0 赞/ 520 阅读