1. 給定2個字符串str1、str2，計算把str1轉變為str2的最小操作數。

可執行的操作有：

• 插入一個字符
• 修改一個字符
• 刪除一個字符

解題：這是一個經典的編輯距離問題，通常使用動態規劃解決。

• 定義dp[i][j]表示將str1的前i個字符轉換為str2的前j個字符所需的最小操作數。
• 初始化：dp[0][j]=j：將空字符變成str2的前j個字符，需要進行j次插入操作；dp[i][0]=i：將str1前i個字符變成空字符需要i次刪除操作。
• 狀態轉移方程：考慮dp[i][j]即str1[0:i]到str2[0:j]的編輯距離。

如果str1[i-1] == str2[j-1]（因為字符串下標從0開始），則最后一個字符相同，不需要操作：

dp[i][j]=dp[i-1][j-1]

如果不同，可以執行三種操作之一，并取最小值：

1）替換：將str1[i-1]替換為str2[j-1]，操作數=1+dp[i-1][j-1]

2）刪除：刪除str1[i-1]，操作數=1+dp[i-1][j]

3）插入：在str1的i位置插入str2[j-1]，操作數=1+dp[i][j-1]

def min_edit_distance(str1,str2):m, n = len(tsr1), len(str2)#創建DP表（m+1）*（n+1）dp = [[0] * (n+1) for _ in range(m+1)]#初始化邊界條件for i in range(m+1):dp[i][0] = ifor j in range(n+1):dp[0][j] = j#填充dp表for i in range(1,m+1):for j in range(i,n+1):if str1[i-1] == str2[j-1]:dp[i][j] = dp[i-1][j-1]else:dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])return dp[m][n]

2. 給定兩個列表first_i = [start_i, end_i],second_j = [start_j, end_j]表示區間，找到兩個區間列表間的交集。

注意：兩個區間列表都是有序的，并且每個列表內的區間可能互相重疊也可能不重疊。

思路：

1）由于兩個列表都是有序的，可以使用兩個指針分別遍歷兩個列表。

2）對于兩個區間A = [startA, endA]和B= [startB, endB]，它們的交集區間為[max(startA, startB), min(endA, endB)]，前提是max?(startA, startB) < min(endA, endB)。

3）然后移動指針，移動結束位置較早的那個區間的指針，因為結束早的區間不可能再和另一個列表中的后續區間有交集。

def interval_intersection(first,second):if not first or not second:return []i, j = 0, 0    #雙指針分別指向兩個列表的當前位置result = []while i < len(first) and j < len(second):#獲取當前比較多兩個區間a_start, a_end = first[i]b_start, b_ens = second[j]#計算可能交集的起始點和結束點start_max = max(a_start,b_start)end_min = min(a_end, b_end)#如果有交集if start_max <= end_min:result.append([start_max, end_min])#移動結束點較小的指針if a_end < b_end:i += 1else:j += 1return result