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