Python初学者笔记第九期 -- （列表相关操作及列表编程练习题）

第17节课 列表相关操作

无论是内置函数、对象函数，用起来确实很方便，但是作为初学者，你必须懂得它们背后的运行逻辑！

1 常规操作

（1）遍历

arr = [1,2,3,4]
# 以索引遍历:可以在遍历期间修改元素
for index in range(len(arr)):arr[index] = arr[index] ** 2print(arr[index])
print(arr)# 以元素遍历:只能获取元素，不能修改元素值（可变对象除外）
for element in arr:print(element)# 同时遍历角标和元素
for index, element in enumerate(arr):print(f"角标{index}，元素{element}")# 反向遍历
for index in range(len(arr) - 1, -1, -1):print(arr[index])

（2）最值

def min_max(arr:list[int]) -> tuple:min_value = arr[0]max_value = arr[0]for i in range(1, len(arr)):if arr[i] > max_value:max_value = arr[i]if arr[i] < min_value:min_value = arr[i]return min_value, max_valuearr = [2,9,8,1,7,4,6,3,5]
min_val, max_val = min_max(arr)
print(min_val, max_val)

（3）存在性

arr = [2,9,8,1,7,4,6,3,5] 
#O(n)
def is_exist(arr:list[int], key:int) -> bool:for element in arr:if element == key:return Truereturn Falseprint(is_exist(arr, 10))
print(is_exist(arr, 8))

（4）反转

arr = [1,2,3,4,5,6,7,8,9]
"""
1 2 3 4 5 6 7 8 9lr
"""
def list_reverse(arr:list[int]) -> None:l = 0r = len(arr) - 1while l < r:arr[l], arr[r] = arr[r], arr[l]l += 1r -= 1list_reverse(arr)
print(arr)

（5）乱序

import random
arr = [1,2,3,4,5,6,7,8,9]def list_shuffle(arr):for i in range(len(arr)):j = random.randint(0, len(arr) - 1)arr[i], arr[j] = arr[j], arr[i]list_shuffle(arr)
print(arr)

（6）二维列表

所谓的二维列表，其实本质上就是一个一维列表，只不过该一维列表中的每一个元素为其他的一维列表

def print_matrix(matrix):for i in range(len(matrix)):for j in range(len(matrix[i])):print(matrix[i][j], end = ' ')print()
# 直接填值创建二维列表
matrix = [[1,2,3], [4,5,6], [7,8,9]]
print(len(matrix))
print(len(matrix[1]))
print_matrix(matrix)
matrix = [[1,2,3,4],[1,2,3],[1,2],[1]
]
print_matrix(matrix)# 循环创建二维列表 指定默认值 0
rows = 3
cols = 5
matrix = []
for i in range(rows):row = [0] * colsmatrix.append(row)
matrix[2][2] = 6
print_matrix(matrix)# 列表推导式创建二维列表
matrix = [[0] * cols for _ in range(rows)]
matrix[2][2] = 6
print_matrix(matrix)matrix = [ [i + j for j in range(cols)] for i in range(rows)]
print_matrix(matrix)

2 查找操作

（1）二分查找

前提数据必须是有序的（升序、降序）

# 返回的是元素key在arr中的角标 如果不存在则返回-1
def binary_search(arr, key): #O(log n)left = 0right = len(arr) - 1mid = (left + right) // 2while arr[mid] != key:if arr[mid] < key:left = mid + 1elif key < arr[mid]:right = mid - 1if left > right:return -1# 重新更新mid的值mid = (left + right) // 2return mid# 顺序查找
def linear_search(arr, key):for index in range(len(arr)):if arr[index] == key:return indexreturn -1# arr = [1,2,3,4,5,6,7,8,9]
# key = 6
# print(binary_search(arr, key))
"""
n/2/2/2/2/..../2 = 1
n/2^x = 1
n = 2^x
x = logn
"""
arr = []
for i in range(70000000):arr.append(i)
key = 69999999
print("数据创建完毕...")
print(binary_search(arr, key))
print(linear_search(arr, key))

（2）插值查找

前提数据必须是有序的（升序、降序），它是二分查找的升级版本

# mid = (key - arr[left]) / (arr[right] - arr[left]) * (right - left) + left
# 当数据分布比较均匀的时候 大致满足等差序列的情况 性能要比二分查找要优秀
def interpalotion_search(arr, key):count = 0left = 0right = len(arr) - 1mid = 0# mid = int((key - arr[left]) / (arr[right] - arr[left]) * (right - left)) + left# while arr[mid] != key:#     count += 1#     if arr[mid] < key:#         left = mid + 1#     elif key < arr[mid]:#         right = mid - 1#     if left > right:#         mid  = -1#         break#     mid = int((key - arr[left]) / (arr[right] - arr[left]) * (right - left)) + leftwhile True:count += 1mid = int((key - arr[left]) / (arr[right] - arr[left]) * (right - left)) + left# key本身在范围外 没找到if mid < left or mid > right:mid = -1breakif arr[mid] < key:left = mid + 1elif key < arr[mid]:right = mid - 1else:break# 在范围内没找到if left > right:mid  = -1breakprint(f"插值查找count={count}")return middef binary_search(arr, key): #O(log n)count = 0left = 0right = len(arr) - 1mid = (left + right) // 2while arr[mid] != key:count += 1if arr[mid] < key:left = mid + 1elif key < arr[mid]:right = mid - 1if left > right:mid = -1break# 重新更新mid的值mid = (left + right) // 2print(f"二分查找count={count}")return mid
# int((20 - 1)/(20-1) * (19 - 0)) + 0 = 19
# int((100 - 1)/(20 - 1) * (19 - 0))+ 0 = 99
# int((-100 - 1)/(20 - 1)*(19-0)) + 0 = - 101
arr= [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
key = -100
print(binary_search(arr, key))
print(interpalotion_search(arr, key))

3 排序操作

希尔排序、堆排序、快速排序、归并排序、计数排序、基数排序、桶排序

（1）选择排序

# 选择排序 O(n^2)
"""
从前往后 每一个元素都要跟其后面的其他元素作比较
如果出现左大右小 则进行交换
"""
def selection_sort(arr):for i in range(len(arr) - 1): # 少一轮for j in range(i + 1, len(arr)):if arr[i] > arr[j]:arr[i], arr[j] = arr[j], arr[i]
arr = [5,2,3,1,4]
selection_sort(arr)
print(arr)

（2）冒泡排序

# 冒泡 O(n^2)
"""
从前往后 元素之间两两进行比较 
如果左大右小则交换
"""
def bubble_sort(arr):# 0 1 2 3for i in range(len(arr) - 1): #-1 少一轮for j in range(len(arr) - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]arr = [5,2,3,1,4]
bubble_sort(arr)
print(arr)

（3）插入排序

# 选择 O(n^2)
def insertion_sort(arr):# 从第2个元素开始遍历for i in range(1, len(arr)):j = iwhile j > 0 and arr[j - 1] > arr[j]:arr[j - 1], arr[j] = arr[j], arr[j - 1]j -= 1
arr = [5,2,3,1,4]
insertion_sort(arr)
print(arr)

根据循环的特性来去解决特定的问题，而不是学习循环本身，学算法思想！

循环之间的好坏其实也有区别，主要在于数据的分布情况

（1）大致升序

（2）大致降序

（3）趋于稳定（方差小，相等值比较多）

（4）完全随机

用time模块记录一下运行时间

第18节课 【列表编程练习题】

练习01 计算数字的出现次数

题目描述

读取1到100之间的整数，然后计算每个数出现的次数

输入输出描述

输入两行，第一行为整数的个数n，第二行为n个整数

输出多行，每行表示某数及其出现的次数，顺序按照数字从小到大

示例

输入：

9

2 5 6 5 4 3 23 43 2

输出：

2出现2次

3出现1次

4出现1次

5出现2次

6出现1次

23出现1次

43出现1次

# 思路1 借助Python自带功能去做
# def sovle(arr, n):
#     arr.sort() #O(n*logn)
#     for index in range(len(arr)):
#         num = arr[index]
#         # 对于第一个数字特殊处理
#         # 与前一个数字不相等 第一次出现
#         if index == 0 or num != arr[index - 1]:
#             print(f"{num}出现{arr.count(num)}次")# 思路2 排序后 连续做比较
"""
num = 5
count = 2i1 1 1 2 2 3 3 3 4 5 5j
1=>3
2=>2
3=>3
4=>1
5=>1
"""
# def sovle(arr, n):
#     #O(nlogn)
#     arr.sort()
#     i = 0
#     # O(n)
#     while i < n:
#         num = arr[i] 
#         count = 1
#         j = i + 1
#         while j < n and arr[j] == arr[i]:
#             count += 1
#             j += 1
#         print(f"{num}出现{count}次")
#         print(f"j = {j}")
#         i = j
#         # 因为此题中需要用到 j = len(arr) 所以不能使用range()# 思路3 计数排序 非比较类排序 只针对整数 O(n + m)
# m 为最值之间的距离
# 牺牲空间 换 时间
def sovle(arr, n):# 找最大值和最小值min_value = min(arr) # O(n)max_value = max(arr) # O(n)# 创建计数数组counts = [0] * (max_value - min_value + 1)# 统计每个数字出现的次数for num in arr:  # O(n)index = num - min_valuecounts[index] += 1# 遍历计数数组counts 打印每个数字出现的次数for index in range(len(counts)): #O(m)if counts[index] != 0:num = index + min_valueprint(f"{num}出现{counts[index]}")# 追加问题：如何排序好的数据打印出来？1 1 1 2 2 3 3 .......# 搞定输入问题
n = int(input())
arr = list(map(int, input().split(" ")))
sovle(arr, n)

练习02 最大公约数 II

题目描述

输入n个数字，求该n个数字的最大公约数

输入输出描述

输入n个数字

输出最大公约数

示例

输入：

9 12 18 21 15

输出：

3

def gcd(arr):min_value = min(arr)for i in range(min_value, 0, -1):for num in arr:if num % i != 0:breakelse:return i 
arr = list(map(int, input().split(" ")))
print(gcd(arr))

练习03 按奇偶排序数组

题目描述

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

输入输出描述

输入数组长度n，接下来输入n个整数

输出排序后的数组

示例

输入：

4

3 1 2 4

输出：

2 4 3 1

解释：

[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案

# 思路1 创建新的数组 分开存奇偶 然后合并
"""
1 2 3 4 5 6 7 8
arr1 = 2 4 6 8
arr2 = 1 3 5 7
arr1 + arr2
""" 
# 时间O(n) 空间S(n)
# def sovle(arr:list[int], n:int) -> list[int]:
#     arr1 = []
#     arr2 = []
#     for num in arr:
#         if num % 2 == 0:
#             arr1.append(num)
#         else:
#             arr2.append(num)
#     return arr1 + arr2# 思路2 双端队列 表头存偶 表尾存奇
# O(n) S(n)
# def sovle(arr:list[int], n:int) -> list[int]:
#     deque = []
#     for num in arr:
#         if num % 2 == 0:
#             deque.insert(0, num)
#         else:
#             deque.append(num)
#     return deque
# 思路3 选择排序
# O(n^2) S(1)
# def sovle(arr:list[int], n:int) -> list[int]:
#     for i in range(len(arr) - 1):
#         for j in range(i + 1, len(arr)):
#             if arr[i] % 2 == 1 and arr[j] % 2 == 0:
#                 arr[i], arr[j] = arr[j], arr[i]
#                 break
#     return arr# 思路4 双指针
"""
是一种解题的思路 主要针对的是一维数据 数组/链表
同向指针 有两个角标都是从左到右的遍历
对向指针 有两个角标一个从头到尾遍历 另一个从尾到头遍历对数组进行分区间数组有序
快慢指针 同向的 一个走一步 另一走两步
滑动窗口 同向的 关于区间的问题
"""
# O(n) S(1)
# def sovle(arr:list[int], n:int) -> list[int]:
#     left = 0
#     right = len(arr) - 1
#     while left < right:
#         # 左偶右奇
#         if arr[left] % 2 == 0 and arr[right] % 2 == 1:
#             left += 1
#             right -= 1
#         # 左偶右偶
#         elif arr[left] % 2 == 0 and arr[right] % 2 == 0:
#             left += 1
#         # 左奇右奇
#         elif arr[left] % 2 == 1 and arr[right] % 2 == 1:
#             right -= 1
#         # 左奇右偶
#         else:
#             arr[left], arr[right] = arr[right], arr[left]
#     return arr# *思路5 保证元素之间的相对顺序 *排序算法的稳定性*
"""
稳定性
现有一组无序数据 ....4(1).....4(2)....4(3).....
排序后 必须保证 ......4(1)4(2)4(3).....
"""
def sovle(arr:list[int], n:int) -> list[int]:# 冒泡 O(n^2)# for i in range(len(arr) - 1):#     for j in range(len(arr) - 1 - i):#         if arr[j] % 2 == 1 and arr[j + 1] % 2 == 0:#             arr[j], arr[j + 1] = arr[j + 1], arr[j]# 插入 O(n^2)for i in range(1, len(arr)):if arr[i] % 2 == 1:continuej = iwhile j > 0 and arr[j - 1] % 2 == 1:arr[j], arr[j - 1] = arr[j - 1], arr[j]j -= 1return arrn = int(input())
arr = list(map(int, input().split()))
print(sovle(arr, n))

练习04 合并两个有序数组

题目描述

给定两个有序递增的数组A和数组B，将其进行合并成一个新的数组C，且保持有序递增，并输出数组C

输入输出描述

第一行输入数组A的长度n，第二行输入n个元素，第三行输入数组B的长度m，第四行输入m个元素

输出数组C的n+m个元素

示例

输入：

5

1 5 16 61 111

4

2 4 5 6

输出：

1 2 4 5 5 6 16 61 111

# 思路1 合并后排序 O(nlogn) S(n)
# def solve(arr1, arr2):
#     arr3 = []
#     arr3.extend(arr1)
#     arr3.extend(arr2)
#     arr3.sort()
#     return arr3# 思路2 按照从小到大 交叉合并 O(n) S(n)
# def solve(arr1, arr2):
#     length1 = len(arr1)
#     length2 = len(arr2)
#     arr3 = [0] * (length1 + length2)
#     p1 = 0
#     p2 = 0
#     p3 = 0
#     while p3 < len(arr3):
#         if p1 < length1 and p2 >= length2:
#             arr3[p3] = arr1[p1]
#             p1 += 1
#         elif p2 < length2 and p1 >= length1:
#             arr3[p3] = arr2[p2]
#             p2 += 1
#         elif arr1[p1] <= arr2[p2]:
#             arr3[p3] = arr1[p1]
#             p1 += 1
#         else:
#             arr3[p3] = arr2[p2]
#             p2 += 1
#         p3 += 1
#     return arr3# 思路3 同一个数组有两个子区间各自有序 问合并后的结果(原地排序)？
# 归并排序的核心思路
# L-M-R含义是对数组中某一个区间进行合并
def solve(arr, L, M, R):temp = []for i in range(L, R + 1):temp.append(arr[i])p1 = 0p2 = M + 1 - Lp3 = Lwhile p3 <= R:if p1 <= M - L and p2 > R - L:arr[p3] = temp[p1]p1 += 1elif p1 > M - L and p2 <= R - L:arr[p3] = temp[p2]p2 += 1elif temp[p1] <= temp[p2]:arr[p3] = temp[p1]p1 += 1else:arr[p3] = temp[p2]p2 += 1p3 += 1
"""
1 2 3 4 2 3 6 8"""# n = int(input())
# arr1 = list(map(int, input().split(" ")))
# m = int(input())
# arr2 = list(map(int, input().split(" ")))
# arr3 = solve(arr1, arr2)
# print(arr3)# 思路3
arr = [1,2,3,4,2,3,4,5,6,7,8,9,2,3,6,8]
solve(arr, 8, 11, 15)
print(arr)

练习05 数组划分

题目描述

给定一个数组A，将第一个元素$A_0$作为枢纽，并把数组划分成三个区间，第一个区间所有元素$<A_0$，第二个区间所有元素$==A_0$，第三个区间所有元素$>A_0$

例如数组[5,2,9,3,6,8]，划分后的结果为[3,2,5,9,6,8]，第一个区间[3,2]，第二个区间[5]，第三个区间[9,6,8]

结果不唯一，只要保证划分后三个区间的元素特性即可，[2,3,5,9,8,6]、[3,2,5,6,8,9]都可作为上述划分的结果

输入输出描述

第一行输入数组的长度n，第二行输入n个元素

输出划分后的结果

示例

输入：

10

5 1 9 2 5 7 4 5 3 6

输出：

1 2 4 3 5 5 5 9 7 6

# 快速排序的核心思路 O(n) S(1)
def solve(arr,L, R):if L >= R:returnlt = Lgt = R + 1v = arr[L]i = L + 1while i < gt:# 小于vif arr[i] < v:arr[i], arr[lt + 1] = arr[lt + 1], arr[i]lt += 1i += 1# 等于velif arr[i] == v:i += 1# 大于velse:gt -= 1arr[gt], arr[i] = arr[i], arr[gt]arr[L], arr[lt] = arr[lt], arr[L]print(arr)# 同样操作左边区间solve(arr, L, lt - 1)# 同样操作右边区间solve(arr, gt, R)arr = [4,1,6,3,6,8,2,4,6,2,3,6,4,2,4,9,7,5,3,5,3,2,4,5,4,5,4]
solve(arr,0, len(arr) - 1)
print(arr)

练习06 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

输入输出描述

输入数组长度n和目标值target，接下来输入n个元素

输出最小子数组长度

示例

输入：

6 7

2 3 1 2 4 3

输出：

2

解释：

子数组 [4,3] 是该条件下的长度最小的子数组

# 思路1 暴力破解 枚举 O(n^2)
"""
优化思路：
1.过滤没有必要的计算
2.避免重复的计算
"""
"""
def sovle(arr, target):min_length = len(arr) + 1for i in range(len(arr)):cur_sum = 0for j in range(i, len(arr)):sub_arr = arr[i:j + 1]cur_sum += arr[j]if cur_sum >= target:min_length = min(len(sub_arr), min_length)print(sub_arr, cur_sum)breakif min_length != len(arr) + 1:return min_lengthelse:return 0   
""" 
# 思路2  O(n) S(1)
def sovle(arr, target):left = 0right = 0cur_sum = arr[left]min_length = len(arr) + 1while True:if cur_sum < target:right += 1if right >= len(arr):breakcur_sum += arr[right]else:cur_length = right - left + 1min_length = min(cur_length, min_length)cur_sum -= arr[left]left += 1if left > right:breakif min_length == len(arr) + 1:return 0else:return min_length
arr = [2,3,1,2,4,3]
#      i
#        j
target = 7
ret = sovle(arr, target)
print(ret)

练习07 寻找两个正序数组中的中位数

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

输入输出描述

输入m和n，然后分别输入m个元素和n个元素

输出中位数

示例1

输入：

2 1

1 3

2

输出：

2.0

解释：

合并数组 = [1,2,3] ，中位数2

示例2

输入：

2 2

1 2

3 4

输出：

2.5

def solve(nums1, nums2):length1 = len(nums1)length2 = len(nums2)if length1 > length2:return solve(nums2, nums1)if length1 == 0:if length2 % 2 == 1:return nums2[length2 // 2]else:return (nums2[length2 // 2] + nums[length2 // 2 - 1]) / 2result = 0 # 中位数的结果L = 0R = length1curA = 0curB = 0total = length1 + length2while L <= R:curA = (L + R) // 2curB = (total + 1) // 2 - curAL1 = -99999999 if curA == 0 else nums1[curA - 1]R1 = 999999999 if curA == length1 else nums1[curA]L2 = -99999999 if curB == 0 else nums2[curB - 1]R2 = 999999999 if curB == length2 else nums2[curB]if L1 > R2:R = curA - 1elif L2 > R1:L = curA + 1else:if total % 2 == 0:result = (max(L1, L2) + min(R1, R2)) / 2else:result = max(L1, L2)breakreturn resultnums1 = [2,4,6,8]
nums2 = [1,3,5,7,9]
print(solve(nums1, nums2))

练习08 豆机器

题目描述

豆机器，也称为梅花或高尔顿盒子，它是一个统计实验的设备，它是由一个三角形直立板和均匀分布的钉子构成，如下图所示：

小球从板子的开口处落下，每次小球碰到钉子，它就是50%的可能掉到左边或者右边，最终小球就堆积在板子底部的槽内

编程程序模拟豆机器，提示用户输入小球的个数以及机器的槽数，打印每个球的路径模拟它的下落，然后打印每个槽子中小球的个数

输入输出描述

输入两个数据，分别表示小球个数和槽子的个数

输出每个小球经过的路径，和最终每个槽子里小球的个数（因为牵扯随机数，程序结果不唯一，示例仅用于表明题意）

示例

输入：

5 8

输出：

LRLRLRR

RRLLLRR

LLRLLRR

RRLLLLL

LRLRRLR

0 0 1 1 3 0 0 0

import random
# balls球的个数 sluts槽子的个数
def solve(balls, sluts):# 定义槽子这个数组arr = [0] * sluts# 模拟每个球下落的路径for _ in range(balls):# 每个球下落几次？sluts - 1次path = ""# 模拟下落的过程 拼接路径index = 0 # 这个球下落的在槽子中的角标for _ in range(sluts - 1):r = random.randint(0, 1)if r == 0:path += "L"else:path += "R"# 计算小球下落的槽子角标index += 1print(path)arr[index] += 1 # 累加槽子中小球的个数return arrballs, sluts = map(int, input().split(" "))
arr = solve(balls, sluts)
# 画图表示一下 柱状图
# pip list 查看python第三方库
# pip install XXX 安装XXX第三方库
import matplotlib.pyplot as plt
plt.bar(list(range(sluts)), arr)
plt.show()

练习09 四个连续的相同数字

题目描述

给定一个二维数组，判断其中是否有四个连续的相同数字，不管这四个数字是在水平方向、垂直方向还是斜线方向

输入输出描述

输入矩阵的行列n和m

输出YES表示存在，NO不存在

示例

输入：

5 5

5 6 2 1 6

6 5 6 6 1

1 3 6 1 4

3 6 3 3 4

0 6 2 3 2

输出：

YES

def is_lianxu(matrix, row, col):length_row = len(matrix)length_col = len(matrix[row])# 向右if col <= length_col - 4:for c in range(col + 1, col + 4):if matrix[row][col] != matrix[row][c]:breakelse:print(matrix[row][col])return True# 向下if row <= length_row - 4:for r in range(row + 1, row + 4):if matrix[row][col] != matrix[r][col]:breakelse:print(matrix[row][col])return True# 向右下if col <= length_col - 4 and row <= length_row - 4:r = row + 1c = col + 1while r < row + 4 and c < col + 4:if matrix[row][col] != matrix[r][c]:breakr += 1c += 1else:print(matrix[row][col])return True# 向左下if row <= length_row - 4 and col >= 3:r = row + 1c = col - 1while r < row + 4 and c > col - 4:if matrix[row][col] != matrix[r][c]:breakr += 1c -= 1else:print(matrix[row][col])return Truereturn Falsedef sovle(matrix):for row in range(len(matrix)):for col in range(len(matrix[row])):if is_lianxu(matrix, row, col):return Truereturn Falsematrix = [[5,6,2,1,6],[3,5,6,6,1],[1,3,6,1,4],[3,6,3,3,4],[0,6,2,3,2]
]
print(sovle(matrix))

练习10 找出最近距离的一对点

输入一组点的坐标，寻找哪两个点的距离最近。先输入点的个数 n，然后在输入 n 行点坐标。

示例1

输入：

8

-1 3

-1 -1

1 1

2 0.5

2 -1

3 3

4 2

4 -0.5

输出：

(1,1)与(2,0.5)最近

"""
8
-1 3
-1 -1
1 1
2 0.5
2 -1
3 3
4 2
4 -0.5
"""
n = int(input())
points = []
for _ in range(n):point = list(map(float, input().split(" ")))points.append(point)distance = -1
p1 = None
p2 = None# 开始计算两两之间点的距离
for i in range(len(points) - 1):for j in range(i + 1, len(points)):cur_p1 = points[i] # [-1, 3]cur_p2 = points[j] # [-1, -1]cur_dist = ((cur_p1[0] - cur_p2[0]) ** 2 + (cur_p1[1] - cur_p2[1]) ** 2) ** 0.5if distance == -1:distance = cur_distelif cur_dist < distance:distance = cur_distp1 = cur_p1p2 = cur_p2
print(p1)
print(p2)
print(distance)

练习11 探索二维矩阵 I

题目描述

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非递减顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

输入输出描述

输入矩阵的行row和列col，和目标值target

接下来输入row行，每行col个元素

输出是否存在

示例

输入：

3 4 3

1 3 5 7

10 11 16 20

23 30 34 60

输出：

true

# 思路1 先卡区间 再对行进行二分查找
# def binary_search(arr, target):
#     low = 0
#     high = len(arr) - 1
#     mid = (low + high) // 2
#     while arr[mid] != target:
#         if arr[mid] < target:
#             low = mid + 1
#         else:
#             high = mid - 1
#         if low > high:
#             mid = -1
#             break
#         mid = (low + high) // 2
#     return mid# def solve(matrix, target):
#     row = len(matrix) # 行数
#     col = len(matrix[0]) # 列数
#     # 先看是否存在与整个范围内
#     if target < matrix[0][0] or target > matrix[row - 1][col - 1]:
#         return -1, -1
#     for i in range(row):
#         line = matrix[i]
#         if line[0] <= target <= line[col - 1]:
#             return i, binary_search(line, target)
# matrix = [
#     [1,3,5,7],
#     [10,11,16,20],
#     [23,30,34,60]
# ]
# target = 0
# x, y = solve(matrix, target)
# if x == -1 or y == -1:
#     print("不存在")
# else:
#     print(x, y)# 思路2 将全体进行二分查找
def sovle(matrix, target):row = len(matrix) # 行数col = len(matrix[0]) # 列数low = 0high = row * col - 1while low <= high:mid = (high + low) // 2cur = matrix[mid // col][mid % col]if cur == target:return Trueelif cur < target:low = mid + 1else:high = mid - 1return Falsematrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]
]
target = 12
print(sovle(matrix, target))

练习12 拉丁方阵

拉丁方阵是指一个含有n个不同拉丁字母的 n × n 的方阵，每个字母在方阵的每一行和每一列都只出现一次。编写一个程序，程序提示用户输入方阵的大小 n，然后输入一个方阵，检测是否为拉丁方阵。方阵的字母是从A开始的n个字母。

示例1

输入：

4

A B C D

B A D C

C D B A

D C A B

输出：

是拉丁方阵

示例2

输入：

3

A B C

C A B

A C B

输出：

不是拉丁方阵

示例3

输入：

3

A F H

输出：

因为 n = 3，所以字母只能是A、B、C

"""
4
A B C D
B A D C
C D B A
D C A B
"""
def is_lading(matrix, aim):# 取每一行for i in range(len(matrix)):line = matrix[i].copy()line.sort()if line != aim:return False# 取每一列for j in range(len(matrix[0])):line = []for i in range(len(matrix)):line.append(matrix[i][j])line.sort()if line != aim:return Falsereturn Truen = int(input())
matrix = []
for _ in range(n):# "A B C D" => ["A","B","C","D"]matrix.append(input().split(" "))
# 确定查找目标 n = 4 -> ["A","B","C","D"]
aim = [ chr(i + 65) for i in range(n)]
print(is_lading(matrix, aim))

练习13 五子棋游戏

五子棋是一种双人对弈的棋类游戏，双方分别使用黑白两色棋子，在棋盘上交替落子。游戏目标为在棋盘的横向、纵向或斜向任一方向上，使自己的五个同色棋子连成一线。通常先手执黑子，后手执白子，轮流在棋盘的交叉点上放置棋子，先达成五连珠的玩家获胜。

棋盘由纵横各 15 条线交叉组成，形成 225 个交叉点。棋子分为黑、白两色，黑子 113 枚，白子 112 枚。

提示用户每次下棋的坐标即可。

def create_board():board = []for _ in range(15):line = []for _ in range(15):line.append("+")board.append(line)return board
def print_board(board):for i in range(15):for j in range(15):print(board[i][j], end=" ")print()# 具体下棋的逻辑
def down_chess(board, chess, player):x, y = map(int,input(f">>>请{player}下棋：").split(" "))# 下棋之前需要判断一下此处是否已经有棋子了if board[x - 1][y - 1] == "+":board[x - 1][y - 1] = chessprint_board(board)else:print(">>>此处已有棋子，请重新下棋!")down_chess(board, chess, player)def is_game_over(board):for row in range(15):for col in range(15):if board[row][col] != "+":# 向右if col < 11:for c in range(col + 1, col + 5):if board[row][col] != board[row][c]:breakelse:return True# 向下if row < 11:for r in range(row + 1, row + 5):if board[row][col] != board[r][col]:breakelse:return True# 右下if row < 11 and col < 11:r = row + 1c = col + 1while r < row + 5 and c < col + 5:if board[row][col] != board[r][c]:breakr += 1c += 1else:return True# 左下if row < 11 and col > 3:r = row + 1c = col - 1while r < row + 5 and c > col - 5:if board[row][col] != board[r][c]:breakr += 1c -= 1else:return Truereturn Falsedef start_game(board):count = 0while not is_game_over(board):# 将棋子下到棋盘上if count % 2 == 0:down_chess(board, "●", "黑方")else:down_chess(board, "○", "白方")count += 1print(">>>游戏结束！")
def main():# 创建棋盘board = create_board()# 打印棋盘print_board(board)# 开始游戏逻辑start_game(board)main()"""
给棋盘加序号        在print_board加
和棋怎么办          数棋子数
最终谁赢            count
悔棋（限制悔棋一步） 栈
"""