想去面试？这10道最高频的手撕代码题都会了吗？

正文

请到「今天看啥」查看全文

(end)
else :
return ( -1 )

mid = (start + end)// 2
if arr[mid]>=target:
end = mid
else :
start = mid

print(binary_search([ 1 , 4 , 7 , 8 , 9 , 12 ], 9 ))
print(binary_search([ 1 , 4 , 7 , 8 , 9 , 12 ], 3 ))

输出结果：

4-1

3，爬楼梯

题目形式：有一个楼梯，总共有10级台阶，每次只能走一级或者两级台阶，全部走完，有多少种走法？

题目难度：简单。

出现概率：约20%。爬楼梯问题是手写代码题中的百兽之豹。爬楼梯问题可以用递归来解决，但是如果考虑到时间复杂度，最好用动态规划的思想来处理，这是一个动态规划算法的教科书级别的案例。连个楼梯都爬不明白，这个算法基础令人堪忧啊！

参考代码：

def climb_stairs(n):
    if n==1:
        return 1
    if n==2:
        return 2
    a,b = 1,2
    i = 3
    while i<=n:
        a,b = b,a+b
        i +=1
    return b

print(climb_stairs(10))

输出结果：

89

4，两数之和

题目形式： 寻找列表中满足两数之和等于目标值的元素的下标。例如：arr = [2,7,4,9]，target = 6  则返回 [0,2]，若不存在，返回空列表[]。

题目难度：简单。

出现概率：约20%。两数之和是手写代码题中的百兽之狼。两数之和问题考察候选人对哈希表可以用空间换取时间这个特性的理解。哎呦喂，写个两数之和还整上两重循环了，你这时间复杂度是多少啊？

参考代码：

def sum_of_two(arr,target):
    dic = {}
    for i,x in enumerate(arr):
        j = dic.get(target-x,-1)
        if j != -1:
            return((j,i))
        else:
            dic[x] = i
    return([])

arr = [2,7,4,9]
target = 6
print(sum_of_two(arr,target))

输出结果：

请到「今天看啥」查看全文