LeetCode 3143. 正方形中的最多点数【位运算,构造法】中等【C++,Java,Py3,Go,Rust】

2024-08-23 05:28

本文主要是介绍LeetCode 3143. 正方形中的最多点数【位运算,构造法】中等【C++,Java,Py3,Go,Rust】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

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

给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ,对于所有 0 <= i < n - 1 ,满足 nums[i + 1] 大于 nums[i] ,并且数组 nums 中所有元素的按位 AND 运算结果为 x 。

返回 nums[n - 1] 可能的 最小 值。

示例 1:

输入:n = 3, x = 4
输出:6
解释:
数组 `nums` 可以是 `[4,5,6]` ,最后一个元素为 `6` 。

示例 2:

输入:n = 2, x = 7
输出:15
解释:
数组 `nums` 可以是 `[7,15]` ,最后一个元素为 `15` 。

提示:

  • 1 <= n, x <= 10^8

方法:位运算,两种简洁解法

从集合的视角看, x x x 是每个 n u m s [ i ] nums[i] nums[i]子集。换句话说, n u m s [ i ] nums[i] nums[i] 一定是 x x x超集。例如 x = 100100 x=100100 x=100100 ,那么 n u m s [ i ] nums[i] nums[i] 一定在如下序列中:
1 00 ‾ 1 00 ‾ , 1 00 ‾ 1 01 ‾ , 1 00 ‾ 1 10 ‾ , 1 00 ‾ 1 11 ‾ , 1 01 ‾ 1 00 ‾ , 1 01 ‾ 1 01 ‾ , … 1\underline{00}1\underline{00}, 1\underline{00}1\underline{01}, 1\underline{00}1\underline{10}, 1\underline{00}1\underline{11}, 1\underline{01}1\underline{00}, 1\underline{01}1\underline{01},\ \dots 100100,100101,100110,100111,101100,101101, 

只看下划线上的数,是一个自然数序列
0000 , 0001 , 0010 , 0011 , 0100 , 0101 , ⋯ 0000,0001,0010,0011,0100,0101,⋯ 0000,0001,0010,0011,0100,0101,
为了让 n u m s [ n − 1 ] nums[n−1] nums[n1] 尽量小,我们应当选择 x x x 的超集中最小的 n n n 个数

所以 x x x 的二进制中的 0 0 0 视作「空位」,往空位上填入 n − 1 n−1 n1 ,即为最小 n u m s [ n − 1 ] nums[n−1] nums[n1] 。如果空位不足,往 x x x 的前面添加前导零即可。

class Solution:def minEnd(self, n: int, x: int) -> int:n -= 1  # 先把 n 减一,这样下面讨论的 n 就是原来的 n-1i = j = 0while n >> j:# x 的第 i 个比特值是 0,即「空位」if (x >> i & 1) == 0:# 空位填入 n 的第 j 个比特值x |= (n >> j & 1) << ij += 1i += 1return x
class Solution {public long minEnd(int n, int x) {n--; // 先把 n 减一,这样下面讨论的 n 就是原来的 n-1long ans = x;int i = 0, j = 0;while ((n >> j) > 0) {// x 的第 i 个比特值是 0,即「空位」if ((ans >> i & 1) == 0) {// 空位填入 n 的第 j 个比特值ans |= (long) (n >> j & 1) << i;j++;}i++;}return ans;}
}
class Solution {
public:long long minEnd(int n, int x) {n--; // 先把 n 减一,这样下面讨论的 n 就是原来的 n-1long long ans = x;int i = 0, j = 0;while (n >> j) {// x 的第 i 个比特值是 0,即「空位」if ((ans >> i & 1) == 0) {// 空位填入 n 的第 j 个比特值ans |= (long long) (n >> j & 1) << i;j++;}i++;}return ans;}
};
func minEnd(n, x int) int64 {n-- // 先把 n 减一,这样下面讨论的 n 就是原来的 n-1i, j := 0, 0for n>>j > 0 {// x 的第 i 个比特值是 0,即「空位」if x>>i&1 == 0 {// 空位填入 n 的第 j 个比特值x |= n >> j & 1 << ij++}i++}return int64(x)
}
impl Solution {pub fn min_end(n: i32, x: i32) -> i64 {let mut tn: i64 = n as i64 - 1;let mut tx: i64 = x as i64;let mut i: i64 = 0;let mut j: i64 = 0;while tn >> j != 0 {if (tx >> i & 1) == 0 {tx |= (tn >> j & 1) << i;j += 1;}i += 1;}tx}
}

复杂度分析

  • 时间复杂度: O ( log ⁡ x + log ⁡ n ) O(\log x+\log n) O(logx+logn)
  • 空间复杂度: O ( 1 ) O(1) O(1)

优化:把 x x x 取反,用 l o w b i t lowbit lowbit 枚举其中的 1 1 1 的值,就是要填的空位。

class Solution:def minEnd(self, n: int, x: int) -> int:n -= 1j = 0t = ~xwhile n >> j:lb = t & -tx |= (n >> j & 1) * lbj += 1t ^= lbreturn x
class Solution {
public:long long minEnd(int n, int x) {n--;long long ans = x;int j = 0;for (long long t = ~x, lb; n >> j; t ^= lb) {lb = t & -t;ans |= (long long) (n >> j++ & 1) * lb;}return ans;}
};
class Solution {public long minEnd(int n, int x) {n--;long ans = x;int j = 0;for (long t = ~x, lb; (n >> j) > 0; t ^= lb) {lb = t & -t;ans |= (long) (n >> j++ & 1) * lb;}return ans;}
}
func minEnd(n, x int) int64 {n--j := 0for t, lb := ^x, 0; n>>j > 0; t ^= lb {lb = t & -tx |= n >> j & 1 * lbj++}return int64(x)
}

复杂度分析

  • 时间复杂度: O ( log ⁡ n ) O(\log n) O(logn) 。循环次数只和入参 n n n 有关。
  • 空间复杂度: O ( 1 ) O(1) O(1)

更快的做法?《Hacker’s Delight》第 7.5 节。

思考题
额外输入一个 f o r b i d d e n forbidden forbidden 数组,表示禁止出现在 n u m s nums nums 中的数。在这种额外约束下, n u m s [ n − 1 ] nums[n−1] nums[n1] 的最小值是多少?
答:出现在 nums 中的数无疑能满足相与后为 x x x禁止的这些数相与也是 x x x ,禁止这些数出现后还要相与为 x x x 。因此先剥离出 f o r b i d d e n forbidden forbidden 数组中每个数出现在【 x x x 0 0 0 位】上的值组成新数组,排序,遍历新数组,如果值小于 k k k(初始为 k = n − 1 k = n - 1 k=n1 ),则 k + + k++ k++ 。最后,往空位上填入 k k k

这篇关于LeetCode 3143. 正方形中的最多点数【位运算,构造法】中等【C++,Java,Py3,Go,Rust】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1098472

相关文章

Spring Boot结成MyBatis-Plus最全配置指南

《SpringBoot结成MyBatis-Plus最全配置指南》本文主要介绍了SpringBoot结成MyBatis-Plus最全配置指南,包括依赖引入、配置数据源、Mapper扫描、基本CRUD操... 目录前言详细操作一.创建项目并引入相关依赖二.配置数据源信息三.编写相关代码查zsRArly询数据库数

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

一文详解如何从零构建Spring Boot Starter并实现整合

《一文详解如何从零构建SpringBootStarter并实现整合》SpringBoot是一个开源的Java基础框架,用于创建独立、生产级的基于Spring框架的应用程序,:本文主要介绍如何从... 目录一、Spring Boot Starter的核心价值二、Starter项目创建全流程2.1 项目初始化(

Spring Boot3虚拟线程的使用步骤详解

《SpringBoot3虚拟线程的使用步骤详解》虚拟线程是Java19中引入的一个新特性,旨在通过简化线程管理来提升应用程序的并发性能,:本文主要介绍SpringBoot3虚拟线程的使用步骤,... 目录问题根源分析解决方案验证验证实验实验1:未启用keep-alive实验2:启用keep-alive扩展建

SpringBoot配置Ollama实现本地部署DeepSeek

《SpringBoot配置Ollama实现本地部署DeepSeek》本文主要介绍了在本地环境中使用Ollama配置DeepSeek模型,并在IntelliJIDEA中创建一个Sprin... 目录前言详细步骤一、本地配置DeepSeek二、SpringBoot项目调用本地DeepSeek前言随着人工智能技

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

Java异常架构Exception(异常)详解

《Java异常架构Exception(异常)详解》:本文主要介绍Java异常架构Exception(异常),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. Exception 类的概述Exception的分类2. 受检异常(Checked Exception)

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子

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

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

springboot报错Invalid bound statement (not found)的解决

《springboot报错Invalidboundstatement(notfound)的解决》本文主要介绍了springboot报错Invalidboundstatement(not... 目录一. 问题描述二.解决问题三. 添加配置项 四.其他的解决方案4.1 Mapper 接口与 XML 文件不匹配