python数据结构（等差数列、k次交换最小整数）

5452. 判断能否形成等差数列

思路：
排序后取前两个数的差，依次检查是否满足等差。
注意提示中给出的数组长度大于等于2，所以不需要考虑边界条件。

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr = sorted(arr)
        num = arr[1] - arr[0]
        pre = arr[1]
        for x in arr[2:]:
            if x - pre != num:
                return False
            pre = x
        return True

5453. 所有蚂蚁掉下来前的最后一刻

思路：
题目一开始看起来还是挺绕的，其实蚂蚁同时改变移动方向可以理解为都没有改变，或者理解为蚂蚁换了身份一直按照既定的方向行走。

class Solution:
    def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
        if len(left) == 0:
            return n-min(right)
        if len(right) == 0:
            return max(left)
        return max(n-min(right),max(left))

5454. 统计全 1 子矩形

思路：
依次遍历每一行，记录从该位置往上1的个数。例如：

• 1 0 1
• 1 1 0
• 1 1 0

每一行的就是 [[1,0,1],[2,1,0],[3,2,0]]
然后我们依次统计每一行为底的矩形的个数。然后按照长度从1到n依次进行统计。

class Solution:
    def cal(self, arr):
        # 计算每一行为底的不同高度的矩形个数
        # max_row为从左到右该点连续1的最大个数
        max_row = [0] * len(arr)
        for i in range(len(arr)):
            if arr[i] == 0:
                max_row[i] = 0
            else:
                max_row[i] = max_row[i-1] + 1
        ans = 0
        # 一次遍历k*l矩形的个数，l为矩形为底的长度，从1到n
        for l in range(1,len(arr)+1):
            for i, m_r in enumerate(max_row):
                if m_r < l:
                    continue
                min_height = min(arr[i-l+1:i+1])
                ans += min_height
        return ans

    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        arr = [0] * n
        res = 0
        for line in mat:
            for i in range(n):
                if line[i] == 0:
                    arr[i] = 0
                else:
                    arr[i] += 1
            res += self.cal(arr)
        return res

5455. 最多 K 次交换相邻数位后得到的最小整数

思路：
直接贪心可以过。从高位开始，遍历k范围内的最小值，取最近的一个交换即可。
可能是数据集太水了，正确解法还不太确定。

class Solution:
    def minInteger(self, num: str, k: int) -> str:
        if k > len(num) **2:
            return ''.join(sorted(num))
        num = list(num)
        for i in range(len(num)):
            if k > 0:
                max_l = min(k+1,len(num)-i)
                min_num = min(num[i:i+max_l])
                if num[i] == min_num:
                    continue
                index = num[i:i+max_l].index(min_num) + i
                tmp = num[i:index]
                num[i] = min_num
                num[i+1:index+1] = tmp
                k -= index - i
            else:
                break
        return ''.join(num)
                

本文地址：https://blog.csdn.net/ykd14/article/details/107142033