某京算法面试题

轻而易举笔试题 F

一、层板等分衣柜

描述：

给定一个高度为 2000mm 的柜子空间，以及 n 个层板距离柜子底部高度，满足移动层板位置

使得层板等分衣柜的空间。计算所有移动层板的顺序。

层板号自下向上依次排列，1，2..n。层板需要考虑空间位置，不能跨层板移动。

示例 1

输入
：
n = 3，zs = 50，60，1000

输出
：

3 2 1

示例 2

输入
：
n = 4，zs = 50，600，700，1000

输出
：

1，4，3，2

4，1，3，2

4，3，1，2

4，3，2，1

提示 1：1 <= n <= 10

提示 2：输出结果需要按小到大排序

解题思路：大体的思路就是，你有几个层板就需要做几次判断，因为你要得到他们的移动顺序，一次判断得到一个，你要知道每次可以移动的层板（这里我写了一个函数返回当前能移动的层板的序号用一个数组存储起来），然后移动完你需要更新数组，讲移动完的删除，新的可以移动的添加，这里我置为-1，为了不影响后面的操作，这里删除会有影响，然后每次移动得到一个值，存进数组里。这个题最大的难点是有多个可以移动的时候你需要选择，因为他要求的不止一个序列，有几个层板我们就需要使用几次for循环，例如第一次若与两种移动方法，我会把这两个可以移动的层板放进数组遍历这个数组，移动完后，更新这个数组，第二次不管有几种，遍历当前数组就好了，以此遍历，有几个层板就遍历几次，每次得到一个移动的层板序号，得到一个次序后，需要将数组还原。其中，有许多可能需要考虑，例如，当移动完后，数组的长度就不再是原来的长度了，所求的序列次数大于第一次能移动的层板数，那么之后第一个层板将不会移动，这时候我的处理办法就是判断他是否需要后面的for循环帮忙，设了一个标志位，让后面的for循环在移动之前先帮助我移动。

# n =int(input("请输入N:"));
n=4;
print("n=",n);
# index =list(map(int,input().split())); #待排序数组
index = [50,600,700,1000]

print("index为",index);
a = 2000;
b = 2000/(n+1);
temp=[];  #目标数组
reslout =[] #能动数组
lastList=[] #结果数组
for o in range(n):
    temp.append(b*(o+1));
print("temp为",temp)
def appendindex(num):
    reslout.append(num + 1);
    # index[num] = temp[num];

def dataInList(a,b,n):          #判断是否在数组内
    flag = False;
    for i in range(n):
        if(b[i]==a):
            flag=True;
    return  flag;

def rest():               
    for i in range(n):
        if(index[i]>temp[i]):
            if(i==0):
                if(dataInList(i+1, reslout, len(reslout)) == False):      #判断是否在函数里
                    appendindex(i);
                    # rest();
            else:
                if(index[i-1]<temp[i]):  #可移动
                    if (dataInList(i+1, reslout, len(reslout)) == False):
                        appendindex(i)
                        # rest();
        elif(index[i]<temp[i]):
            if(i==(n-1)):
                if (dataInList(i+1, reslout, len(reslout)) == False):
                    appendindex(i);
                    # rest();
            else:
                if (dataInList(i+1, reslout, len(reslout)) == False):
                    if(index[i+1]>temp[i]):
                        appendindex(i)
                      # rest();
    print("能动数组为", reslout);
    print("原数组为", index);
def helpNext(reslout):   #返回移动数组中待移动的个数，若大于1.需要后面帮忙
    i =0;
    for i in range(len(reslout)):
        if(reslout[i]!=-1):
            i +=1;
    return i;
def MoveInFact(i):         #实际移动的主要操作
    k = reslout[i] - 1;
    lastList.append(reslout[i]);
    index[k] = temp[k];
    reslout[i] = -1;
    rest();  # 更新能动数组

def runCanMoveList():
    global index;
    flag1=0;
    flag2=0;
    flag3=0;
    for i in range(len(reslout)):   #第一圈  0 /1     bwh =2
        if( reslout[i]!=-1):
            k = reslout[i] - 1;
            lastList.append(reslout[i]);
            index[k] = temp[k];
            reslout[i] = -1;
            rest();
            if(helpNext(reslout)>1):
                help1=True;
                flag1=i;

            for i in range(len(reslout)): #第二圈  0/1/2   j  len(reslout)=3
                if(help1):
                    if (reslout[flag1] != -1):
                        MoveInFact(flag1);
                        # help1=False;
                if ( reslout[i]!=-1 ):
                    MoveInFact(i);
                    if (helpNext(reslout) > 1):
                        help2 = True;
                        flag2 = i;

                    for i in range(len(reslout)): #第三圈 1/1/2   k
                        if (help1):
                            if (reslout[flag1] != -1):
                                MoveInFact(flag1);
                        if (help2):
                            if (reslout[flag2] != -1):
                                MoveInFact(flag2);
                                # help2=False;
                        if (  reslout[i]!=-1):
                            MoveInFact(i);
                            if (helpNext(reslout) > 1):
                                help3 = True;
                                flag3 = i;
                            # if (n == 3):
                            #     print("结果数组:", lastList);
                            #     lastList.clear();
                            #     index = [50, 60, 1000];
                            #     reslout.clear();
                            #     rest()
                            for i in range(len(reslout)): #第四圈
                                if (help1):
                                    if (reslout[flag1] != -1):
                                        MoveInFact(flag1);
                                if (help2):
                                    if (reslout[flag2] != -1):
                                        MoveInFact(flag2);
                                if (help3):
                                    if (reslout[flag3] != -1):
                                        MoveInFact(flag3);
                                        # help3=False;
                                if (reslout[i]!=-1):
                                    MoveInFact(i);
                                    if(n==4):
                                        print("结果数组:", lastList);
                                        lastList.clear();
                                        index=[50,600,700,1000];
                                        reslout.clear();
                                        rest()

rest();
runCanMoveList();

来源：只䀚