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
悔棋（限制悔棋一步） 棧
"""