LeetCode 2897. 对数组执行操作使平方和最大【贪心,位运算,哈希表】2301

本文主要是介绍LeetCode 2897. 对数组执行操作使平方和最大【贪心,位运算,哈希表】2301,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

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

你可以对数组执行以下操作 任意次 :

  • 选择两个互不相同的下标 i 和 j ,同时 将 nums[i] 更新为 (nums[i] AND nums[j]) 且将 nums[j] 更新为 (nums[i] OR nums[j]) ,OR 表示按位  运算,AND 表示按位  运算。

你需要从最终的数组里选择 k 个元素,并计算它们的 平方 之和。

请你返回你可以得到的 最大 平方和。

由于答案可能会很大,将答案对 10^9 + 7 取余 后返回。

示例 1:

输入:nums = [2,6,5,8], k = 2
输出:261
解释:我们可以对数组执行以下操作:
- 选择 i = 0 和 j = 3 ,同时将 nums[0] 变为 (2 AND 8) = 0 且 nums[3] 变为 (2 OR 8) = 10 ,结果数组为 nums = [0,6,5,10]- 选择 i = 2 和 j = 3 ,同时将 nums[2] 变为 (5 AND 10) = 0 且 nums[3] 变为 (5 OR 10) = 15 ,结果数组为 nums = [0,6,0,15] 。
从最终数组里选择元素 156 ,平方和为 152 + 62 = 261261 是可以得到的最大结果。

示例 2:

输入:nums = [4,5,4,7], k = 3
输出:90
解释:不需要执行任何操作。
选择元素 754 ,平方和为 72 + 52 + 42 = 9090 是可以得到的最大结果。

提示:

  • 1 <= k <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解法 位运算+贪心+哈希表

一个直接的感受是,如果将一个数和其他更多的数按位与,则结果会越来越小;如果将一个数和其他更多的数按位或,则结果会越来越大。

现在对 n u m s [ i ] nums[i] nums[i] n u m s [ j ] nums[j] nums[j] 同时更新,对于同一个比特位,由于 AND 和 OR 不会改变都为 0 0 0 和都为 1 1 1 的情况,所以操作等价于:把一个数的 0 0 0 和另一个数的同一个比特位上的 1 1 1 交换

假设交换前两个数是 x , y x,y x,y ,且 x > y x > y x>y 。则把小的数上的 1 1 1 给大的数,假设交换后 x x x 增加了 d d d ,则 y y y 也减少了 d d d

  • 交换前: x 2 + y 2 x^2 + y^2 x2+y2
  • 交换后: ( x + d ) 2 + ( y − d ) 2 = x 2 + y 2 + 2 d ( x − y ) + 2 d 2 > x 2 + y 2 (x+d)^2 + (y - d)^2 = x^2 + y^2 + 2d(x - y) + 2d^2 > x^2 +y^2 (x+d)2+(yd)2=x2+y2+2d(xy)+2d2>x2+y2

这说明应该通过交换,让一个数越大越好。相当于 1 1 1聚集在一个数中,比分散到不同数中更好

由于可以操作任意次,那么一定可以「组装」出尽量大的数:做法如下:

  1. 对每个比特位,统计 n u m s nums nums 数组中的元素在这个比特位上有多少个 1 1 1 ,记到一个长至多为 30 30 30 c n t cnt cnt 数组中(因为 1 0 9 < 2 30 10^9 < 2^{30} 109<230
  2. 循环 k k k 次。每次循环,组装一个数(记为 x x x):遍历 c n t cnt cnt ,只要 c n t [ i ] > 0 cnt[i] > 0 cnt[i]>0 就将其减一,同时将 2 i 2^i 2i 加到 x x x 中。这样相当于把 1 1 1 尽量聚集在一个数中。
  3. x 2 x^2 x2 加到答案中。
class Solution {
public:int maxSum(vector<int>& nums, int k) {int cnt[31] {};for (int num : nums)for (int i = 0; i < 31; ++i)cnt[i] += ((num >> i) & 1);long long ans = 0;const int MOD = 1e9 + 7;while (k--) {int x = 0;for (int i = 0; i < 31; ++i) {if (cnt[i]) {x |= 1 << i;cnt[i]--;}}ans = (ans + (long long)x * x) % MOD;}return ans;}
};

复杂度分析:

  • 时间复杂度: O ( n log ⁡ U ) \mathcal{O}(n\log U) O(nlogU) ,其中 n n n nums \textit{nums} nums 的长度, U = max ⁡ ( nums ) U=\max(\textit{nums}) U=max(nums)
  • 空间复杂度: O ( log ⁡ U ) \mathcal{O}(\log U) O(logU)

这篇关于LeetCode 2897. 对数组执行操作使平方和最大【贪心,位运算,哈希表】2301的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/237079

相关文章

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

Python 中的 with open文件操作的最佳实践

《Python中的withopen文件操作的最佳实践》在Python中,withopen()提供了一个简洁而安全的方式来处理文件操作,它不仅能确保文件在操作完成后自动关闭,还能处理文件操作中的异... 目录什么是 with open()?为什么使用 with open()?使用 with open() 进行

Linux ls命令操作详解

《Linuxls命令操作详解》通过ls命令,我们可以查看指定目录下的文件和子目录,并结合不同的选项获取详细的文件信息,如权限、大小、修改时间等,:本文主要介绍Linuxls命令详解,需要的朋友可... 目录1. 命令简介2. 命令的基本语法和用法2.1 语法格式2.2 使用示例2.2.1 列出当前目录下的文

Mysql表的简单操作(基本技能)

《Mysql表的简单操作(基本技能)》在数据库中,表的操作主要包括表的创建、查看、修改、删除等,了解如何操作这些表是数据库管理和开发的基本技能,本文给大家介绍Mysql表的简单操作,感兴趣的朋友一起看... 目录3.1 创建表 3.2 查看表结构3.3 修改表3.4 实践案例:修改表在数据库中,表的操作主要

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处