欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-11-30 14:08:04
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...

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