OD C卷 - 宽度最小的子矩阵

宽度最小的子矩阵 （100）

• 给定一个n行 * m列的矩阵；
• 给定一个k个整数的数组k_list；
• 在n*m的矩阵中找一个宽度最小的子矩阵，该子矩阵包含k_list中所有的整数；
  输入描述：
  第一行输入n,m 两个整数；
  后续n行每行输入 m个数据；
  输入k值；
  输入个整数
  输出描述：
  最小宽度值，若找不到，则输出-1

示例1
输入：
2 5
1 2 2 3 1
2 3 2 3 2
3
1 2 3
输出：
2
说明，
矩阵第0、3列包含了1、2、3；
矩阵第3、4列包含了1、2、3

示例2
输入：
2 5
1 2 2 3 1
1 3 2 3 4
3
1 1 4
输出：
5
思路：

• 滑动的子矩阵
• 从第一列起始，找一个宽度最小的子矩阵；
• 从第二列开始，找一个宽度最小的子矩阵；
• 依次到最后一列…
• 以上的宽度每次取最小值

 
class MinWidth:
    def solution(self, n, m, matrix, k_list):
        k_dict = self.to_dict(k_list)
        min_width = float("inf")
        # 类似双指针
        for start_idx in range(m):
            for end_idx in range(start_idx, m):
                temp_list = []
                # 获取当前子矩阵的所有元素
                for i in range(n):
                    temp_list.extend(matrix[i][start_idx:end_idx+1])
                temp_dict = self.to_dict(temp_list)
                # 集合操作
                flag = True
                for key in k_dict:
                    if key in temp_dict and k_dict[key] <= temp_dict[key]:
                        continue
                    else:
                        flag = False
                        break

                if flag:
                    min_width = min(min_width, end_idx - start_idx + 1)
                    break
        print(min_width)

    def to_dict(self, alist):
        dict_ = {}
        for i in alist:
            dict_[i] = dict_.get(i, 0) + 1
        return dict_


if __name__ == '__main__':
    min_width = MinWidth()

    while True:
        try:
            n, m = list(map(int, input().strip().split()))
            matrix = []
            for i in range(n):
                matrix.append(list(map(int, input().strip().split())))
            k = int(input().strip())
            k_list = list(map(int, input().strip().split()))
            min_width.solution(n, m, matrix, k_list)

        except KeyboardInterrupt:
            break

&nbsp

原文地址：https://blog.csdn.net/weixin_45228198/article/details/140702044

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！