请把一张纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。给定一个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向。
[要求]
时间复杂度为)
，额外空间复杂度为)
[编程题]折纸问题
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
printAllFlods(Integer.valueOf(in.nextLine().trim()));
}
public static void printAllFlods(int fTimes) {
if(fTimes<1)
return;
printProcess(1,fTimes,true);
}
public static void printProcess(int index,int n,boolean isDown) {
if(index==n) {
System.out.println(isDown?"down":"up");
return;
}
printProcess(index+1,n,true);
System.out.println(isDown?"down":"up");
printProcess(index+1,n,false);
}
}
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
printAllFlods(Integer.valueOf(in.nextLine().trim()));
}
public static void printAllFlods(int fTimes) {
if(fTimes<1)
return;
printProcess(1,fTimes,true);
}
public static void printProcess(int index,int n,boolean isDown) {
if(index==n) {
System.out.println(isDown?"down":"up");
return;
}
printProcess(index+1,n,true);
System.out.println(isDown?"down":"up");
printProcess(index+1,n,false);
}
}
发表于 2021-11-05 14:04:21
回复(0)
// 时间复杂度O(2^N)，空间复杂度O(N)
#include<iostream>
using namespace std;
void printProcess(int i, int& n, bool down)
{
if (i > n) return ;
printProcess(i + 1, n, true);
cout << (down ? "down" : "up") << endl;
printProcess(i + 1, n, false);
}
int main()
{
int n; cin >> n;
printProcess(1, n, true);
return 0;
}
发表于 2019-10-15 22:42:26
回复(0)
#include <iostream>
#include <cmath>
using namespace std;
//这个解法不符合要求，但是简单
int main() {
int n;
cin >> n;
int size = pow(2, n);
int a[size];
int i = 1;
a[0] = -1;
int len = 1;
for (; i < n; i++) {
a[len] = -1;
for (int j = 1; j <= len; j++) {
a[len + j] = -a[len - j];
}
len = len * 2 + 1;
}
for (int index = 0; index < len; index++) {
if (a[index] == -1) {
cout << "down" << endl;
} else {
cout << "up" << endl;
}
}
return 0;
}
#include <cmath>
using namespace std;
//这个解法不符合要求，但是简单
int main() {
int n;
cin >> n;
int size = pow(2, n);
int a[size];
int i = 1;
a[0] = -1;
int len = 1;
for (; i < n; i++) {
a[len] = -1;
for (int j = 1; j <= len; j++) {
a[len + j] = -a[len - j];
}
len = len * 2 + 1;
}
for (int index = 0; index < len; index++) {
if (a[index] == -1) {
cout << "down" << endl;
} else {
cout << "up" << endl;
}
}
return 0;
}
发表于 2019-10-11 16:22:44
回复(0)
将对折几次的结果写出来看看就能发现规律。其实就是个根节点为down的满二叉树结构，所有的节点都满足左孩子为down，右孩子为up，对折n次就是输出n层树的中序遍历序列。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
private static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
dfs(1, true);
}
private static void dfs(int depth, boolean isLeft) {
if(depth > n) return;
dfs(depth + 1, true);
System.out.println(isLeft? "down": "up");
dfs(depth + 1, false);
}
}
编辑于 2021-11-13 22:27:45
回复(0)
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner s =new Scanner(System.in);
int a =s.nextInt();
int length=(int)Math.pow(2,a)-1;
String[] result=new String[length];
int left=0;
int right=length-1;
boolean n=true;
report(result,left,right,n);
for(int i=0;i<length;i++){
System.out.println(result[i]);
}
}
public static void report(String[] result,int left,int right,boolean n){
if(left>right){
return;
}
int mid =(left+right)/2;
report(result,left,mid-1,true);
if(n){
result[mid]="down";
}else{
result[mid]="up";
}
report(result,mid+1,right,false);
}
}
public class Main{
public static void main(String[]args){
Scanner s =new Scanner(System.in);
int a =s.nextInt();
int length=(int)Math.pow(2,a)-1;
String[] result=new String[length];
int left=0;
int right=length-1;
boolean n=true;
report(result,left,right,n);
for(int i=0;i<length;i++){
System.out.println(result[i]);
}
}
public static void report(String[] result,int left,int right,boolean n){
if(left>right){
return;
}
int mid =(left+right)/2;
report(result,left,mid-1,true);
if(n){
result[mid]="down";
}else{
result[mid]="up";
}
report(result,mid+1,right,false);
}
}
发表于 2022-11-17 17:51:16
回复(0)
#include <iostream>
using namespace std;
void InOrderPrint(int i, int N, bool isDown){
if(i > N)
return;
InOrderPrint(i + 1, N, true);
string s = isDown == true ? "down" : "up";
cout << s << endl;
InOrderPrint(i + 1, N, false);
}
int main(void){
int N;
cin >> N;
InOrderPrint(1, N, true);
return 0;
using namespace std;
void InOrderPrint(int i, int N, bool isDown){
if(i > N)
return;
InOrderPrint(i + 1, N, true);
string s = isDown == true ? "down" : "up";
cout << s << endl;
InOrderPrint(i + 1, N, false);
}
int main(void){
int N;
cin >> N;
InOrderPrint(1, N, true);
return 0;
}
知道是一道二分题，但无从下手的时候
首先把它加框 分成 左子树 + 处理信息 + 右子树
写完后写终止条件
发表于 2021-05-21 10:26:38
回复(0)
发表于 2020-01-08 17:23:40
回复(0)
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
void inPrint(vector<bool>& tree,int index)
{
if (index >= tree.size())return;
inPrint(tree, index * 2 + 1);
printf("%s\n", tree[index]?"up":"down");
inPrint(tree, index * 2 + 2);
}
int main()
{
int count = 0;
scanf("%d", &count);
if (count < 0)
{
printf("-1");
return 0;
}
//true为上，false为下
vector<bool> tree(pow(2, count) - 1, false);
int endIndex = 0;
int curIndex = 0;
while (endIndex < tree.size())
{
bool flag = false;
while (curIndex<=endIndex)
{
if (flag)tree[curIndex] = true;
flag = !flag;
curIndex++;
}
endIndex = 2 * (endIndex + 1);
}
inPrint(tree,0);
}
发表于 2019-08-08 18:55:19
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-10 14:07:45
-
2023-03-05 13:20:13
-
2023-02-23 12:41:36 -
2023-02-16 16:22:55
-
2023-01-25 20:23:44
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
