力扣题
// 暴力
class Solution {
public:int closestToTarget(vector<int>& arr, int target) {
int res=INT_MAX;for(int i=0;i<arr.size();i++){
for(int j=i;j<arr.size();j++){
int ans=arr[i];for(int k=i+1;k<=j;k++)ans=ans & arr[k];// cout<<ans<<endl;res=min(res,abs(ans-target));}}return res;}
};// 位运算
class Solution {
public:int closestToTarget(vector<int>& arr, int target) {
int res=INT_MAX;int add=arr[0];vector<int> mem;for(int i=0;i<arr.size();i++){
mem.push_back(arr[i]);for(int j=0;j<mem.size();j++){
mem[j]=mem[j] &arr[i];res=min(res,abs(mem[j]-target));}// add=add & arr[i];// cout<<add<<endl;}return res;}
};class Solution {
public:int closestToTarget(vector<int>& arr, int target) {
int res=INT_MAX;int add=arr[0];vector<int> mem;for(int i=0;i<arr.size();i++){
mem.push_back(arr[i]);for(int j=0;j<mem.size();j++){
mem[j]=mem[j] &arr[i];res=min(res,abs(mem[j]-target));}set<int>s(mem.begin(), mem.end());mem.assign(s.begin(), s.end());}return res;}
};// 线段树+ 滑动窗口class Solution {
public:vector<int> tree;vector<int> data;int closestToTarget(vector<int>& arr, int target) {
int n=arr.size();data.resize(n);for( int i=0;i<n;i++){
data[i]=arr[i];}tree.resize(4*n);buildTree(1,0,n-1);// for(int i=1;i<4*n;i++) cout<<tree[i]<<endl;int l=0;int r=0;int ans=INT_MAX;while(r<n){
int t=query(l,r);if(t<target) r=max(++l,r); //左边界右移 elser++; //右边界右移ans=min(ans,abs(t-target)); //更新结果}// cout<<query(1,1)<<endl;return ans; }void buildTree(int treeindex,int l,int r){
if(l==r) {
tree[treeindex]=data[l];return;}int mid=l+(r-l)/2;buildTree(2*treeindex,l,mid);buildTree(2*treeindex+1,mid+1,r);tree[treeindex]=tree[treeindex*2]& tree[treeindex*2+1];}int query(int queryL,int queryR){
return _query(1,0,data.size()-1,queryL,queryR);}int _query(int treeindex,int l,int r, int queryL,int queryR){
if(l==queryL && r==queryR) return tree[treeindex];int mid=l+(r-l)/2;// cout<<treeindex<<endl;if(queryL>=l&& queryR<=mid){
return _query(treeindex*2,l,mid,queryL,queryR);}else if(queryL>mid&& queryR<=r) return _query(2*treeindex+1,mid+1,r,queryL,queryR);return _query(2*treeindex,l,mid,queryL,mid)& _query(2*treeindex+1,mid+1,r,mid+1,queryR);}
};