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

相关文章

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

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

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

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

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

Python使用DrissionPage中ChromiumPage进行自动化网页操作

《Python使用DrissionPage中ChromiumPage进行自动化网页操作》DrissionPage作为一款轻量级且功能强大的浏览器自动化库,为开发者提供了丰富的功能支持,本文将使用Dri... 目录前言一、ChromiumPage基础操作1.初始化Drission 和 ChromiumPage

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

Redis中管道操作pipeline的实现

《Redis中管道操作pipeline的实现》RedisPipeline是一种优化客户端与服务器通信的技术,通过批量发送和接收命令减少网络往返次数,提高命令执行效率,本文就来介绍一下Redis中管道操... 目录什么是pipeline场景一:我要向Redis新增大批量的数据分批处理事务( MULTI/EXE

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.