解题思路

这是一个折纸问题，可以发现每次折叠会产生规律性的折痕。通过观察可以发现：

  1. 每次折叠后，中间是"下"折痕
  2. 上半部分是上次折痕的顺序
  3. 下半部分是上次折痕的相反顺序

关键点：

  1. 每次折叠的折痕数是2^n-1
  2. 可以用二叉树表示折痕关系
  3. 中序遍历得到从上到下的顺序
  4. 左子树都是"down"，右子树都是"up"

算法步骤：

  1. 计算总折痕数
  2. 递归生成折痕序列
  3. 中序遍历获取结果

代码

class FoldPaper {
private:
    int index = 0;
    
    void fold(int level, int n, bool isDown, vector<string>& result) {
        if (level > n) {
            return;
        }
        
        // 处理左子树
        fold(level + 1, n, true, result);
        
        // 处理当前节点
        result[index++] = isDown ? "down" : "up";
        
        // 处理右子树
        fold(level + 1, n, false, result);
    }
    
public:
    vector<string> foldPaper(int n) {
        if (n <= 0) {
            return vector<string>();
        }
        
        // 计算总折痕数
        int len = (1 << n) - 1;
        vector<string> result(len);
        
        // 递归生成折痕
        index = 0;
        fold(1, n, true, result);
        return result;
    }
};

import java.util.*;
public class FoldPaper {
    public String[] foldPaper(int n) {
        if (n <= 0) {
            return new String[0];
        }
        
        // 计算总折痕数
        int len = (1 << n) - 1;
        String[] result = new String[len];
        
        // 递归生成折痕
        fold(1, n, true, result);
        return result;
    }
    
    private int index = 0;
    
    private void fold(int level, int n, boolean isDown, String[] result) {
        if (level > n) {
            return;
        }
        
        // 处理左子树
        fold(level + 1, n, true, result);
        
        // 处理当前节点
        result[index++] = isDown ? "down" : "up";
        
        // 处理右子树
        fold(level + 1, n, false, result);
    }
}

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class FoldPaper:
    def __init__(self):
        self.index = 0
        
    def foldPaper(self, n):
        if n <= 0:
            return []
            
        # 计算总折痕数
        length = (1 << n) - 1  # 等同于 2^n - 1
        result = [""] * length
        
        def fold(level, n, is_down):
            if level > n:
                return
                
            # 处理左子树
            fold(level + 1, n, True)
            
            # 处理当前节点
            result[self.index] = "down" if is_down else "up"
            self.index += 1
            
            # 处理右子树
            fold(level + 1, n, False)
        
        # 开始递归
        self.index = 0
        fold(1, n, True)
        return result

算法及复杂度

  • 算法：递归 + 中序遍历
  • 时间复杂度：，每次折叠产生2倍的折痕
  • 空间复杂度：，存储结果数组