[数据结构与算法]leetcode 315周赛 解题报告

目录

6204. 与对应负数同时存在的最大正整数

6205. 反转之后不同整数的数目

6219. 反转之后的数字和

6207. 统计定界子数组的数目

?

?

6204. 与对应负数同时存在的最大正整数

给你一个?不包含?任何零的整数数组?nums?，找出自身与对应的负数都在数组中存在的最大正整数?k?。

返回正整数?k?，如果不存在这样的整数，返回?-1?

思路：

两层循环嵌套

class Solution:
    def findMaxK(self, nums: List[int]) -> int:
        ans=[]
        for i in range(len(nums)):
            if nums[i]<0:
                continue
            for j in range(len(nums)):
                if nums[j]==-nums[i]:
                    ans.append(nums[i])
        if ans==[]:
            return -1
        return max(ans)

6205. 反转之后不同整数的数目

给你一个由?正?整数组成的数组?nums?。

你必须取出数组中的每个整数，反转其中每个数位，并将反转后得到的数字添加到数组的末尾。这一操作只针对?nums?中原有的整数执行。

返回结果数组中?不同?整数的数目。

思路：

模拟+去重?

class Solution:
    def countDistinctIntegers(self, nums: List[int]) -> int:
        temp=nums
        for i in range(len(nums)):
 
            s=str(nums[i])[::-1]
  
            k=-1
            for j in range(len(s)):
                if s[j]=='0':
                    continue
                else:
                    k=j
                    break
              
            temp.append(int(s[k:]))

        a=set(temp)
        ans=len(a)

        return ans

6219. 反转之后的数字和

给你一个?非负?整数?num?。如果存在某个?非负?整数?k?满足?k + reverse(k) = num? ，则返回?true?；否则，返回?false?。

reverse(k)?表示?k?反转每个数位后得到的数字。

思路：

模拟?

class Solution:
    def sumOfNumberAndReverse(self, num: int) -> bool:
        if num==0:
            return True
        for i in range(1,num):
            s=str(i)[::-1]
            k=-1
            for j in range(len(s)):
                if s[j]=='0':
                    continue
                else:
                    k=j
                    break
            
            if int(s[k:])+i==num:
                return True
        return False

?

6207. 统计定界子数组的数目

给你一个整数数组?nums?和两个整数?minK?以及?maxK?。

nums?的定界子数组是满足下述条件的一个子数组：

• 子数组中的?最小值?等于?minK?。
• 子数组中的?最大值?等于?maxK?。

返回定界子数组的数目。

子数组是数组中的一个连续部分。

思路：

首先考虑一个简单的情况，nums 的所有元素都在[minK,maxK] 范围内。

在这种情况下，相当于要统计同时包含 minK 和 {maxK}maxK 的子数组的个数。

我们可以枚举子数组的右端点。遍历 nums，记录 minK 上一次出现的位置 minI 和 maxK 上一次出现的位置 maxI，当遍历到 nums[i] 时，如果minK 和 \maxK 之前出现过，则左端点 ≤min(minI,maxI) 的子数组都是合法的，合法子数组的个数为 min(minI,maxI)+1。

同时我们要记录min(minI,maxI)左边最后出现的不在[minK,maxK]?范围之外的nums[i]?的下标I，因为在最外层遍历的过程中，遍历到一个在[minK,maxK]?范围内的节点时，因为题目要求找出满足要求的子数组，所以我们的结果ans要新增min(minI,maxI)?I

如果 min(minI,maxI)?iI<0，则表示在 I右侧 minK 和 maxK 没有同时出现，此时合法子数组的个数为 0。

?

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        min_I,max_I,I=-1,-1,-1
        ans=0
        for i in range(len(nums)):
            if nums[i]==minK: min_I=i
            if nums[i]==maxK: max_I=i
            # if nums[i]>nums[max_I] or nums[i]<nums[min_I]:
            #     I=i
            if not minK <= nums[i] <= maxK: 
                I = i 

            ans+=max(0,min(min_I,max_I)-I)
        return ans

?

?