使用kotlin解决这个题目:1090. 受标签影响的最大值 提示 中等 51 相关企业 我们有一个 n 项的集合。给出两个整数数组 values 和 labels ,第 i 个元素的值和标签分别是 values[i] 和 labels[i]。还会给出两个整数 numWanted 和 useLimit 。 从 n 个元素中选择一个子集 s : 子集 s 的大小 小于或等于 numWanted 。 s 中 最多 有相同标签的 useLimit 项。 一个子集的 分数 是该子集的值之和。 返回子集 s 的最大 分数 。 示例 1: 输入:values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1 输出:9 解释:选出的子集是第一项,第三项和第五项。 示例 2: 输入:values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2 输出:12 解释:选出的子集是第一项,第二项和第三项。 示例 3: 输入:values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1 输出:16 解释:选出的子集是第一项和第四项。
时间: 2023-07-02 13:04:25 浏览: 173
```kotlin
fun largestValsFromLabels(values: IntArray, labels: IntArray, numWanted: Int, useLimit: Int): Int {
val n = values.size
val pairs = Array(n) { Pair(values[it], labels[it]) }
pairs.sortByDescending { it.first } // 按值从大到小排序
val used = mutableMapOf<Int, Int>() // 记录每个标签已经使用的次数
var ans = 0
var cnt = 0
for (pair in pairs) {
if (cnt == numWanted) break // 已选够 numWanted 个元素
if (used.getOrDefault(pair.second, 0) < useLimit) { // 当前标签还能用
ans += pair.first
used[pair.second] = used.getOrDefault(pair.second, 0) + 1
cnt++
}
}
return ans
}
```
相关问题
使用kotlin解决这个题目:1330. 翻转子数组得到最大的数组值 提示 困难 164 相关企业 给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。 你可以选择给定数组的任意子数组,并将该子数组翻转。但你只能执行这个操作 一次 。 请你找到可行的最大 数组值 。 示例 1: 输入:nums = [2,3,1,5,4] 输出:10 解释:通过翻转子数组 [3,1,5] ,数组变成 [2,5,1,3,4] ,数组值为 10 。 示例 2: 输入:nums = [2,4,9,24,2,1,10] 输出:68 提示: 1 <= nums.length <= 3*10^4 -10^5 <= nums[i] <= 10^5
下面是使用 Kotlin 解决该问题的代码:
```kotlin
fun maxValueAfterReverse(nums: IntArray): Int {
var sum = 0
var diff = 0
var maxStart = Int.MIN_VALUE
var minEnd = Int.MAX_VALUE
val n = nums.size
for (i in 0 until n - 1) {
val a = nums[i]
val b = nums[i + 1]
sum += kotlin.math.abs(a - b)
diff = kotlin.math.max(diff, kotlin.math.abs(nums[0] - b) - kotlin.math.abs(a - b))
diff = kotlin.math.max(diff, kotlin.math.abs(nums[n - 1] - a) - kotlin.math.abs(a - b))
maxStart = kotlin.math.max(maxStart, kotlin.math.min(a, b))
minEnd = kotlin.math.min(minEnd, kotlin.math.max(a, b))
}
return sum + kotlin.math.max(
diff,
kotlin.math.max(
(minEnd - maxStart) * 2,
kotlin.math.max(
kotlin.math.abs(nums[0] - minEnd),
kotlin.math.abs(nums[n - 1] - maxStart)
)
)
)
}
```
该函数的思路如下:
首先,我们计算出给定数组的初始值(即子数组未翻转时的数组值)。
然后,我们枚举所有可能的子数组,并计算翻转该子数组后的数组值。注意,由于只能执行一次翻转操作,因此我们只需考虑两个长度不为 $1$ 的子数组的翻转。对于每个子数组,我们可以通过计算该子数组两端的元素与其他元素之间的差值来确定翻转该子数组时数组值的变化量。
在计算翻转子数组的数组值变化量时,我们需要考虑以下几种情况:
- 翻转的子数组不包含数组的首尾元素。
- 翻转的子数组包含数组的首元素但不包含数组的尾元素。
- 翻转的子数组包含数组的尾元素但不包含数组的首元素。
- 翻转的子数组同时包含数组的首尾元素。
为了方便计算,我们分别记录数组中的最大值和最小值,以及所有相邻元素之间的差值的和。最终的结果是数组的初始值加上以上四种情况中的最大值。
时间复杂度:$O(n)$,其中 $n$ 是数组的长度。
阅读全文