甜橘子，专注成都网站制作网站设计与营销型网站建设与优化
QQ :532337155
电话：028-86922220
#include "graphics.h"
创新互联拥有十年成都网站建设工作经验,为各大企业提供成都做网站、成都网站建设、成都外贸网站建设服务，对于网页设计、PC网站建设（电脑版网站建设）、成都App制作、wap网站建设（手机版网站建设）、程序开发、网站优化（SEO优化）、微网站、空间域名等，凭借多年来在互联网的打拼，我们在互联网网站建设行业积累了很多网站制作、网站设计、网络营销经验，集策划、开发、设计、营销、管理等网站化运作于一体，具备承接各种规模类型的网站建设项目的能力。
#include "stdio.h"
#define N 10
#define M N*N-4+1 /*堆栈最大值，用来保存路口信息*/
#define UP 1
#define DOWN -1
#define LEFT 2
#define RIGHT -2
#define UP_M man.x-1=0a[man.x-1][man.y] /*人当前位置的上一个位置*/
#define DOWN_M man.x+1Na[man.x+1][man.y]
#define LEFT_M man.y-1=0a[man.x][man.y-1]
#define RIGHT_M man.y+1Na[man.x][man.y+1]
#define ENTER 3 /*岔路的入口*/
#define HAVE 2 /*某条路已经走过*/
struct cross across,stack[M]=;
int top=1;
int PX=70,PY=40;
struct man;
/*迷宫定义，1表示路，可自行更改迷宫的路径，可使全为1，看效果等*/
int a[N][N]={0,0,0,1,1,0,1,1,1,0,
1,1,0,1,0,1,1,0,1,0,
0,1,1,1,1,0,1,1,1,1,
1,0,1,0,1,1,1,0,1,0,
1,1,1,1,0,0,1,1,1,1,
1,0,1,0,1,1,1,0,1,0,
0,0,1,1,1,0,1,1,1,0,
1,1,1,0,1,0,1,0,1,0,
0,0,1,0,1,1,1,0,1,1,
0,1,1,0,0,1,0,0,0,0};
void init_man() /*初始化人的状态，要求迷宫入口须在左侧*/
{int i;setcolor(WHITE);
for(i=0;iN;i++)
if(a[i][0]) {man.x=i;man.y=0;
if(a[i][1]) man.s=RIGHT;
else if(i+1Na[i+1][0]) man.s=DOWN;
else if(i-1=0a[i-1][0]) man.s=UP;
else
return ;}
if(i==N)
}
void show_map() /*显示迷宫*/
{int i,j;
for(i=0;iN;i++)
for(j=0;jN;j++)
if(a[i][j]) {setfillstyle(1,WHITE);
bar(PX+j*20,PY+i*20,PX+j*20+20,PY+i*20+20);}
else {setfillstyle(1,LIGHTBLUE);
bar(PX+j*20,PY+i*20,PX+j*20+20,PY+i*20+20);}
setcolor(BLACK);
for(i=0;iN;i++)
{line(PX+i*20,PY,PX+i*20,PY+20*N);
line(PX,PY+i*20,PX+20*N,PY+i*20);}
}
void show_man(int color)
{
setfillstyle(1,color);
bar(PX+man.y*20+5,PY+man.x*20+5,PX+man.y*20+20-5,PY+man.x*20+20-5);
}
int cross() /*岔路判断*/
{int count=0;
if(UP_M) count++;
if(DOWN_M) count++;
if(LEFT_M) count++;
if(RIGHT_M) count++;
return count;}
void move() /*依据人的移动状态而移动到新位置*/
{
show_man(GREEN);
switch(man.s)
{case UP:man.x-=1;break;
case DOWN:man.x+=1;break;
case LEFT:man.y-=1;break;
case RIGHT:man.y+=1;break;
}
show_man(LIGHTRED);
}
void back() /*回头走*/
{switch(man.s)
{case UP:man.s=DOWN;move();break;
case DOWN:man.s=UP;move();break;
case LEFT:man.s=RIGHT;move();break;
case RIGHT:man.s=LEFT;move();break;
}
}
void go_on() /*为通路且不是岔路时，继续向前走*/
{switch(man.s)
{case UP:if(UP_M) move();
else if(LEFT_M)
else if(RIGHT_M)
break;
case DOWN:if(DOWN_M) move();
else if(LEFT_M)
else if(RIGHT_M)
break;
case LEFT:if(LEFT_M) move();
else if(UP_M)
else if(DOWN_M)
break;
case RIGHT:if(RIGHT_M) move();
else if(UP_M)
else if(DOWN_M)
break;
}
}
int xin() /*判断人当前位置是否是新岔路口*/
{int i;
for(i=1;itop;i++)
if(man.x==stack[i].xman.y==stack[i].y) return i;
return 0;
}
void copy() /*拷贝岔路信息到across结构体*/
{across.x=man.x;
across.y=man.y;
if(UP_M==1) across.up=1;
else across.up=0;
if(DOWN_M==1) across.down=1;
else across.down=0;
if(LEFT_M==1) across.left=1;
else across.left=0;
if(RIGHT_M==1) across.right=1;
else across.right=0;
}
void rukou() /*为岔路设置一个入口*/
{switch(man.s)
{case UP:across.down=ENTER;break;
case DOWN:across.up=ENTER;break;
case LEFT:across.right=ENTER;break;
case RIGHT:across.left=ENTER;break;
}
}
void xuanlu(struct cross *p) /*在岔路时，为人选一条路行走*/
{switch(man.s)
{case UP:if(p-up==1) p-up=HAVE;
else if(p-left==1)
else if(p-right==1)
else
break;
case DOWN:if(p-down==1) p-down=HAVE;
else if(p-left==1)
else if(p-right==1)
else
break;
case LEFT:if(p-left==1) p-left=HAVE;
else if(p-up==1)
else if(p-down==1)
else
break;
case RIGHT:if(p-right==1) p-right=HAVE;
else if(p-up==1)
else if(p-down==1)
else
break;
}
}
push(struct cross *p) /*把新岔路口入栈*/
{stack[top].left=p-left;
stack[top].right=p-right;
stack[top].up=p-up;
stack[top].down=p-down;
stack[top].x=p-x;
stack[top].y=p-y;
top++;
}
int wan(struct cross *p) /*当前人所在的岔路口走完否？*/
{int count=0;
if(p-left==1) count++;
if(p-right==1) count++;
if(p-up==1) count++;
if(p-down==1) count++;
if(count0) return 0;
return 1;
}
void chukou(struct cross *p) /*人从出口出来*/
{if(p-up==ENTER) man.s=UP;
else if(p-down==ENTER) man.s=DOWN;
else if(p-left==ENTER) man.s=LEFT;
else man.s=RIGHT;
}
main()
{int c,k;
int gdriver=DETECT,gmode;
registerbgidriver(EGAVGA_driver);
initgraph(gdriver,gmode,"");
cleardevice();
show_map();
init_man();show_man(LIGHTRED);getch();delay(65000);
do{
switch(c=cross())
{case 1:switch(man.s)
{case UP:if(UP_M) move();
else back();break;
case DOWN:if(DOWN_M) move();
else back();break;
case LEFT:if(LEFT_M) move();
else back();break;
case RIGHT:if(RIGHT_M) move();
else back();break;}
break;
case 2:go_on();break;
case 3:
case 4:k=xin();
if(!k)
else {if(wan(stack[k])) chukou(stack[k]);
else xuanlu(stack[k]);}
move();
break;
}
delay(65000);
}while(!kbhit());
closegraph();}
==================================================
编译环境：tc 2.0
本程序的前提是将迷宫保存在一个二维数组里，可走的地方为0，不可走的地方为1。由于采用回朔算法，不使用递归，所以首先应该建立一个栈来保存路径，路径是用一个一个点来表示的，也就是说栈中保存的是一系列点的列表。
栈节点类型说明：
struct StackNode
{
POINT Point;
struct StackNode *Next, *Prev;//双向链表形式
};
栈结构用一个类（CPointStack）实现，声明如下：
class CPointStack
{
public:
void ClearStack();//清空栈
void InitStack();//初始化栈
bool Pop(POINT pt);//弹出顶端元素，并给出该点的坐标，返回是否弹出成功
bool Push(POINT pt);//将pt点的信息压入栈，返回是否压入成功
CPointStack();
virtual ~CPointStack();
protected:
StackNode *m_psnTop;//栈顶指针
StackNode m_snBottom;//栈底，不保存点信息
};
以下为成员函数实现，都是一些数据结构的操作，应该没什么好说的：
//构造时初始化栈
CPointStack::CPointStack()
{
InitStack();
}
//析构时清空栈
CPointStack::~CPointStack()
{
ClearStack();
}
//将点压入栈(成功返回true,失败返回false)
bool CPointStack::Push(POINT pt)
{
StackNode* NewNode = new StackNode;
//是否返回true主要看这里申请内存是否成功
if(!NewNode)
return false;
NewNode-Point = pt;
NewNode-Prev = m_psnTop;
NewNode-Next = NULL;
m_psnTop-Next = NewNode;
m_psnTop = NewNode;
return true;
}
//将点弹出栈(成功返回true,栈为空则返回false)
bool CPointStack::Pop(POINT pt)
{
if(m_psnTop == m_snBottom)//是否返回true主要看这里栈是否为空
return false;
StackNode *p;
p = m_psnTop;
m_psnTop = m_psnTop-Prev;
pt = p-Point;
delete p;
m_psnTop-Next = NULL;
return true;
}
//初始化栈
void CPointStack::InitStack()
{
m_psnTop = m_snBottom;
m_snBottom.Next = NULL;
m_snBottom.Prev = NULL;
}
//清空栈
void CPointStack::ClearStack()
{
StackNode *p;
while(m_psnTop != m_snBottom)
{
p = m_psnTop;
m_psnTop = m_psnTop-Prev;
delete p;
}
}
接下来设计怎样走出这个迷宫，也就是迷宫算法的主体部分。再次用一个类实现。
在设计这个类时，我考虑到以下几点：
1、迷宫入口和出口的坐标
2、保存迷宫的2维数组
3、获得路径的函数
但是实际设计时由于没有考虑太多问题，只是以设计迷宫算法和解决一个具体迷宫为目的，所以没有考虑动态大小的迷宫，而是将迷宫大小定为601×401。而且在设计迷宫算法后没有将路径顺序输出而是直接在原图中标识（在保存迷宫数据的表中设置经过的点为2而将死路点设置为3）。
这样迷宫类（CGoMaze）的声明为：
class CGoMaze
{
public:
void Go();//寻找路径的函数
POINT m_ptIn;//入口坐标
POINT m_ptOut;//出口坐标
BYTE m_btArrMaze[401][601];//保存迷宫的二维表
CGoMaze();
virtual ~CGoMaze();
};
最后让我们来看一下CGoMaze::Go()这个函数：
我们模仿人走迷宫时的思路，设置一个当前点，一个目标点（下一个要走的点）。初始情况下当前点为入口，终止条件为当前点为出口，这样，我们的函数大概结构就出来了。
在从入口到出口的过程中程序对当前点的上、下、左、右四个点依次进行判断，当发现任一个方向是未走过的区域时，就将当前点指向那个点进行尝试，同时将当前点入栈并做标记。而当4个方向都不通或已走过时，则为死路，标记当前点为死路并从栈中弹出上一个点继续进行尝试，这时因为当前点已被标记为死路，则弹出上一个点时就不会重复这条路，达到寻找正确路径的效果。
Go函数的具体实现如下，其实挺简单的^_^：
void CGoMaze::Go()
{
CPointStack psPath;//保存路径的栈
POINT ptCur = m_ptIn, ptNext;//设置当前点为入口
while(ptCur.x != m_ptOut.x || ptCur.y != m_ptOut.y)//判断是否已经走出
{
ptNext = ptCur;//设置目标点为当前点，便于下面偏移
if(m_btArrMaze[ptCur.y - 1][ptCur.x] == 0)
ptNext.y --;//如果上方是空的，则目标点向上偏移
else if(m_btArrMaze[ptCur.y][ptCur.x - 1] == 0)
ptNext.x --;//如果左边是空的，则目标点向左偏移
else if(m_btArrMaze[ptCur.y + 1][ptCur.x] == 0)
ptNext.y ++;//如果下方是空的，则目标点向下偏移
else if(m_btArrMaze[ptCur.y][ptCur.x + 1] == 0)
ptNext.x ++;//如果右边是空的，则目标点向右偏移
else
{//这里是没有路的状态
m_btArrMaze[ptCur.y][ptCur.x] = 3;//标记为死路
psPath.Pop(ptCur);//弹出上一次的点
continue;//继续循环
}
//如果有路的话会执行到这里
m_btArrMaze[ptCur.y][ptCur.x] = 2;//标记当前点为路径上的点
psPath.Push(ptCur);//当前点压入栈中
ptCur = ptNext;//移动当前点
}
}
其实这个部分可以将栈设置为CGoMaze类的成员，然后在Go函数里加上：
psPath.ClearStack();
这样就可以用Timer来演示走迷宫的过程了
#includestdio.h
#includestring.h
#includestdlib.h
#includetime.h
int m,n,num,map[101][101],f[101][101],a[101],b[101],d[2][4]={0,-1,0,1,-1,0,1,0},ans,flag;
void maze()
{
int i,j;
time_t t;
srand(time(t));
for(i=0;im;i++)
for(j=0;jn;j++)
{
map[i][j]=rand()%2;
if(map[i][j])
num++;
}
if(numm*n/2)
{
for(i=0;im;i++)
for(j=0;jn;j++)
if(!map[i][j])
map[i][j]+=rand()%2;
}
map[0][0]=1;
map[m-1][n-1]=1;
}
void print()
{
int i,j;
for(i=0;im;i++)
for(j=0;jn;j++)
{
printf("%d ",map[i][j]);
if(j==n-1)puts("");
}
}
void dfs(int x,int y)
{
int i,tx,ty;
if(!flag)
return;
for(i=0;i4;i++)
{
tx=x+d[0][i];
ty=y+d[1][i];
if(!f[tx][ty]tx=0ty=0txmtynmap[tx][ty])
{
f[tx][ty]=1;
a[ans]=tx;
b[ans++]=ty;
if(tx+ty==0)
{
printf("(%d,%d)\n",m,n);
for(flag=i=0;ians;i++)
printf("(%d,%d)\n",a[i]+1,b[i]+1);
return;
}
dfs(tx,ty);
f[tx][ty]=0;
ans--;
}
}
}
int main()
{
while(scanf("%d%d",m,n),m+n)
{
memset(f,0,sizeof(f));
num=ans=0;
flag=1;
maze();
print();
dfs(m-1,n-1);
if(flag)
puts("There is no path");
}
return 0;
}
很久以前做的，现在都忘记了。你看一下吧。我的报告，也可以发给你，不过还是期望你自己可以学会怎么做，少年智则国智。C＋＋和C一回事，你把其中的语法规则改一下就好，比如输入输出语句，将结构体改成类，也可不改，都支持的。
#include "stdio.h"
#include "conio.h" /*provide the support of getch */
#define max 10
#define maxlength (max*max) /*the max lenth of the path*/
#define zdir 4 /*the total direction*/
#include "graphics.h" /*provide the support of graphics*/
#include "dos.h" /* provide the support of function:sleep */
#include "time.h" /* provide the support of sleep */
#define M 10 /*the max lenth of the map*/
#define N 10 /*the max lenth of the map*/
/*the following four function are stating functions*/
void printmap(void);
int zfindpath(int row,int col,int erow,int ecol);
void creategraphich(int n1,int n2,int n3,int n4);
void creategraphich(int n1,int n2,int n3,int n4);
int zmap[max][max]={ {1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
struct {
int row,col;
}offsets[zdir]={{0,1 },
{1,0 },
{0,-1},
{-1,0}
};
struct {
int row;
int col;
} path[maxlength];
/*define a globle variable to convenience output*/
int len;
int zfindpath(int row,int col,int erow,int ecol)
{
int dir,row2,col2;
/* int x=150+col*22,y=100+row*22; */
sleep(1);
setcolor(10); /* draw a cirlce */
setfillstyle(1, 14);
circle(150+(col)*22+10,100+(row)*22+10, 8);
floodfill(150+(col)*22+10+4, 100+(row)*22+10+4, 10);
if((row==erow)(col==ecol))
{ path[0].row=erow;
path[0].col=ecol; /* judge if is the exit */
return 1;
} /* the end of if */
zmap[row][col]=2; /* block current position */
for(dir=0;dirzdir;dir++)
{
row2=row+offsets[dir].row; /* step to next space */
col2=col+offsets[dir].col;
if(zmap[row2][col2]==0) /* mean the way could go at this stage */
{
len=zfindpath(row2,col2,erow,ecol);
if(len0)
{
path[len].row=row2; /* use recursion to find the path */
path[len].col=col2;
return ++len;
} /*the end of if */
} /*the end of if */
} /* the end of for */
sleep(1);
setfillstyle(1, 15);
bar( 150+col*22,100+row*22,170+col*22,120+row*22);
/* sleep(1); */
return 0;
} /* the end of zfindpaht */
void printmap() /* first ,print the map that we will go */
{
int i,j;
for(i=0;imax;i++)
{
for(j=0;jmax;j++)
printf(" %d",zmap[i][j]);
printf("\n");
}
getch();
}
void createmap(int n1,int n2,int n3,int n4)
{
int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22;
void *buf;
int gdriver=DETECT,gmode=VGAHI;
initgraph(gdriver,gmode,"c:\\tc");
cleardevice();
setbkcolor(10);
setcolor(1);
settextstyle(4, 0, 5);
outtextxy(70,20,"hello,welcome to here! ");
setcolor(4);
setfillstyle(1, 4);
for(i=0;i10;i++)
for(j=0;j10;j++)
{
if(zmap[i][j]==1) {setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
else {setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
}
line(100,80,150+n2*22,100+n1*22); /* draw a line */
line(337+(n4-8)*22,287+(n3-8)*22,337,360);
setcolor(1);
settextstyle(4, 0, 3);
outtextxy(80,60,"this is the entrance! ");
outtextxy(320,360,"this is the exit! ");
}
void creategraphich(int n1,int n2,int n3,int n4)
{
int i,j,size,trow,tcol,x=150+n2*22,y=100+n1*22;
void *buf;
int gdriver=DETECT,gmode=VGAHI;
initgraph(gdriver,gmode,"c:\\tc");
cleardevice();
setbkcolor(10);
setcolor(1);
settextstyle(4, 0, 5);
outtextxy(70,20,"hello,welcome to here! ");
setcolor(4);
setfillstyle(1, 4);
for(i=0;i10;i++)
for(j=0;j10;j++)
{
if(zmap[i][j]==1) {setfillstyle(1, 4); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
else {setfillstyle(1, 15); bar( 150+j*22,100+i*22,170+j*22,120+i*22);/*sleep(1);*/}
}
line(100,80,150+n2*22,100+n1*22); /* draw a line */
line(337+(n4-8)*22,287+(n3-8)*22,337,360);
setcolor(1);
settextstyle(4, 0, 3);
outtextxy(80,60,"this is the entrance! ");
outtextxy(320,360,"this is the exit! ");
setcolor(4); /* draw a circle heart */
setfillstyle(1, 4);
sector(250,350,0,180,20,20); /* draw the upper circle */
sector(290,350,0,180,20,20); /* draw the downer circle */
sector(310,350,180,240,80,76);
sector(230,350,300,360,80,76);
setcolor(10); /* draw a cirlce */
setfillstyle(1, 14);
circle(150+(n2)*22+10,100+(n1)*22+10, 8);
floodfill(150+(n2)*22+10+4, 100+(n1)*22+10+4, 10);
size=imagesize(150+(n2)*22+10-8, 100+(n1)*22+10-8, 150+(n2)*22+10+8, 100+(n1)*22+10+8);
buf=malloc(size);
getimage(150+(n2)*22+10-8, 100+(n1)*22+10-8, 150+(n2)*22+10+8, 100+(n1)*22+10+8,buf);
/*sleep(2);
putimage(192,122 , buf, COPY_PUT); */
for(i=len;i0;i--) /* the total number of the path is len-1 */
{
trow=path[i-1].row-path[i].row;
tcol=path[i-1].col-path[i].col;
sleep(1);
x=x+tcol*22;
y=y+trow*22;
putimage(x,y, buf, COPY_PUT);
}
/* printf the result*/
setcolor(1);
settextstyle(4, 0, 3);
outtextxy(357,287,"sussessfully!!!");
getch();
closegraph();
free((void *)buf);
}
void changemap(int d)
{
FILE *fw;
int i,j;
if(d==1)
{
fw=fopen("c:\\tc\\a.txt","r");
if(!fw) {printf("not found!"); getch();return;}
for(i=0;iM;i++)
{ for( j=0;jN;j++ ) { fscanf(fw,"%d",zmap[i][j]);}
} /* the end of for */
}/* the end of first if*/
else {
fw=fopen("c:\\tc\\b.txt","r");
if(!fw) {printf("not found!"); getch();return;}
for(i=0;iM;i++)
{ for( j=0;jN;j++ ) { fscanf(fw,"%d",zmap[i][j]);}
} /* the end of for */
} /* the end of else */
printf("the map we will follow to search :\n");
for(i=0;iM;i++)
{ for(j=0;jN;j++) { printf(" %d",zmap[i][j]);}
printf("\n");
}
getch();
fclose(fw);
}
main()
{
while(1){
int i,j,n1,n2,n3,n4,n5,n6;
int zch;
/* while(1){ */
len=0;
printf("if you want to use the default map,press 1,if you want to use the spare map,press 2 :\n");
scanf("%d",zch);
if(zch==2)
changemap(1);
/*printmap(); */
else
{
changemap(2);
/* printmap(); */ /* first ,print the map that we will go */
}
printf("please input the startpoint(row,col):\n"); /* input the start point and end point ,those two value should less then 10 and larger then 0*/
scanf("%d%d",n1,n2);
printf("please input the endpoint(row,col):\n");
scanf("%d%d",n3,n4);
n5=n1;
n6=n2;
createmap(n5,n6,n3,n4); /* in this step ,we will create the primitive map */
zfindpath(n1,n2,n3,n4); /* function of searching the path */
path[len].row=n5;
path[len].col=n6;
getch();
closegraph();
printf("the resultant path is \n");
for(i=len;i0;i--)
{
printf("(%d,%d)\n",path[i].row,path[i].col);
} /* the end of for*/
getch();
printf("now,we will create the final graphics of the map:\n"); /* create the final graphics of the map*/
getch();
creategraphich(n5,n6,n3,n4);
} /* the end of while */
} /* the end of main */
给出两个整数n和k，返回从1到n中取k个数字的所有可能的组合
例如：
如果n=4，k=2，结果为
[↵ [2,4],↵ [3,4],↵ [2,3],↵ [1,2],↵ [1,3],↵ [1,4],↵]
这题本身并不是特别的难,但是不同方法的复杂度差很多,而且响应了之前碰到的那句:
最先想到的方式:
方法一:
用走迷宫的思路暴力递归,n个数每一个都可以看做迷宫的一步,有选和不选两种选择:
这种方式表面上像一颗二叉树一样展开n个数有2^n次方种递归,但是对二叉树进行适当裁剪,对不要对枝叶不再扩展,勉强通过了测试55 ms 42.3 MB;
方法二:
层序递归的思路,一层层的去求,求f(n,1),f(n,2),......,f(n,k)----n个数选1个的集合,选2个的集合....k个的集合;这种方式会建立大量的集合;
一开始我这样做,0-k的每一位上有1-n种选择,表面上感觉是k*n的复杂度,但是由于是不重复的,每次为了避免前面选过的数再次被选我用的HashSet不断判断的方式来避免重复加入,最后直接超时了;
方法三:
动态规划的背包思路: dp[i][j]---∑dp[i-1][j]+∑f(dp[i-1][j-1],i);利用前面的结果,二维的一格格的求,(方法二相当于一维的f(n,1)-f(n,2)-f(n,3)-.....-f(n,k),n恒定,一层层的求), 这种方式比方法二快,但比走迷宫暴力并剪枝的方式慢4倍, 213 ms -270.3 MB勉强通过;
( 之前华为那道题两个数组互相交换,最后最小值,那道题则用动态规划转为背包问题最好,映证了那句话:求所有符合的结果用深度递归(及时修剪),求最优结果或结果数量用动态规划; )
方法四:
用DFS深度优先遍历,类似于走迷宫但是每一步横向铺开,方法一的每一步都只考虑两种情况,选和不选,这里直接扩散到 i到n-(k-size)+1 (其中size是前面递归过来的已经选了的情况数;
)中的任意位置,类似于棋盘不只上下左右走了,棋子♟可以跳到任意位置;
在每一次递归前list.add(i),执行go(next)递归之后,又及时的进行删除动作,list.remove(last);只在最后符合要求时clone这个list,并放入结果集合;(不保存中间结果)
最后只用了2ms 42MB;