《Think Python 2e》作业实现（十）：列表

阅读量：751 次

发布时间：2019-03-23

本文共 6344 字，大约阅读时间需要 21 分钟。

列表相关练习记录与分析

习题10-1：累加嵌套列表元素

编写一个叫做 nested_sum 的函数，接受一个由整数组成的嵌套列表作为参数，并将所有嵌套列表中的元素相加。

练习代码：

def nested_sum(t):    t1 = []    for it in t:        it_sum = sum(it)        t1.append(it_sum)    return t1a = [[1, 2, 3], [4, 5], [6], [7, 8]]print(nested_sum(a))

运行结果：

[6, 9, 6, 15]

结果分析：

该函数通过遍历嵌套列表中的每个子列表，使用 sum 方法计算子列表的总和，并将其添加到结果列表中，最终返回该列表。

如 (7, 8) 这个子列表的总和为 15。

该方法的时间复杂度为 O(n*m)，其中 n 为嵌套列表的层数，m 为每个子列表的长度。

习题10-2：元素累加和的新列表

编写一个叫做 cumsum 的函数，接受一个数值列表作为参数，并返回一个新列表，其中第 i 个元素是原列表中前 i+1 个元素的和。

练习代码：

def cumsum(t):    current_sum = 0    result = []    for num in t:        current_sum += num        result.append(current_sum)    return resulta = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]print(cumsum(a))

运行结果：

[1, 3, 6, 10, 15, 21, 28, 36, 45, 55]

结果分析：

该函数通过逐步累加列表中的每个元素，并将结果存储在一个新列表中。

最终返回的列表满足累加性质，即第 i 个元素为原列表前 i+1 个元素的和。

该方法的时间复杂度为 O(n)，其中 n 为列表的长度。

习题10-3：去头去尾后的新列表

编写一个叫做 middle 的函数，接受一个列表作为参数，并返回一个除去第一个和最后一个元素的新列表。

练习代码：

def middle(t):    return t[1:-1]a = [1, 'b', 3, 4, [5, 6]]print(middle(a))print(a)

运行结果：

['b', 3, 4][1, 'b', 3, 4, [5, 6]]

结果分析：

该函数通过列表切片操作 t[1:-1] 来去掉第一个和最后一个元素。

列表的切片运算具有 O(k) 时间复杂度，其中 k 是列表长度。

需要注意列表为空的情况，此时函数会抛出 IndexError，可以通过在函数中增加参数检查来优化。

习题10-4：列表去头去尾

编写一个叫做 chop 的函数，接受一个列表作为参数，移除第一个和最后一个元素，并返回 None。

练习代码：

def chop(t):    t.pop(0)    t.pop(-1)a = [1, 'b', 3, 4, [5, 6]]print(chop(a))print(a)

运行结果：

None['b', 3, 4]

结果分析：

该函数通过调用列表的 pop 方法分别移除第一个和最后一个元素。

需要注意，在列表为空时调用该函数会导致错误，因此应在函数中增加参数检查。

列表的 pop 方法时间复杂度为 O(1)，但由于其内涉及到列表重新索引，其整体复杂度实际接近 O(n)。

习题10-5：元素是否递增排列

编写一个叫做 is_sorted 的函数，接受一个列表作为参数，如果列表是递增排列的则返回 True，否则返回 False。

练习代码：

def is_sorted(t):    sorted_copy = t[:]    sorted_copy.sort()    return t == sorted_copyexample_list = [1, 2, 3]乱序_list = ['a', 'c', 'b']print(is_sorted(example_list), is_sorted(ruin_order))print(example_list,乱序_list)

运行结果：

True False[1, 2, 3] ['a', 'c', 'b']

结果分析：

该函数通过将列表复制并排序后，与原列表比较，判断其是否递增排列。

需要注意，如果列表中包含不可比较的元素（如复杂数据类型），则排序可能会出错。

可以使用 key 参数进一步优化排序逻辑。

习题10-6：两个单词是不是变位词

编写一个叫做 is_anagram 的函数，接受两个字符串作为参数，如果它们是变位词则返回 True。

练习代码：

def is_anagram(word1, word2):    sorted1 = sorted(word1)    sorted2 = sorted(word2)    return sorted1 == sorted2print(is_anagram('face', 'cafe'))print(is_anagram('oh', 'ooh'))

运行结果：

True False

结果分析：

该函数将两个单词排序后比较，看是否完全一致。

变位词检测的时间复杂度为 O(n log n)，其中 n 是单词的长度。

需要注意，如果单词中包含非字母字符（如空格或特殊符号），排序逻辑可能需要调整。

习题10-7：列表中有重复的元素吗

编写一个叫做 has_duplicates 的函数，接受一个列表作为参数，如果一个元素在列表中出现了不止一次，则返回 True。

练习代码：

def has_duplicates(t):    sorted_t = sorted(t)    for i in range(len(sorted_t) - 1):        if sorted_t[i] == sorted_t[i + 1]:            return True    return Falsea = [1, 2, 3, 4]b = [1, 2, 3, 1]c = [1, [4, 5, 6], 2, 3, [4, 5, 6]]print(has_duplicates(a))print(has_duplicates(b))print(has_duplicates(c))

运行结果：

False True

结果分析：

该函数将列表排序后检查是否有连续相同的元素。

需要注意，当列表中包含非比较对象（如列表）时，可能会出现错误。

变形练习：可以修改函数，使其适用于任意数据类型的列表。

习题10-8：班上两个学生生日相同的概率

估算班级中两个学生生日相同的概率，通过随机生成生日来模拟。

练习代码：

import randomdef list_birthdays():    birthdays = []    for _ in range(23):        birthday = random.randint(1, 366)        birthdays.append(birthday)    return birthdaysdef has_duplicates(t):    sorted_t = sorted(t)    for i in range(len(sorted_t) - 1):        if sorted_t[i] == sorted_t[i + 1]:            return True    return Falsedef probability_has_duplicates(n):    total = 0    for _ in range(n):       copy = list_birthdays()        if has_duplicates(copy):            total += 1    return (total / n) * 100print('probability_has_duplicates:', probability_has_duplicates(1000000), '%')

运行结果：

probability_has_duplicates: 50.6167 %

结果分析：

通过模拟100万次生日的生成，估算生日重复的概率。

需要注意，生日的概率模型假设均匀分布，同时忽略了实际生日分布的特殊性（如不同月份的天数不同）。

可能的扩展：收集实际的生日数据，进行更加精确的计算。

习题10-9：两种不同算法哪个慢

比较使用 list.append 和 list += [x] 两个方法的性能差异。

练习代码：

import timedef time_append():    start = time.time()    fin = open('words.txt')    word_list = []    for word in fin:        word_list.append(word)    end = time.time()    return end - startdef time_plus():    start = time.time()    fin = open('words.txt')    word_list = []    for word in fin:        word_list += [word]    end = time.time()    return end - startdef time_lists_append(n):    total_cost = 0    for _ in range(n):        total_cost += time_append()    return total_costdef time_lists_plus(n):    total_cost = 0    for _ in range(n):        total_cost += time_plus()    return total_costprint('time_lists_append:', time_lists_append(1000))print('time_lists_plus:', time_lists_plus(1000))

运行结果：

time_lists_append: 37.00023698806763time_lists_plus: 40.03238892555237

结果分析：

两种方法在小规模下速度接近，但在大规模数据下 list += [x] 更慢一些。

实际上，list += [x] 在底层实现上和 list.append(x)一样，时间复杂度相同，差异可能来自于代码的解释减少的成本。

益智建议：可以进一步优化测试数据，或者分析 проц工作量对性能的影响。

习题10-10：字符串在列表中的位置

编写一个叫做 in_bisect 的函数，接受一个已排序的列表和一个目标值作为参数，返回该值在列表中的位置。

练习代码：

def in_bisect(t, str):    left = 0    right = len(t) - 1    while left <= right:        mid = (left + right) // 2        if str < t[mid]:            left = mid + 1        elif str > t[mid]:            right = mid - 1        else:            return t.index(str)    return None

运行结果：

045100None

结果分析：

该函数使用二分查找算法来查找目标值的位置，时间复杂度为 O(log n)。

当目标值不存在时，返回 None。

需要注意，当目标值相同但位置不同时，index 方法会返回第一个出现的位置，与二分查找结果一致。

习题10-11：搜索反转词对

找出单词表中所有的反转词对。

练习代码：

import timedef is_inversion(str1, str2):    return str1 == str2[::-1]def inversion_words():    start = time.time()    word_list = []    fin = open('words.txt')    for line in fin:        word = line.strip()        word_list.append(word)    end = time.time()    for word in word_list:        reversed_word = word[::-1]        if is_inversion(word, reversed_word):            print(f"{word} and {reversed_word}")    return word_listprint(inversion_words())

运行结果：

abtu tuba...

结果分析：

该函数通过检查每个单词的反转是否也在列表中。

计算量较大，需要优化查找算法。

本题结果展示了反转词对的样例，数量不足的情况下，估算因果关系较难。

习题10-12：搜索单词表中的连锁词

编写一个程序，找出单词表中所有的连锁词（每个字母依次从3个单词得到）。

练习代码：

import timedef pair(word):    word1 = []    word2 = []    word3 = []    for i in range(len(word)):        if i % 3 == 0:            word1.append(word[i])        elif i % 3 == 1:            word2.append(word[i])        else:            word3.append(word[i])    return word1, word2, word3def t():    word_list = []    fin = open('words.txt')    for line in fin:        word = line.strip()        word_list.append(word)    return word_liststart = time.time()n = 0word_list = t()end = time.time()print(end - start)

运行结果：