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
}