-
Leetcode 2897. Apply Operations on Array to Maximize Sum of Squares
- 1. 解題思路
- 2. 代碼實現(xiàn)
- 題目鏈接：2897. Apply Operations on Array to Maximize Sum of Squares
1. 解題思路
這一題事實上非常的簡單，我們只需要想明白一些關鍵點就行了。
題中最終的目標是獲得 k k k個數(shù)，使得其平方和最大。因此，我們就只需要理解一下題中給出的操作會帶來怎樣的變化，以及要如何獲取最大的平方和即可。
首先，對于題中給出的位操作，事實上只有在一種情況下才會產生變化，即 i = 1 , j = 0 i=1, j=0 i=1,j=0的情況下，會變?yōu)?span id="n5n3t3z" class="katex--inline"> i = 0 , j = 1 i=0, j=1 i=0,j=1，其余情況都不會產生變化。因此，我們無法改變各個位上 0 , 1 0,1 0,1的數(shù)目總量，但是總可以通過一定的操作將其均勻化或者聚合到某幾個數(shù)上。
然后，如果要使得兩個數(shù)的平方和最大，我們考察某一位上的數(shù)最好是分布在較大的數(shù)還是在較小的數(shù)上，不妨令這個位上的數(shù)為
x
x
x，然后其余位上的數(shù)分別為
a
,
b
a, b
a,b，那么平方和就是：
(
a
+
x
)
2
+
b
2
=
a
2
+
2
a
x
+
x
2
+
b
2
(a+x)^2 + b^2 = a^2 + 2ax+x^2 + b^2
(a+x)2+b2=a2+2ax+x2+b2
顯然， a a a較大時，可以獲得更大的平方和。
綜上，我們就可以獲得我們最終的結論：
- 要取 k k k個數(shù)，使得平方和最大，我們只需要統(tǒng)計每一位上擁有的 1 1 1的個數(shù)，然后盡可能全部分配到這 k k k個數(shù)當中即可。
2. 代碼實現(xiàn)
給出最終的代碼實現(xiàn)如下：文章來源：http://www.zghlxwxcb.cn/news/detail-727575.html
class Solution:
def maxSum(self, nums: List[int], k: int) -> int:
MOD = 10**9+7
digits = [0 for _ in range(32)]
flag = [pow(2, i, MOD) for i in range(32)]
for x in nums:
idx = 0
while x != 0:
digits[idx] += x % 2
x = x // 2
idx += 1
ans = 0
for i in range(k):
x = 0
for idx in range(32):
if digits[idx] > 0:
digits[idx] -= 1
x += flag[idx]
ans = (ans + x * x) % MOD
return ans
提交代碼評測得到：耗時2510ms，占用內存30.6MB。文章來源地址http://www.zghlxwxcb.cn/news/detail-727575.html
到了這里，關于Leetcode 2897. Apply Operations on Array to Maximize Sum of Squares的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
