详解自动化面试常见算法题！！

1、实现一个数字的反转，比如输入12345，输出54321

num = 12345
num_str = str(num)
reversed_num_str = num_str[::-1]
reversed_num = int(reversed_num_str)
print(reversed_num)  # 输出 54321

• 代码解析：首先将输入的数字转换为字符串，然后使用切片操作将字符串反转，最后再将反转后的字符串转换回数字类型。

2、统计在一个队列中的数字，有多少个正数，多少个负数，如[1,3,5,7,0,-1,-9,-4,-5,8]

nums = [1, 3, 5, 7, 0, -1, -9, -4, -5, 8]
positive_count = 0
negative_count = 0

for num in nums:
    if num > 0:
        positive_count += 1
    elif num < 0:
        negative_count += 1

print(f"正数数量：{positive_count}，负数数量：{negative_count}")

• 代码解析：首先定义了一个数字列表 nums，然后用变量 positive_count和negative_count 分别记录其中的正数和负数数量。循环遍历这个列表，对于每个数字，如果它是正数则正数数量加一，否则如果是负数则负数数量加一。最后输出正数和负数数量的统计结果。

3、一个数的阶乘运算，求结果，如求5的阶乘结果。

n = 5  # 求 5 的阶乘
factorial = 1  # 阶乘的初始值为 1

for i in range(1, n+1):
    factorial *= i  # 依次乘以 1, 2, 3, ..., n

print(factorial)  # 输出 120

• 代码解析：首先定义了待求阶乘的数 n，然后将阶乘的初始值设为 1。在循环中，使用 range(1, n+1) 来遍历 1 到 n 这n个数的值。对于每个数，用 factorial 依次乘以它，最终得到的结果即为阶乘。最后输出结果

4、1加到N的阶层之和,比如N=4, result = (1! + 2! + 3! + 4!)

n = 4
factorial_sum = 0  # 1到N的阶层之和
result = 0  # 最终的结果

# 循环计算1到N的阶层之和
for i in range(1, n+1):
    factorial = 1  # 用来记录i的阶层
    for j in range(1, i+1):
        factorial *= j
    factorial_sum += factorial

# 累加到结果中
result += factorial_sum

print(result)  # 输出 33

• 代码解析：首先定义了待求解的数 n 和计算 1 到 N 的阶层之和的变量 factorial_sum。在循环中，使用两层嵌套循环来计算 i 的阶层，然后把所有阶层求和得到 factorial_sum。最后将 factorial_sum 加入到最终结果 result 中。最后输出结果。

5、求出1000以内的完全数

for n in range(2, 1001):
    factors = []  # 用来存储n的因子
    for i in range(1, n):
        if n % i == 0:
            factors.append(i)  # 将i加入到n的因子列表中

    if sum(factors) == n:
        print(n)

• 代码解析：外层循环 for n in range(2, 1001) 遍历所有可能的完全数，即从2到1000。在内层循环 for i in range(1, n) 中，使用 n % i == 0 来判断i是否是n的因子，如果是则将它加入到因子列表 factors 中。在循环结束后，使用 sum(factors) == n 来判断所有因子的和是否等于n，如果是则说明n是完全数，输出它的值即可。
• 完全数是指除自身外所有因子之和等于自身的数。其中最经典的两个完全数是6和28，它们的因子分别是1, 2, 3和1, 2, 4, 7, 14。

6、求出1000以内的水仙花数

for n in range(100, 1000):
    # 将 n 的每一位取出来，计算它们的立方和
    digits = [int(d) for d in str(n)]
    digit_cubes_sum = sum(d ** 3 for d in digits)

    # 如果立方和等于 n，则说明这是一个水仙花数
    if digit_cubes_sum == n:
        print(n)

• 代码解析：外层循环 for n in range(100, 1000) 遍历所有三位数，内层使用了列表推导式和 sum() 函数来计算 n 的每个数字的立方和。在判断时，如果立方和等于 n，说明 n 是一个水仙花数，将它输出即可。
• 水仙花数是指一个 n 位数（n≥3）它的每个位上的数字的 n 次幂之和等于它本身。比如 153 就是一个水仙花数，因为 1^3 + 5^3+ 3^3 = 153.

7、求出1000以内的回文数

for n in range(100, 1000):
    # 将 n 转换为字符串，并将字符串反转后再转成数字
    reversed_n = int(str(n)[::-1])

    # 如果翻转后的数等于 n，则说明 n 是一个回文数
    if reversed_n == n:
        print(n)

• 代码解析：外层循环 for n in range(100, 1000) 遍历所有三位数，将每个数字转换成字符串，然后使用字符串切片 [::-1] 反转它，并将反转后的字符串转回数字。在判断时，如果反转后的数等于 n，则说明 n 是一个回文数，将它输出即可。
• 回文数是指一个数字从左往右和从右往左读都是一样的，比如 121、1221。

8、实现一个数字的斐波那契数列

# 方式一：循环实现
def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a
# 测试代码
n = 10
print([fib(i) for i in range(n)])  # 输出结果为 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# 方式二：递归实现
def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)
# 测试代码
n = 10
print([fib(i) for i in range(n)])  # 输出结果为 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

• 代码解析：

  • **方式一（循环实现）：初始化 a 和 b 为 0 和 1，然后使用 **for 循环遍历 0 到 n-1，每次将 a 和 b 的值更新为 b 和 a+b，最后返回 a。
  • **方式二（递归实现）：首先判断 n 的值是否小于等于 1，如果是，则直接返回 n。否则，递归调用 **fib(n-1) 和 fib(n-2) 并返回它们的和。

• 斐波那契数列是指从 0 和 1 开始，后续每个数都等于前两个数之和的数列。其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

9、统计列表1~9999中包含3的元素的总个数

import re

# 方式一：循环实现
count = 0

# 遍历 1~9999 中的每个数字，将数字转换成字符串并查找其中是否包含字符 3
for i in range(1, 10000):
    if '3' in str(i):
        count += 1

print(count)  # 输出结果为 3439

# 方式二：循环+正则匹配实现
theList = list(filter(lambda x: re.match('(.*?)3(.*?)',str(x)) ,a))
print(f"列表[1~9999]中包含3的元素总个数为:{len(theList)}") # 输出结果为 3439

• 代码解析：
• 方式一（循环）：使用 for 循环遍历 1~9999 中的每个数字，并将每个数字转换成字符串，然后查找其中是否包含字符 3。如果包含，则将计数器加 1。最后，计数器的值就是包含数字 3 的元素的个数
• 方式二（循环+正则匹配）：
  • re.match() 函数用于检查列表 a 中的每个元素是否包含数字3。正则表达式 (.*?)3(.*?) 匹配任何包含数字3的字符串，无论它在字符串中的位置如何。
  • filter() 函数用于创建一个新列表，其中仅包含与正则表达式匹配的 a 中的元素。 lambda 函数用于定义一个简单的函数，它接受一个参数 x ，并且如果 re.match('(.*?)3(.*?)',str(x)) 返回一个匹配对象（即如果 x 包含数字3），则返回 True ，否则返回 False 。 结果列表被赋值给变量 theList 。 - len() 函数用于计算 theList 的长度，这给出了在范围[1, 9999]中包含数字3的元素的总数。

10、写一个冒泡排序的算法程序

def bubble_sort(arr):
    n = len(arr)
    # 遍历 n 次
    for i in range(n):
        # 第 i 次遍历，找出未排序部分的最大元素并将其放到末尾
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            
# 测试代码            
arr = [5, 2, 8, 4, 1]
bubble_sort(arr)
print(arr)  # 输出结果为 [1, 2, 4, 5, 8]

• 代码解析：
  • bubble_sort() 函数接收一个列表 arr，并将其进行冒泡排序。具体实现时，使用两个嵌套的循环对列表中的所有元素进行比较，如果相邻两个元素的顺序相反，则交换它们的顺序，直到整个列表都排好序。
  • **先定义了一个列表 **arr，然后调用 bubble_sort(arr) 对其进行冒泡排序，并输出排序后的结果。
• 冒泡排序是一种基本的排序算法，也是最简单的一种排序算法之一。它的基本思想是：通过重复交换相邻的两个元素来实现排序。具体来说，冒泡排序的过程如下：
  1. 从列表的第一个元素开始，依次比较相邻的两个元素，如果第一个元素大于第二个元素，则交换它们的位置；
  2. 继续比较第二个元素和第三个元素，如果第二个元素大于第三个元素，则交换它们的位置；
  3. 重复上述步骤，直到比较到列表的最后一个元素；
  4. 重复上述步骤，直到列表中的所有元素都按照从小到大的顺序排列为止。

11、用python实现二分法排序

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# 测试代码
arr = [1, 3, 4, 6, 8, 9, 11, 12, 13, 16]
target = 9
pos = binary_search(arr, target)
if pos == -1:
    print("元素不在列表中")
else:
    print("元素在列表中的下标为：", pos)

• 代码解析：
  • binary_search() 函数接收一个有序列表 arr 和一个待查找的元素 target，并返回该元素在列表中的下标（从 0 开始计数）；如果该元素不在列表中，则返回 -1。二分查找算法通过不断地将待查找部分缩小一半来实现查找
  • **有序列表 **arr 和一个待查找的元素 target，然后调用 binary_search(arr, target) 函数查找该元素在列表中的下标，并输出结果。
• 二分查找，也叫二分查找、折半查找，是一种在有序数组中查找某一特定元素的搜索算法。二分查找每次将查找区间减半，直到找到目标元素，或者确定目标元素不存在于数组中。具体来说，二分查找的基本步骤如下：
  1. 首先，令左侧下标 low 等于数组的第一个元素下标，右侧下标 high 等于数组的最后一个元素下标，计算中间下标 mid；
  2. 比较中间下标的值与目标值的大小关系。若相等，则返回中间下标；若小于目标值，则目标值在中间下标的右侧，将 low 置为 mid + 1；否则目标值在中间下标的左侧，将 high 置为 mid - 1；
  3. 重复上述步骤，直到 low 大于 high，表示查找区间为空，返回 -1

12、写一个快排的算法程序

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 选择中间的元素作为基准值
    left = [x for x in arr if x < pivot]  # 小于基准值的放在左边
    mid = [x for x in arr if x == pivot]  # 等于基准值的放在中间
    right = [x for x in arr if x > pivot]  # 大于基准值的放在右边
    return quick_sort(left) + mid + quick_sort(right)

# 测试代码
arr = [5, 2, 8, 4, 1]
arr_sorted = quick_sort(arr)
print(arr_sorted)  # 输出结果为 [1, 2, 4, 5, 8]

• 代码解析：
  • quick_sort() 函数接收一个列表 arr，并返回排序后的新列表。具体实现时，先选择列表中间的元素作为基准值 pivot，然后将列表分成三部分：小于基准值的放在左边，等于基准值的放在中间，大于基准值的放在右边。然后递归地对左、右两个子列表进行排序。
  • **先定义了一个列表 **arr，然后调用 quick_sort(arr) 将其进行快速排序，并输出排序后的结果。
• 快速排序（Quick Sort）是一种常用的排序算法，属于交换排序的一种。其基本思想是：选定一个基准值，将列表分成两个子列表，小于基准值的放在左边，大于或等于基准值的放在右边，然后递归地对左、右两个子列表进行排序，最终将整个列表排序。具体来说，快速排序算法的基本步骤如下：
  1. 确定基准值：选取一个基准值，在列表中选择一个元素作为基准值。
  2. 分割：将列表按照基准值进行分割，小于基准值的放在左边，大于或等于基准值的放在右边。分割后，将列表分成了两个部分，左边部分的所有元素都小于基准值，右边部分的所有元素都大于或等于基准值。
  3. 递归：对左、右两个子列表分别进行快速排序的递归操作，直到排序完成。