2411. 按位或最大的最小子数组长度
思路:位运算+滑动窗口,时间复杂度0(n*32)。
**遍历每一个元素nums[i],然后看能否改变它前面的元素nums[j]( j<i ),
当(nums[j]|nums[i])==nums[j]时,说明当前元素nums[i]对nums[j]是没有增益效果的,那对剩下的左边元素同样也是无,所以break。
当(nums[j]|nums[i])!=nums[j]时,说明当前元素nums[i]对nums[j]是有增益效果的,细节看注释。
**
C++版本:
class Solution {
public:vector<int> smallestSubarrays(vector<int>& nums) {int n=nums.size();// 答案,默认长度都为1vector<int> v(n,1);// 遍历每一个元素nums[i],然后看能否改变它前面的元素nums[j]( j<i )for(int i=0;i<n;i++){for(int j=i-1;j>=0;j--){// 当前元素nums[i]对nums[j]是没有增益效果的,那对剩下的左边元素同样也是无if((nums[j]|nums[i])==nums[j]) break;// 当前元素nums[i]对nums[j]是有增益效果的nums[j]|=nums[i];v[j]=i-j+1;}}return v;}
};
JAVA版本:
class Solution {public int[] smallestSubarrays(int[] nums) {int n=nums.length;int[] v=new int[n];Arrays.fill(v,1);for(int i=0;i<n;i++){for(int j=i-1;j>=0;j--){if((nums[j]|nums[i])==nums[j]) break;nums[j]|=nums[i];v[j]=i-j+1;}}return v;}
}
GO版本:
func smallestSubarrays(nums []int) []int {n:=len(nums)v:=make([]int,n)for i:=range v {v[i]=1}for i:=0;i<n;i++ {for j:=i-1;j>=0;j-- {if (nums[j]|nums[i])==nums[j] {break}nums[j]|=nums[i]v[j]=i-j+1}}return v
}