算法实战课
查找与排序算法

霍格沃兹测试开发

ceshiren.com

目录

  • 学习价值
  • 知识点梳理
  • 成果展示
  • 实战练习

学习价值

  • 是通过大厂面试的必备硬核能力

    • 算法能力能够准确辨别一个程序员的技术功底是否扎实
    • 算法能力是发掘程序员的学习能力与成长潜力的关键手段
    • 算法能力能够协助判断程序员在面对新问题时，分析并解决问题的能力
    • 算法能力是设计一个高性能系统的必备基础

  • 是升职加薪必备的基础能力

  • 是成为高阶测试开发工程师的必经之路

招聘需求

  • 阿里巴巴招聘需求:

    • 薪资: 20K+
    • 要求: 具备很强的逻辑思维能力和较高的分析、处理问题的能力

  • 字节测试开发实习生招聘需求：

    • 具备较强的逻辑思维能力、沟通协作能力和学习能力

算法的学习技巧

  1. 从简单算法开始刷题练习。
  2. 多画图，理解过程之后，再开始用代码实现。
  3. 先实现再优化。

成果展示

  • 掌握面试常考的查找算法与时间复杂度计算。
    • 顺序查找
    • 二分查找
  • 掌握面试常考的排序算法与时间复杂度计算。
    • 冒泡排序

实战一目标

  • 掌握简单的查找算法实现
  • 掌握时间与空间复杂度复杂度的计算方法
  • 掌握较为复杂的查找算法实现

相关知识点

形式 章节
知识点 顺序查找
知识点 复杂度分析
知识点 二分查找

顺序查找

顺序查找

课堂练习

  • 第一次刷题

统计位数为偶数的数字

复杂度分析

复杂度分析

课堂练习

  1. 根据下面函数要求编写单元测试用例。
  2. 编写一段函数，要求在一个无序列表中查找目标元素，并返回目标元素的索引值，若不存在返回-1。
  3. 计算这段代码的时间复杂度是多少。
# 示例1：

输入: nums = [7,8,2,4,5,79,18,32], target = 5
输出: 4
解释: 5 出现在 nums 中并且下标为 4

# 示例2：

输入: nums = [7,8,2,4,5,79,18,32], target = 55
输出: -1
解释: 55 不存在 nums 中因此返回 -1

二分查找

二分查找

课堂练习

  1. 根据下面函数要求编写单元测试用例。
  2. 编写一段函数，要求在一个有序列表中查找目标元素，并返回目标元素的索引值，若不存在返回-1，尽量使用二分查找法实现。
  3. 计算这段代码的时间复杂度是多少。
# 示例1：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

# 示例2：

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

答案解析

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)
        while low < high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid
        return -1

实战练习一（错误版本）

  • 需求说明
  • 练习思路

需求说明

第一个错误的版本

练习思路

相关知识点

形式 章节
知识点 顺序查找
知识点 二分查找

题目解析

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left < right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left

实战二目标

  • 掌握常见面试题冒泡排序的实现。

相关知识点

形式 章节
知识点 冒泡排序
知识点 递归算法

冒泡排序

冒泡排序

课堂练习

  1. 画出冒泡排序的实现过程。
  2. 根据下面的函数要求编写单元测试用例。
  3. 给定一个无序列表。通过冒泡排序的方式，将其从小到大，升序排列。
  4. 计算这段代码的时间复杂度是多少。

实战三目标

  • 掌握常用算法-递归。

递归算法

递归算法

课堂练习

  1. 求和函数的定义为：sum(n) = 1 + 2 + … + n，其中n为正整数。
  2. 根据上面的函数要求编写单元测试用例。
  3. 使用非递归的方式实现。
  4. 使用递归的方式实现。
  5. 计算这段代码的时间复杂度是多少。

总结