当前位置：首页 > news >正文

LeetCode 3314.构造最小位运算数组 I：今日先简单题简单做-到II再优化

news 2026/5/12 12:06:41

【LetMeFly】3314.构造最小位运算数组 I：今日先简单题简单做-到II再优化

力扣题目链接：https://leetcode.cn/problems/construct-the-minimum-bitwise-array-i/

给你一个长度为n的质数数组nums。你的任务是返回一个长度为n的数组ans，对于每个下标i，以下条件均成立：

ans[i] OR (ans[i] + 1) == nums[i]

除此以外，你需要最小化结果数组里每一个ans[i]。

如果没法找到符合条件的ans[i]，那么ans[i] = -1。

质数指的是一个大于 1 的自然数，且它只有 1 和自己两个因数。

示例 1：

输入：nums = [2,3,5,7]

输出：[-1,1,4,3]

解释：

对于i = 0，不存在ans[0]满足ans[0] OR (ans[0] + 1) = 2，所以ans[0] = -1。
对于i = 1，满足ans[1] OR (ans[1] + 1) = 3的最小ans[1]为1，因为1 OR (1 + 1) = 3。
对于i = 2，满足ans[2] OR (ans[2] + 1) = 5的最小ans[2]为4，因为4 OR (4 + 1) = 5。
对于i = 3，满足ans[3] OR (ans[3] + 1) = 7的最小ans[3]为3，因为3 OR (3 + 1) = 7。

示例 2：

输入：nums = [11,13,31]

输出：[9,12,15]

解释：

对于i = 0，满足ans[0] OR (ans[0] + 1) = 11的最小ans[0]为9，因为9 OR (9 + 1) = 11。
对于i = 1，满足ans[1] OR (ans[1] + 1) = 13的最小ans[1]为12，因为12 OR (12 + 1) = 13。
对于i = 2，满足ans[2] OR (ans[2] + 1) = 31的最小ans[2]为15，因为15 OR (15 + 1) = 31。

提示：

1 <= nums.length <= 100
2 <= nums[i] <= 1000
nums[i]是一个质数。

解题方法：模拟

今天就每个数O ( 1 ) O(1)O(1)的话，明天的每日一题就没得做了。

对于一个数n nn，如何求得其对应的最小a n s ansans？

使用一个变量从0 00试到n − 1 n-1n−1就好了。

每个数都这样试试，也不用优化，今日的每日一题就这样结束了。

时间复杂度O ( l e n ( n u m s ) × max ⁡ ( n u m s ) ) O(len(nums)\times\max(nums))O(len(nums)×max(nums))
空间复杂度O ( 1 ) O(1)O(1)，力扣返回值不计入算法空间复杂度

AC代码

C++

/* * @LastEditTime: 2026-01-20 22:52:17 */classSolution{private:intget(intn){for(inti=0;i<=n;i++){if((i|(i+1))==n){returni;}}return-1;}public:vector<int>minBitwiseArray(vector<int>&nums){vector<int>ans(nums.size());for(inti=0;i<nums.size();i++){ans[i]=get(nums[i]);}returnans;}};

Python

''' LastEditTime: 2026-01-20 22:55:49 '''fromtypingimportListclassSolution:defget(self,n:int)->int:foriinrange(n):if(i|(i+1))==n:# 不是(i or (i + 1))returnireturn-1defminBitwiseArray(self,nums:List[int])->List[int]:return[self.get(t)fortinnums]

Java

/* * @LastEditTime: 2026-01-20 23:04:56 */importjava.util.List;classSolution{privateintget(intn){for(inti=0;i<n;i++){if((i|(i+1))==n){returni;}}return-1;}publicint[]minBitwiseArray(List<Integer>nums){int[]ans=newint[nums.size()];// 是size不是lengthfor(inti=0;i<nums.size();i++){ans[i]=get(nums.get(i));}returnans;}}

Go

/* * @LastEditTime: 2026-01-20 22:58:16 */packagemainfuncminBitwiseArray(nums[]int)[]int{get:=func(nint)int{fori:=0;i<n;i++{if(i|(i+1))==n{returni}}return-1}ans:=make([]int,len(nums))fori,n:=rangenums{ans[i]=get(n)}returnans}

Rust

/* * @LastEditTime: 2026-01-20 23:07:14 */implSolution{fnget(n:i32)->i32{foriin0..n{if(i|(i+1))==n{returni;}}-1}pubfnmin_bitwise_array(nums:Vec<i32>)->Vec<i32>{nums.iter().map(|&num|Self::get(num)).collect()}}

Rust - 压缩版(bushi)

/* * @LastEditTime: 2026-01-20 23:09:46 */implSolution{pubfnmin_bitwise_array(nums:Vec<i32>)->Vec<i32>{nums.iter().map(|&n|{foriin0..n{if(i|(i+1))==n{returni;}}-1}).collect()}}