企业网站建设之域名篇,做网站都需要学什么,辽宁省建设工程信息网官网电话,网站备案代理3289. 数字小镇中的捣蛋鬼
数字小镇 Digitville 中#xff0c;存在一个数字列表 nums#xff0c;其中包含从 0 到 n - 1 的整数。每个数字本应 只出现一次#xff0c;然而#xff0c;有 两个 顽皮的数字额外多出现了一次#xff0c;使得列表变得比正常情况下更长。
为了…3289. 数字小镇中的捣蛋鬼
数字小镇 Digitville 中存在一个数字列表 nums其中包含从 0 到 n - 1 的整数。每个数字本应 只出现一次然而有 两个 顽皮的数字额外多出现了一次使得列表变得比正常情况下更长。
为了恢复 Digitville 的和平作为小镇中的名侦探请你找出这两个顽皮的数字。
返回一个长度为 2 的数组包含这两个数字顺序任意。
示例 1
输入 nums [0,1,1,0]
输出 [0,1]
解释
数字 0 和 1 分别在数组中出现了两次。
示例 2
输入 nums [0,3,2,1,3,2]
输出 [2,3]
解释:
数字 2 和 3 分别在数组中出现了两次。
示例 3
输入 nums [7,1,5,4,3,4,6,0,9,5,8,2]
输出 [4,5]
解释:
数字 4 和 5 分别在数组中出现了两次。
提示
2 n 100nums.length n 20 nums[i] n输入保证 nums 中 恰好 包含两个重复的元素。
class Solution:def getSneakyNumbers(self, nums: List[int]) - List[int]:dict1 Counter(nums)l []for i in dict1:if dict1[i] 1:l.append(i)return l时间复杂度on空间复杂度on 3290. 最高乘法得分
给你一个大小为 4 的整数数组 a 和一个大小 至少为 4 的整数数组 b。
你需要从数组 b 中选择四个下标 i0, i1, i2, 和 i3并满足 i0 i1 i2 i3。你的得分将是 a[0] * b[i0] a[1] * b[i1] a[2] * b[i2] a[3] * b[i3] 的值。
返回你能够获得的 最大 得分。
示例 1
输入 a [3,2,5,6], b [2,-6,4,-5,-3,2,-7]
输出 26
解释 选择下标 0, 1, 2 和 5。得分为 3 * 2 2 * (-6) 5 * 4 6 * 2 26。
示例 2
输入 a [-1,4,5,-2], b [-5,-1,-3,-2,-4]
输出 -1
解释 选择下标 0, 1, 3 和 4。得分为 (-1) * (-5) 4 * (-1) 5 * (-2) (-2) * (-4) -1。
提示
a.length 44 b.length 10**5-105 a[i], b[i] 10**5
一开始想的是记忆化搜索但是爆了
#内存爆了
class Solution:def maxScore(self, a: List[int], b: List[int]) - int:n len(b)cachedef dfs(i : int, ans : int, step : int) - int:if step 4:return anselif i n or step 4:return -infreturn max(dfs(i 1,ans a[step] * b[i],step 1),dfs(i 1,ans,step))return dfs(0,0,0)
#时间爆了
class Solution:def maxScore(self, a: List[int], b: List[int]) - int:n len(b)cachedef dfs(i : int, ans : int, step : int) - int:if step 4:return anselif i n or step 4:return -infreturn max(dfs(i 1,ans a[step] * b[i],step 1),dfs(i 1,ans,step))ans dfs(0,0,0)dfs.cache_clear()return ans 最后改了动态规划才好
class Solution:def maxScore(self, a: List[int], b: List[int]) - int:n len(b)dp [[float(-inf)] * 5 for _ in range(n 1)]dp[0][0] 0 for i in range(n):for step in range(4, -1, -1):if step 0:dp[i 1][step] max(dp[i 1][step], dp[i][step - 1] a[step - 1] * b[i])dp[i 1][step] max(dp[i 1][step], dp[i][step])return dp[n][4]
