题目描述
请把纸条竖着放在桌⼦上,然后从纸条的下边向上⽅对折,压出折痕后再展 开。此时有1条折痕,突起的⽅向指向纸条的背⾯,这条折痕叫做“下”折痕 ;突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折,对折N次。请从上到下计算出所有折痕的⽅向。
给定折的次数n,请返回从上到下的折痕的数组,若为下折痕则对应元素为"down",若为上折痕则为"up".
测试样例:
1
返回:["down"]
题目来源
解题思路
首先我用手头的纸张进行实验,进行对折1,2,3,4次,发现了一些规律。
N次折纸所得的折痕为 2的N次方 +(2的N次方 - 1)。
N次折纸与 N -1 次折纸有明显的继承关系。新增的折痕以先“down”后"up"的方式对前一次的折痕进行补充。
解决方案
package codewars.jul;
import java.util.LinkedList;
public class FoldPaper {
private static String[] next(String[] previous, int fold) {
int n = (int) Math.pow(2, fold);
String[] rs = new String[n + (n - 1)];
int cur = 0;
boolean down = true;
for (int i = 0; i < rs.length; i++) {
if (i % 2 == 1) {
rs[i] = previous[cur++];
}
}
for (int i = 0; i < rs.length; i++) {
if (rs[i] == null) {
if (down) {
rs[i] = "down";
down = false;
} else {
rs[i] = "up";
down = true;
}
}
}
return rs;
}
public String[] foldPaper(int n) {
if (n < 1) {
return new String[0];
}
LinkedList list = new LinkedList();
int pieces = 0;
int count = 0;
if (n == 1) {
list.add("down");
pieces = 2;
count = 1;
return list.toArray(new String[0]);
} else {
return next(foldPaper(n - 1), n - 1);
}
}
public static void main(String[] args) {
FoldPaper obj = new FoldPaper();
String[] arr = obj.foldPaper(4);
for (String str : arr) {
System.out.print(str + " ");
}
}
}