22.10.16 LC周赛 第2至4题
?? 这次周赛终于做出3道题，可惜比我强的太多了！不说废话了，好好总结一下，继续保持学习，今天的每日一题挺有意思，一会去好好看一下！
?
6205. 反转之后不同整数的数目（集合的性质）
题目链接：6205. 反转之后不同整数的数目
题目大意：给你一个由 正 整数组成的数组 nums 。
你必须取出数组中的每个整数，反转其中每个数位，并将反转后得到的数字添加到数组的末尾。这一操作只针对 nums 中原有的整数执行。
返回结果数组中 不同 整数的数目。
例如：
输入：nums = [1,13,10,12,31]
输出：6
解释：反转每个数字后，结果数组是 [1,13,10,12,31,1,31,1,21,13] 。
反转后得到的数字添加到数组的末尾并按斜体加粗表示。注意对于整数 10 ，反转之后会变成 01 ，即 1 。
数组中不同整数的数目为 6（数字 1、10、12、13、21 和 31）。
输入：nums = [2,2,2]
输出：1
解释：反转每个数字后，结果数组是 [2,2,2,2,2,2] 。
数组中不同整数的数目为 1（数字 2）。
- 解题思路：充分运用集合的性质。
- 时间复杂度：构造函数复杂度为
O
(
N
log
?
U
)
O(N \log U)
O(NlogU) ，N为数组长度 U为数组中最大值
- 空间复杂度：构造函数复杂度为
O
(
N
)
O(N)
O(N)
class Solution:
def countDistinctIntegers(self, A: List[int]) -> int:
return len(set(A+[int(str(x)[::-1]) for x in A]))
?
6219. 反转之后的数字和（暴力就成 唔想太多！）
题目链接：6219. 反转之后的数字和
题目大意：给你一个 非负 整数 num 。如果存在某个 非负 整数 k 满足 k + reverse(k) = num ，则返回 true ；否则，返回 false 。
reverse(k) 表示 k 反转每个数位后得到的数字。
例如：
输入：num = 443
输出：true
解释：172 + 271 = 443 ，所以返回 true 。
输入：num = 63
输出：false
解释：63 不能表示为非负整数及其反转后数字之和，返回 false 。
输入：num = 181
输出：true
解释：140 + 041 = 181 ，所以返回 true 。注意，反转后的数字可能包含前导零。
- 解题思路：不要想太多 直接暴力做就行。
- 时间复杂度：构造函数复杂度为
O
(
n
log
?
n
)
O(n \log n)
O(nlogn) ，n为num的数值
- 空间复杂度：构造函数复杂度为
O
(
N
)
O(N)
O(N)
class Solution:
def sumOfNumberAndReverse(self, num: int) -> bool:
return any(i+int(str(i)[::-1])==num for i in range(num+1))
?
6207. 统计定界子数组的数目（索引的关键）
题目链接：6207. 统计定界子数组的数目
题目大意：给你一个整数数组 nums 和两个整数 minK 以及 maxK 。
nums 的定界子数组是满足下述条件的一个子数组：
- 子数组中的 最小值 等于 minK 。
- 子数组中的 最大值 等于 maxK 。
返回定界子数组的数目。子数组是数组中的一个连续部分。
输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。
输入：nums = [1,1,1,1], minK = 1, maxK = 1
输出：10
解释：nums 的每个子数组都是一个定界子数组。共有 10 个子数组。
- 解题思路：关键点在 数组索引上 通过连续子数组的限制 索引起到了非常巨大的作用，单纯使用暴力通过不了10**6左右的数据量。
- 时间复杂度：
O
(
N
)
O(N)
O(N)，N为数组长度
- 空间复杂度：
O
(
1
)
O(1)
O(1)
class Solution:
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
minI,maxI,newI = -1,-1,-1
ans = 0
for i,x in enumerate(nums):
if x==minK: minI = i
if x==maxK: maxI = i
if x < minK or maxK < x: newI = i
if minI != -1 and maxI != -1:
ans += max(0,min(minI,maxI)-newI)
return ans
"""
# 暴力超时
i,j = 0,0
ans = 0
n = len(nums)
for i in range(n):
maxN,minN = nums[i],nums[i]
for j in range(i,n):
if nums[j]<minN:
minN = nums[j]
if nums[j]>maxN:
maxN = nums[j]
if minN == minK and maxN == maxK:
ans += 1
return ans
"""
总结
?? 努力 奋斗！通过3道，第一次达成，不过不是很如意，还有许多路要走，继续学习，不能没有节制的熬夜，身体扛不住，要学会松紧有度的调节自我，挺过这一段非常艰难的时间，You can control your mind and life！
|