Leetcode,硬:2818。应用操作以最大化得分。迅速
#编程 #算法 #ios #swift

描述

您有一个n个正整数和整数k。

的数量

最初,您从分数开始1开始。您必须在最多使用以下操作k时最大化得分:

  • 选择您以前没有选择的任何非空的子阵列nums [l,...,r]。
  • 选择具有最高质量分数的nums [l,...,r]的元素x。如果存在多个这样的元素,请选择具有最小索引的一个。
  • 将您的分数乘以x。

在这里,nums[l, ..., r]表示nums的子阵列,从索引l开始,以索引r结束,两端都是包容性的。

整数x的质量得分等于x的不同主要因素的数量。例如,300的质量分数是3

返回在大多数k操作应用后的最大得分。

由于答案可能很大,请将其返回modulo 10^9 + 7

示例1:

Input: nums = [8,3,9,3,8], k = 2
Output: 81
Explanation: To get a score of 81, we can apply the following operations:
- Choose subarray nums[2, ..., 2]. nums[2] is the only element in this subarray. Hence, we multiply the score by nums[2]. The score becomes 1 * 9 = 9.
- Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 1, but nums[2] has the smaller index. Hence, we multiply the score by nums[2]. The score becomes 9 * 9 = 81.
It can be proven that 81 is the highest score one can obtain.

示例2:

Input: nums = [19,12,14,6,10,18], k = 3
Output: 4788
Explanation: To get a score of 4788, we can apply the following operations: 
- Choose subarray nums[0, ..., 0]. nums[0] is the only element in this subarray. Hence, we multiply the score by nums[0]. The score becomes 1 * 19 = 19.
- Choose subarray nums[5, ..., 5]. nums[5] is the only element in this subarray. Hence, we multiply the score by nums[5]. The score becomes 19 * 18 = 342.
- Choose subarray nums[2, ..., 3]. Both nums[2] and nums[3] have a prime score of 2, but nums[2] has the smaller index. Hence, we multipy the score by nums[2]. The score becomes 342 * 14 = 4788.
It can be proven that 4788 is the highest score one can obtain.

约束:
1 <= nums.length == n <= 10^5
1 <= nums [i] <= 10^5
1 <= k <= min(n *(n + 1) / 2,10^9)< / p>

方法

1计算素数:

  • 计算数组中每个整数的质量分数。素数代表整数的不同主要因素的数量。
  • 初始化一个布尔数组大小的码头,其中上层是nums和1的最大元素。
  • 初始化相同尺寸的整数数组列表。
  • 将Prime [0]和Prime [1]设置为false。
  • 迭代整数从2到上限-1,并根据其主要因素更新PrimesCore和Prime。

2计算下一个更大的元素:

  • 初始化阵列NextGreateRement和size N size n的everreaterorequalelement,其中n是nums的长度。
  • 使用单调堆栈找到NUMS中每个元素的质量分数更高的下一个更大的元素。
  • 通过数字迭代并保持一堆索引。
  • 对于每个元素,堆栈中的pop元素如果其质量分数小于或等于当前元素的质量分数。
  • 将堆栈顶部的索引记录为Next Greaterlement,如果堆栈不是空的,则将其设置为n。
  • 反向重复上述过程以计算viveReaterReoreQualelemt。

3排序和过程元素:

  • 创建一个元组(num,i)的数组,其中num是元素的值,而i是nums中的索引。
  • 按第一个元素(num)的降序排序元组。
  • 循环通过分类的元组并执行以下步骤:
    • 将操作数量计算为(i -fiveReaterReorequalelement [i]) *(nextGreateReallement [i] - i)和k。
    • 更新RES通过使用助手功能POW。
    • 通过操作数量减少K。
    • 如果k变为0,返回res。

4个辅助功能:

  • 实现POW函数以使用模块化算术有效地计算指示。

复杂

  • 时间复杂性O(max(nums) * log(max(nums)) + n * log(n))。考虑计算素数分数,使用堆栈计算下一个更大的元素并对元组进行排序。

  • 空间复杂性O(max(nums) + n)。考虑阵列所需的空间和用于计算的堆栈。

代码(Swift)

class Solution {

    func maximumScore(_ nums: [Int], _ k: Int) -> Int {
        let MOD = 1_000_000_007
        var k = k  // Make a mutable copy of k
        let n = nums.count

        var upper = nums.max()! + 1

        var prime = [Bool](repeating: true, count: upper)
        prime[0] = false
        prime[1] = false
        var primeScore = [Int](repeating: 0, count: upper)

        for i in 2..<upper {
            if prime[i] {
                var j = i
                while j < upper {
                    primeScore[j] += 1
                    prime[j] = false
                    j += i
                }
            }
        }

        var nextGreaterElement = [Int](repeating: n, count: n)
        var s = [Int]()
        for i in (0..<n).reversed() {
            while !s.isEmpty && primeScore[nums[i]] >= primeScore[nums[s.last!]] {
                s.popLast()
            }
            nextGreaterElement[i] = s.isEmpty ? n : s.last!
            s.append(i)
        }

        var prevGreaterOrEqualElement = [Int](repeating: -1, count: n)
        s.removeAll()
        for i in 0..<n {
            while !s.isEmpty && primeScore[nums[i]] > primeScore[nums[s.last!]] {
                s.popLast()
            }
            prevGreaterOrEqualElement[i] = s.isEmpty ? -1 : s.last!
            s.append(i)
        }

        var res = 1
        var tuples = [(num: Int, index: Int)]()
        for i in 0..<n {
            tuples.append((nums[i], i))
        }
        tuples.sort { a, b in
            a.num > b.num
        }

        for (num, i) in tuples {
            let operations = min(
                (i - prevGreaterOrEqualElement[i]) * (nextGreaterElement[i] - i), k)
            res = (res * pow(num, operations, MOD)) % MOD
            k -= operations
            if k == 0 {
                return res
            }
        }

        return res
    }

    func pow(_ x: Int, _ n: Int, _ mod: Int) -> Int {
        var res = 1
        var x = x
        var n = n
        while n > 0 {
            if n % 2 == 1 {
                res = (res * x) % mod
            }
            x = (x * x) % mod
            n /= 2
        }
        return res
    }
}


来源:Github

Sergey Leschev LeetCode Global TOP 200


联系人
我明确专注于上市时间,而没有优先考虑技术债务。我作为系统建筑师,移动(ios-swift,android-kotlin),前端(react-typescript)和后端(nodejs-.net-.net-php-php-php-php-kafka-sql)参加了系统架构师的预售/RFX活动。 -nosql)。我还通过知识转移到成功交付的知识转移,成立了预售作为CTO的工作。

在 ð§电子邮件:sergey.leschev@gmail.com
ðLinkedIn:https://linkedin.com/in/sergeyleschev/
ðleetcode:https://leetcode.com/sergeyleschev/
ðTwitter:https://twitter.com/sergeyleschev
ðgithub:https://github.com/sergeyleschev
ð网站:https://sergeyleschev.github.io
ðreddit:https://reddit.com/user/sergeyleschev
ðQuora:https://quora.com/sergey-leschev
ð媒介:https://medium.com/@sergeyleschev
□PDF设计模式:Download