算法题

1.一段n个台阶组成的楼梯,小明从楼梯的最底层向最高层处前进,他可以一次迈一阶或两阶,问:他有多少种不同的走法?

def func(n):
  if n==0 or n==1:
        return 1
  else:
        return f(n-1)+f(n-2)

2. 检查给定的链表是否包含循环，包含循环返回1，不包含循环则返回0。同时说明所实现的时间和空间复杂度是多少。

def find_loop(list):
    p1 = p2 = list
    while p2 and p2.pnext:
        p1 = p1.pnext
        p2 = p2.pnext.pnext
        if p1 == p2:
            return 1
    return 0
时间复杂度O(n), 空间复杂度O(1).

3. 按照单词反转给定句子。例如，输入"what is your name"，返回"name your is what"。
   特别提醒：使用python语言者，请不要使用诸如''.split, [::-1]等时间/空间复杂度不是O(1)的函数。java等其他语言类推。

def str_reverse(str,i,j):
    while i<j:
        str[i],str[j]=str[j],str[i]
        i+=1
        j-=1
def sentence_reverse(sentence):
    sent_list = list(sentence)
    i=0
    len_list = len(sent_list)
    while i<len_list:
        if sent_list[i] !=' ':
            start = i
            end=start+1
            while (end<len_list) and (sent_list[end]!=' '):
                end += 1
            str_reverse(sent_list,start,end-1)
            i = end
        else:
            i+=1
    sent_list.reverse()
    return(''.join(sent_list))

4. 打印二叉搜索树的所有叶子节点。请优先思考非递归的方法。最后，就所实现的函数说明时间和空间复杂度。