首页 > 试题广场 >

折纸问题

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

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

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

测试样例:
1
返回:["down"]

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)
n = 1, size = 1: "down",
n = 2, size = 3: "down", "down", "up"
n = 3, size = 7: "down", "down", "up", "down", "down", "up", "up"
可以观察到每次迭代的时候,数组的新size是2*size+1. 前面的部分并没有改变,最中间的值永远是"down",后半部分直接把前面的值翻转一下就可以得到。
class FoldPaper
{
    public string[] foldPaper(intn)
    {
        // write code here
        int length = (2<< n-1) -1;
        string[] result = new string[length]; 
        int size =1;
        result[0] = "down";
        for(int i =2; i <= n; i++) {
            result[size] = "down";
            for(int j = size+1; j < 2* size +1; j++) {
                result[j] = result[2* size - j] =="down"?"up":"down";
            }
            size =2* size +1;
        }
        return result;
    }
}

编辑于 2016-02-21 09:41:28 回复(2)
class FoldPaper {
public:
    vector<string> foldPaper(int n) {
        vector<string> v;         Push(v, n, "down");         return v;
    }
    void Push(vector<string> &v, int n, string s)
    {
        if(n>0)
        {
            Push(v, n-1, "down");
            v.push_back(s);
            Push(v, n-1, "up");         }     }
};

发表于 2017-10-30 00:34:49 回复(0)

我们用一个假想的一维数组来模拟这个满二叉树,如果折叠N次,那么共有 2 N -1条折痕,也就是说,这棵想象中的满二叉树,有 2 N -1个结点。从1开始按层次遍历标号各结点。显然,除根结点外,偶数号结点均为左结点,奇数号结点均为右结点。也就是说,遇到偶数,就输出Down,遇到奇数,就输出Up.

迭代 来实现二叉树的中序遍历即可搞定。

class FoldPaper {
public:
    vector<string> foldPaper(int n) {
        // write code here
        vector<string>result;
        if(n<=0)
            return result;
        int num=pow(2,n)-1;
        int tree=1;
        stack<int> node;
        while(tree<=num||!node.empty())
        {
            while(tree<=num)
            {
                node.push(tree);
                tree*=2;
            }
            tree=node.top();
            node.pop();
            if(tree%2==0||tree==1)
                result.push_back("down");
            else
                result.push_back("up");
            tree=tree*2;
            tree++;
        }
        return result;
    }
};
发表于 2016-05-30 15:37:05 回复(0)
classFoldPaper {
public:
    vector<string> printFoldPaper(inti,intn,bool isDownOrUp){
        if(i>n)
            returndownOrUp;
        printFoldPaper(i+1,n,true);
        if(isDownOrUp)
            downOrUp.push_back("down");
        else
            downOrUp.push_back("up");
        printFoldPaper(i+1,n,false);
        returndownOrUp;
    }
    vector<string> foldPaper(intn) {
        // write code here
        returnprintFoldPaper(1,n,true);
         
    }
private:
    vector<string> downOrUp;
};

发表于 2015-09-12 10:10:36 回复(0)

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)
import java.util.*;

public class FoldPaper {
    ArrayList<String>res = new ArrayList<>();
    public String[] foldPaper(int n) {
        FoldPaper1(n,"down");
        String []result =res.toArray(new String [res.size()]);
        return result;
    }
    /*
    *递归函数,怎么写,需要什么参数?
    *终止条件           层数 n==0
    *递归状态           if 他不是最底层,就先插入左节点,然后是自己,然后是右节点
    *输入参数           层数n,和状态,左边就是"down",右边就是"up",顶层也是"down"
    */
    public void FoldPaper1(int n,String style){
         if(n==0){
             return ;
         }
         FoldPaper1(n-1,"down");
         res.add(style);
         FoldPaper1(n-1,"up");
    }
}
发表于 2018-03-29 12:35:57 回复(0)
 public static String[] foldPaper(int n) {
        int length = (1<<n) - 1 ;
        int middle = length / 2;
        String[] result = new String[length];
        if(n == 1){
            result[0] = "down";
            return result;
        }else{
            result[0] = "down";
            for(int i=1;i<=middle;i=i*2+1){
                result[i] = "down";
                for(int j=i-1;j>=0;j--){
                    int k = i-j;
                    if(result[j].equals("down")){
                        result[i+k] = "up";
                    }else{
                        result[i+k] = "down";
                    }
                }
            }
            return result;
        }
可以先折四下找出规律
1: down
2:down down up
3:  down down up down down up up
4: down down up down down up up down down down up up down up up 
可以找出的规律:
    折痕数为折的次数的2次方-1,所以算出length=(1<<n)-1;
    多折一次,最中间的折痕永远是down,且字符串数组关于中间折痕永远轴对称相反,比如以折2次为例,折痕处为down最中间的一个,然后两边位置互反。
    编程时先将每次中间折痕的下标元素赋值为down,然后将中间游标值往左移以为,在对称轴做对称赋值即可
发表于 2017-09-28 10:27:16 回复(1)
Solution with Java:
public class FoldPaper {
    public String[] foldPaper(int n) {
        if(n <= 0)
            return new String[]{};
        inOrder(n, "down");
        String [] ss = new String[list.size()];
        list.toArray(ss);
        ss[ss.length/2] = "down";    //root node is down
        return ss;
    }
    List<String> list = new ArrayList<String>();
    public void inOrder(int n, String str){
        if(n == 0)
            return ;
        inOrder(n-1, "down");
        list.add(str);
        inOrder(n-1, "up");
    }
}
发表于 2017-08-28 09:27:41 回复(0)
classFoldPaper {
public:
    vector<string> printprocess(inti,intn,bool down){
        if(i>n)
            returnDownUpString;  
        printprocess(i+1,n,true);         
        if(down)
            DownUpString.push_back("down");
        else             
            DownUpString.push_back("up");         
        printprocess(i+1,n,false);         
        returnDownUpString;
    }
    vector<string> foldPaper(intn) {
        // write code here
        returnprintprocess(1,n,true);
    }
private:
    vector<string> DownUpString;
};

编辑于 2017-01-15 16:54:49 回复(0)
构造一颗完全二叉树:
import java.util.*;

public class FoldPaper {
    public String[] foldPaper(int n) {
        // write code here
        List<String> list = new LinkedList<String>();
        fold(n,list,"down");
        String[] strs = new String[(int) (Math.pow(2,n)-1)];
        return list.toArray(strs);
    }

    public static void fold(int n, List<String> list,String str){
        if(n != 0){
            fold(n-1,list,"down");
            list.add(str);
            fold(n-1,list,"up");
        }
    }
}

发表于 2016-09-30 12:32:49 回复(1)
class FoldPaper:
    def foldPaper(self, n):
        return self.foldPapers(n,True)
    
    def foldPapers(self,n,down):
        if n==1:
            return self.foldOnce(down)
        return self.foldPapers(n-1,True) \
        + self.foldOnce(down) + self.foldPapers(n-1,False)
        
    def foldOnce(self,down):
        if down:
            return ["down"]
        else:
            return ["up"]
n=1对应最后一次对折出现的折痕,n=n对应第一次对折位置在最中间的折痕
                                                                    down
                                             down                                    up
                                  down            up                   down           up
                             down   up    down  up         down   up   down  up
编辑于 2015-09-17 14:16:56 回复(0)
简单起见,假设下用d来表示,上用u来表示。

首先,第一次折叠后,序列是d。
第二次折叠后,序列是ddu。
第三次折叠后,序列是ddudduu。
经过分析发现,每次的序列,是在前一次的每个间隔中,以dudu。。。的顺序插入的。
比如:第一次的是d,它有左右两个空位,分别插入d u后就变为了ddu。
          第二次是ddu,从第一个d左边到第三个位置的u右边,共有四个空位,分别插入dudu后,结果是ddudduu 

递归函数如下:
recursion(n)
{
  if n == 1
    return d
  else
    a = recursion(n-1)
    for i = 1 to (2^n - 1)
      if i % 4 == 1
        b[i] = 'd'
      else if i % 4 == 3
        b[i] = 'u'
      else
        b[i] = a[i/2]
    return b[2^n - 1]
}


有不对的地方欢迎批评指正,谢谢。
发表于 2015-09-09 10:01:30 回复(0)

给一个很长很窄的纸条,把纸条竖着放在桌子上,然后从纸条的下边向上方对折1次,压出折痕后展开,此时折痕是凹下去的,也就是突起的方向指向纸条的下方;
如果从纸条的下边向上方对折2次,压出折痕后展开,此时有三条折痕,从上到下依次是:下折痕、下折痕、上折痕;
如果纸条每次都从下边向上方对折,在对折n次之后展开。此时所有折痕突起的方向是什么样的呢?
请写一个函数,输入一个整数代表纸条的对折次数记为fTimes,从上到下依次打印所有折痕的突起方向。
例如:
fTimes = 1
打印:down
fTimes = 2
打印:down down up

提示:折痕其实是二叉树结构。该二叉树的特点是:根节点是下,每一个节点的左节点是下,右节点是上。该二叉树的中序遍历即为答案,但不需要构造一颗二叉树,用递归方法可打印出来。

  1. void  printupdown_core( int  index, int  num, bool  Isdown)  
  2. {  
  3.     if (index==num)  
  4.         return ;  
  5.     printupdown_core(index+1,num,true );  
  6.     if (Isdown)  
  7.             cout<<"down\t" ;  
  8.         else   
  9.             cout<<"up\t" ;  
  10.     printupdown_core(index+1,num,false );  
  11. }  
  12.   
  13. //左节点是“下”,右节点是“上”   
  14. void  printupdown( int  num)  
  15. {  
  16.     if (num<=0)  
  17.         return ;  
  18.     printupdown_core(1,num,true );  
  19.     cout<<"down\t" ;  
  20.     printupdown_core(1,num,false );  
  21. }  
发表于 2015-12-23 20:45:00 回复(3)
classFoldPaper {
public:
    vector<string> foldPaper(intn) {
        // write code here
        vector<string> v;
        pushs(v,n,"down");
        returnv;
    }
    voidpushs(vector<string> &v,intn,string s){
        if(n>0){
            pushs(v,n-1,"down");
            v.push_back(s);
            pushs(v,n-1,"up");
        }
    }
};

发表于 2015-12-12 23:07:45 回复(2)
import java.util.*;

public class FoldPaper {
    private ArrayList<String>res = new ArrayList<>();
    public String[] foldPaper(int n) {
        // write code here
        printProcesses(1,n,true);
        String []str= res.toArray(new String[]{});
        return str;
    }

    public void printProcesses(int n, int N ,boolean down){
        if (n>N){
            return;
        }
        printProcesses(n+1,N,true);
        res.add(down?"down":"up");
        printProcesses(n+1,N,false);
    }

/*    public static void main(String[] args) {
        String[]res = new FoldPaper().foldPaper(3);
        for (String s:res){
            System.out.println(s);
        }
    }*/

}
考察的是二叉树的中序遍历,可以试着折两下子,发现每一次折都会在最新的折痕上下位置出现两个新的折痕,一上一下,上为down,下为up。打印的时候,从上往下打印,类似于二叉树的中序遍历。
编辑于 2018-03-16 11:34:23 回复(1)
public String[] foldPaper(int n) {
		// write code here
		int length = 1;
		for (int i = 0; i < n; i++) {
			length = 2 * length;
		}
		length = length - 1;// 计算折痕数为2^n-1
		String[] fold = new String[length];  if (n == 1) {
			fold[0] = "down";// 只有一个折痕时
			return fold;
		} else if (n > 1) {
			fold[0] = "down";
			for (int j = 1; j <= (length / 2); j = (j * 2) + 1) {
				fold[j] = "down";// 每次第(length+1)/2个折痕都为"down",并根据该折痕为中心点两侧相对
				for (int k = j; k > 0; k--) {
					if (fold[j - k].equals("down")) {
						fold[j + k] = "up";
					} else {
						fold[j + k] = "down";
					}
				}
			}
			return fold;
		} else {
			return null;
	}
  }

编辑于 2016-03-15 23:16:47 回复(2)
递归中序遍历
import java.util.*;

public class FoldPaper {
    public String[] foldPaper(int n) {
        
        List<String> list = new LinkedList<String>();
        listProcess(1,n,true,list);
        int len = (2<< n-1) -1;
        String[] strs = new String[len];
        for(int i=0; i<len; i++){
            strs[i] = list.get(i);
        }
        
        return strs;
    }
    
    public void listProcess(int i, int n, boolean isDown, List<String> list){
        if(i>n){
            return;
        }
        listProcess(i+1,n,true,list);
        list.add(isDown?"down":"up");
        listProcess(i+1,n,false,list);
    }
}
发表于 2017-08-02 09:04:42 回复(0)
我用的是二叉树的中序遍历做的,但是测试用例10通不过,郁闷
import java.util.*;

public class FoldPaper {

public  static void main(String[]args){
foldPaper(6);
}
private static List<String> list = new ArrayList<>();

public static String[] foldPaper(int n) {

Node root = createTree(0, n);
InOrder(root);
int size = (int) Math.pow(2, n) - 1;
String[] result = new String[size];
for (int i = 0; i < size; i++) {
result[i] = list.get(i);
}

return result;
// write code here
}

private static void InOrder(Node node) {
if (node != null) {
InOrder(node.left);
String param;
if (node.data == 0) {
param = "down";
} else {
param = "up";
}
System.out.println(param);
list.add(param);
InOrder(node.right);
} else {
return;
}

}

private static Node createTree(int value, int num) {
Node node = new Node(value);
if (num > 1) {
node.left = createTree(0, num - 1);
node.right = createTree(1, num - 1);
}
return node;
}

private static class Node {

public Node(int value) {
this.data = value;
}

int data;
Node left;
Node right;
}
}

发表于 2016-04-14 15:38:28 回复(1)
想请教一下各位,实在不知道自己这个错在哪里了,在牛客刷题比较少,实际输出不能看到全部?根据正确的代码作为对数器和这个比较,也暂时没发现什么问题,还请各位赐教
import java.util.*;

public class FoldPaper {
    public String[] foldPaper(int n) {
        if (n == 0) return new String[0];
        // write code here
        //就是个中序遍历

        Queue<Node> queue = new LinkedList();
        Node root = new Node("down");
        queue.add(root);
        int height = 1;
                //这里是在用层序遍历建二叉树
        while (true) {
            int num = queue.size();

            while (num > 0) {
                Node cur = queue.poll();
                cur.left = new Node("down");
                queue.add(cur.left);

                cur.right = new Node("up");
                queue.add(cur.right);

                num--;
            }
                        //高度等于n说明建树完毕
            if (++height == n) {
                break;
            }
        }
                //用逗号分隔得到数组
        return inOrder(root).split(",");

    }

    static StringBuilder path = new StringBuilder();
        中序遍历拼接结果,用逗号做分割
    public String inOrder(Node root) {
        if (root == null) return "";
        inOrder(root.left);
        path.append(root.val+",");
        inOrder(root.right);
        return path.toString();
    }
}

class Node {
    String val;
    Node right;
    Node left;
    public Node (String val) {
        this.val = val;
    }
}


编辑于 2022-06-06 18:59:11 回复(0)

问题信息

难度:
78条回答 26436浏览

热门推荐

通过挑战的用户

查看代码