# 求职 算法题：第 77 题 - 爬楼梯

MmoMartin · 2020年06月14日 · 最后由 槽神 回复于 2020年06月18日 · 763 次阅读

1、写一个树的中序排序算法。【这道题固定模式，没啥好玩的，自己去熟悉就可以了，没有下面例子题目有趣】

2、是 Leecode 的第 70. 爬楼梯面试题目：

``````from itertools import permutations
def step_all(n):
total = 0
"""
:param n: 总台阶，每次只走1或2，组合有多少种

:return: all
"""
if n == 1:
return 1
elif n == 2:
return 2
elif n >= 3:
if n % 2 == 0:
step_min = int(n/2)  # 最小的step登顶
for i in range(step_min+1, n):
len_i = i  # 长度
count_two = (step_min - (len_i - step_min))
count_one = len_i - count_two
list_step = [2 for x in range(count_two)]
list_step.extend([1 for y in range(count_one)])
li_per = list(permutations(list_step))
count = len(set(li_per))
total += count
elif n % 2 == 1:
total = 0
step_min = int((n-1) / 2) + 1  # 最小的step登顶,step-min为2的个数 3:2  4:1   5:0
for i in range(step_min+1, n):
len_i = i  # 长度
count_two = (step_min - (len_i-(step_min-1)))
print(count_two)
count_one = len_i - count_two
list_step = [2 for x in range(count_two)]
list_step.extend([1 for y in range(count_one)])
li_per = list(permutations(list_step))
count = len(set(li_per))
print(count)
total += count
print(total)
step_min_list = [2 for z in range(step_min-1)]
step_min_list.extend([1 for i in range(1)])
li_per = list(permutations(step_min_list))
step_min_list_count = len(set(li_per))
total = total + step_min_list_count + 1
``````

``````def step_all(n):
def mutil_sum(start_x, end_x=None):
sum_total = 1
if end_x:
print(end_x)
for i in range(start_x, start_x - end_x, -1):
sum_total *= i
return sum_total
for i in range(1, start_x + 1):
sum_total *= i
return sum_total
if n == 1:
return 1
elif n == 2:
return 2
elif n >= 3:
if n % 2 == 0:
total = 0
min_len = int((n / 2))
count_two = min_len
count_one = 0
for i in range(min_len, n):
print("只需%s次爬上楼顶"%(count_two + count_one))
print("2的个数:%s" % count_two)
print("1的个数:%s" % count_one)
if count_two >= count_one:
type_sum = mutil_sum((count_one+count_two), count_two) / mutil_sum(count_two)
total += type_sum
print("只需%s次爬上楼顶的组合数为：%s"%((count_two + count_one), type_sum))
else:
type_sum = mutil_sum((count_one + count_two), count_one) / mutil_sum(count_one)
total += type_sum
print("只需%s次爬上楼顶的组合数为：%s" % ((count_two + count_one), type_sum))
count_two -= 1
count_one += 2
print("只需%s次爬上楼顶" % (count_two + count_one))
print("2的个数:%s" % count_two)
print("1的个数:%s" % count_one)
if count_two >= count_one:
print("%s >= %s"%(count_two,  count_one))
type_sum = (mutil_sum((count_one+count_two), count_two)) / mutil_sum(count_two)
total += type_sum
print("只需%s次爬上楼顶的组合数为：%s" % ((count_two + count_one), type_sum))
else:
type_sum = (mutil_sum((count_one+count_two), count_two)) / mutil_sum(count_one)
total += type_sum
print("只需%s次爬上楼顶的组合数为：%s" % ((count_two + count_one), type_sum))
if n % 2 == 1:
total = 0
min_len = int(((n - 1) / 2)) + 1
count_two = min_len - 1
count_one = 1
for i in range(min_len, n):
print("只需%s次爬上楼顶"%(count_two + count_one))
print("2的个数:%s" % count_two)
print("1的个数:%s" % count_one)
if count_two >= count_one:
type_sum = (mutil_sum((count_one+count_two), count_two)) / mutil_sum(count_two)
total += type_sum
print("只需%s次爬上楼顶的组合数为：%s"%((count_two + count_one), type_sum))
else:
type_sum = (mutil_sum((count_one+count_two), count_one)) / mutil_sum(count_one)
total += type_sum
print("只需%s次爬上楼顶的组合数为：%s" % ((count_two + count_one), type_sum))
count_two -= 1
count_one += 2
print("只需%s次爬上楼顶" % (count_two + count_one))
print("2的个数:%s" % count_two)
print("1的个数:%s" % count_one)
if count_two >= count_one:
type_sum = (mutil_sum((count_one+count_two), count_two)) / mutil_sum(count_two)
total += type_sum
print("只需%s次爬上楼顶的组合数为：%s" % ((count_two + count_one), type_sum))
else:
type_sum = (mutil_sum((count_one+count_two), count_one)) / mutil_sum(count_one)
total += type_sum
print("只需%s次爬上楼顶的组合数为：%s" % ((count_two + count_one), type_sum))

``````

#2 · 2020年06月15日 Author