Python实现经典算法

题目形式:手写一下快速排序算法。

题目难度:中等。

出现概率:约50%。手写快排绝对是手撕代码面试题中的百兽之王,掌握了它就是送分题,没有掌握它就是送命题。

参考代码:

def quick_sort(arr,start=0,end=None):
    if end is None:
        end = len(arr)-1
    if end<=start:
        return(arr)
    i,j = start,end
    ref = arr[start]
    while j>i:
        if arr[j]>= ref:
            j = j - 1
        else:
            # 此处使用一行语句交换3个元素的值
            arr[i],arr[j],arr[i+1] = arr[j],arr[i+1],arr[i]
            i = i + 1
    quick_sort(arr,start=start,end = i-1)
    quick_sort(arr,start=i+1,end = end)
    return(arr)

print(quick_sort([1,1,3,3,2,2,6,6,6,5,5,7]))

输出结果:

[1, 1, 2, 2, 2, 3, 5, 5, 6, 6, 6, 7]

2,二分查找

题目形式:手写一下二分查找算法。给定一个有序数组 arr 和一个目标元素 target ,返回该 target 在 arr 中的索引,若不存在,返回-1。

题目难度:简单。

出现概率:约30%。二分查找绝对是手写代码题中的百兽之后,没有妃子可以和她争宠。连个二分查找都写不出来,还来应聘程序员,你是不是对程序员这个职业有什么误解?

参考代码:

nums = [1, 2, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 10, 11, 11, 11,
11, 12, 13, 13, 15, 16, 16, 20, 21, 21, 23, 24, 26,
26, 27, 28, 28, 31, 33, 33, 34, 35, 38, 38, 39, 40,
42, 43, 45, 45, 46, 46, 47, 47, 51, 52, 52, 53, 53,
55, 55, 56, 56, 57, 57, 57, 58, 59, 61, 62, 64, 66,
66, 67, 68, 69, 69, 71, 72, 72, 74, 74, 75, 76, 78,
78, 79, 79, 79, 79, 80, 82, 85, 88, 89, 90, 90, 91,
91, 91, 94, 99, 99]
def find(num,nums):
    mid = len(nums) // 2
    if nums[mid] > num:
        nums = nums[0:mid]
        print(nums)
        find(num, nums)
    elif nums[mid] < num:
        nums = nums[mid+1:]
        print(nums)
        find(num, nums)
    else:
        print('找到了')
        print(nums[mid])
        return nums[mid]
find(40,nums)

输出结果:
[1, 2, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 10, 11, 11, 11, 11, 12, 13, 13, 15, 16, 16, 20, 21, 21, 23, 24, 26, 26, 27, 28, 28, 31, 33, 33, 34, 35, 38, 38, 39, 40, 42, 43, 45, 45, 46, 46, 47]
 [21, 23, 24, 26, 26, 27, 28, 28, 31, 33, 33, 34, 35, 38, 38, 39, 40, 42, 43, 45, 45, 46, 46, 47]
 [38, 38, 39, 40, 42, 43, 45, 45, 46, 46, 47]
 [38, 38, 39, 40, 42]
 [40, 42]
 [40]
找到了
40

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 twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            res = target - nums[i]
            if res in nums and nums.index(res) != i:
                return [i,nums.index(res)]

输出结果:

(0, 2)

5,最大回撤

题目形式:有一个数组,求其中两个数x,y,满足x的索引小于y的索引,使得 x-y 最大。例如 arr = [3,7,2,6,4,1,9,8,5], 最大回撤是6,对应的x=7,y=1。

题目难度:中等。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/af0858b1de81dc21f3c4bc9dfad64eef.html