LeetCode-376

本场两道题都与中位数有关，个人感觉第三题会比第四题难想一点，本场整体难度中等

Q1 找出缺失和重复的数字

  • 给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n2] 范围内。除了 a 出现 两次，b 缺失 之外，每个整数都 恰好出现一次 。

    任务是找出重复的数字a 和缺失的数字 b 。

    返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。

    示例 1：

    1
    2
    3
    输入：grid = [[1,3],[2,2]]
    输出：[2,4]
    解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。

    示例 2：

    1
    2
    3
    输入：grid = [[9,1,7],[8,9,2],[3,4,6]]
    输出：[9,5]
    解释：数字 9 重复，数字 5 缺失，所以答案是 [9,5] 。

    提示：

    • 2 <= n == grid.length == grid[i].length <= 50
    • 1 <= grid[i][j] <= n * n
    • 对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。
    • 对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。
    • 除上述的两个之外，对于所有满足1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x 。

使用Set加枚举模拟本题即可解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    fun findMissingAndRepeatedValues(grid: Array<IntArray>): IntArray {
        val n = grid.size
        val s2 = hashSetOf<Int>()
        var a = 0
        var b = 0
        for (g in grid) {
            for (i in 0..<n) {
                if (s2.contains(g[i]))
                    a = g[i]
                s2.add(g[i])
            }
        }
        for (x in 1..n * n) {
            if (!s2.contains(x)) {
                b = x
                break
            }
        }
        return intArrayOf(a, b)

    }
}

Q2 划分数组并满足最大差限制

  • 给你一个长度为 n 的整数数组 nums，以及一个正整数 k 。

    将这个数组划分为一个或多个长度为 3 的子数组，并满足以下条件：

    • nums 中的 每个 元素都必须 恰好 存在于某个子数组中。
    • 子数组中 任意 两个元素的差必须小于或等于 k 。

    返回一个 二维数组 ，包含所有的子数组。如果不可能满足条件，就返回一个空数组。如果有多个答案，返回 任意一个 即可。

    示例 1：

    1
    2
    3
    4
    5
    输入：nums = [1,3,4,8,7,9,3,5,1], k = 2
    输出：[[1,1,3],[3,4,5],[7,8,9]]
    解释：可以将数组划分为以下子数组：[1,1,3]，[3,4,5] 和 [7,8,9] 。
    每个子数组中任意两个元素的差都小于或等于 2 。
    注意，元素的顺序并不重要。

    示例 2：

    1
    2
    3
    输入：nums = [1,3,3,2,7,3], k = 3
    输出：[]
    解释：无法划分数组满足所有条件。

    提示：

    • n == nums.length
    • 1 <= n <= 105
    • n 是 3 的倍数
    • 1 <= nums[i] <= 105
    • 1 <= k <= 105

很容易看出想让相邻的数的差值最小的办法就是排序，排序后模拟一遍过程，即可得到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    fun divideArray(nums: IntArray, k: Int): Array<IntArray> {
        nums.sort()
        val n = nums.size
        val ret = mutableListOf<IntArray>()
        var i = 0
        while (i < n) {
            if (i + 2 < n && nums[i + 2] - nums[i] <= k) {
                ret.add(intArrayOf(nums[i], nums[i + 1], nums[i + 2]))
                i += 3
            } else {
                return emptyArray()
            }
        }
        return ret.toTypedArray()
    }
}

Q3 使数组成为等数数组的最小代价

给你一个长度为 n 下标从 0 开始的整数数组 nums 。

你可以对 nums 执行特殊操作 任意次 （也可以 0 次）。每一次特殊操作中，你需要 按顺序 执行以下步骤：

  • 从范围 [0, n - 1] 里选择一个下标 i 和一个 正 整数 x 。
  • 将 |nums[i] - x| 添加到总代价里。
  • 将 nums[i] 变为 x 。

如果一个正整数正着读和反着读都相同，那么我们称这个数是 回文数 。比方说，121 ，2552 和 65756 都是回文数，但是 24 ，46 ，235 都不是回文数。

如果一个数组中的所有元素都等于一个整数 y ，且 y 是一个小于 109 的 回文数 ，那么我们称这个数组是一个 等数数组 。

请你返回一个整数，表示执行任意次特殊操作后使 nums 成为 等数数组 的 最小 总代价。

示例 1：

1
2
3
4
输入：nums = [1,2,3,4,5]
输出：6
解释：我们可以将数组中所有元素变为回文数 3 得到等数数组，数组变成 [3,3,3,3,3] 需要执行 4 次特殊操作，代价为 |1 - 3| + |2 - 3| + |4 - 3| + |5 - 3| = 6 。
将所有元素变为其他回文数的总代价都大于 6 。

示例 2：

1
2
3
4
输入：nums = [10,12,13,14,15]
输出：11
解释：我们可以将数组中所有元素变为回文数 11 得到等数数组，数组变成 [11,11,11,11,11] 需要执行 5 次特殊操作，代价为 |10 - 11| + |12 - 11| + |13 - 11| + |14 - 11| + |15 - 11| = 11 。
将所有元素变为其他回文数的总代价都大于 11 。

示例 3 ：

1
2
3
4
输入：nums = [22,33,22,33,22]
输出：22
解释：我们可以将数组中所有元素变为回文数 22 得到等数数组，数组变为 [22,22,22,22,22] 需要执行 2 次特殊操作，代价为 |33 - 22| + |33 - 22| = 22 。
将所有元素变为其他回文数的总代价都大于 22 。

提示：

  • 1 <= n <= 105
  • 1 <= nums[i] <= 109

本题很容易想到要最终变成的那个数，不能太大，也不能太小，那就先预处理数据范围内的中位数，(起初我并未想到中位数，先无脑写了个三分，然后就错了)，由于是绝对值的差，那么大概率就可以通过排序+前缀和+二分来解决，枚举要变成哪个数就行。如何处理1−1091-10^9内的回文数呢?由于太菜，只能想到字符串处理，枚举前半部分，拼接后半部分，由于可能是奇数长度或偶数长度，所以枚举的一个数都会变成两个数，这个数据范围试错了好多，后来学习到效率更高的处理方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 预处理
arr = []
for i in range(1, 60001):
    s = str(i)
    arr.append(int(s + s[::-1]))
    arr.append(int(s + s[:len(s) - 1][::-1]))

arr.sort()


class Solution:
    def minimumCost(self, nums: List[int]) -> int:
        n = len(nums)
        l, r = 0, len(arr) - 1
        nums.sort()
        s = [0] * (n + 1)
        ans = 10 ** 15
        for i in range(n):
            s[i + 1] = s[i] + nums[i]

        def get(k: int) -> int:
            l, r = 0, n - 1
            while l < r:
                mid = (l + r + 1) // 2
                if nums[mid] <= k:
                    l = mid
                else:
                    r = mid - 1
            if nums[l] > k:
                return s[n] - k * n
            return (l + 1) * k - s[l + 1] + s[n] - s[l + 1] - (n - l - 1) * k

        for x in arr:
            v = get(x)
            if v > ans:
                return ans #大于之后直接返回即可
            ans = v
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#更高效率的处理方法，而且不需要排序
arr = []
base = 1
while base <= 10000:
    # 计算奇数长度
    for i in range(base, base * 10):
        x = i
        t = i // 10
        while t:
            x = x * 10 + t % 10
            t //= 10
        arr.append(x)
    # 计算偶数长度
    if base <= 1000:
        for i in range(base, base * 10):
            x = t = i
            while t:
                x = x * 10 + t % 10
                t //= 10
            arr.append(x)
    base *= 10

Q4 执行操作使频率分数最大

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

你可以对数组执行 至多 k 次操作：

  • 从数组中选择一个下标 i ，将 nums[i] 增加 或者 减少 1 。

最终数组的频率分数定义为数组中众数的 频率 。

请你返回你可以得到的 最大 频率分数。

众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [1,2,6,4], k = 3
输出：3
解释：我们可以对数组执行以下操作：
- 选择 i = 0 ，将 nums[0] 增加 1 。得到数组 [2,2,6,4] 。
- 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,3] 。
- 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,2] 。
元素 2 是最终数组中的众数，出现了 3 次，所以频率分数为 3 。
3 是所有可行方案里的最大频率分数。

示例 2：

1
2
3
输入：nums = [1,4,4,2,4], k = 0
输出：3
解释：我们无法执行任何操作，所以得到的频率分数是原数组中众数的频率 3 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 0 <= k <= 1014

使用二分+滑窗+前缀和处理。本题不能向上个题一样枚举变成哪个数，而是要枚举答案，其他的就很好想了，一段已经排好序的数中变成中位数的绝对值差肯定最小，然后前缀和思想和之前的题是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        s = [0] * (n + 1)
        for i in range(n):
            s[i + 1] = s[i] + nums[i]
        """
        贪心的将所有数变为中位数
        固定窗口的滑窗
        """

        def check(v: int) -> bool:
            le, ri = 0, v - 1
            mid = (le + ri) // 2
            if nums[mid] * (mid - le + 1) - (s[mid + 1] - s[le]) + (
                    s[ri + 1] - s[mid + 1] - nums[mid] * (ri - mid)) <= k:
                return True
            for i in range(ri + 1, n):
                ll, rr = i - v + 1, i
                mm = (ll + rr) // 2
                if nums[mm] * (mm - ll + 1) - (s[mm + 1] - s[ll]) + (s[rr + 1] - s[mm + 1] - nums[mm] * (rr - mm)) <= k:
                    return True
            return False

        l, r = 0, n
        while l < r:
            mid = (l + r + 1) // 2
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l
算法
#leetcode
LeetCode-376
http://example.com/2024/01/03/LeetCode-376/
作者
ykexc
发布于
2024年1月3日
许可协议