leetcode 困难题 1521. 找到最接近目标值的函数值

Problem: 1521. 找到最接近目标值的函数值

布尔操作&的性质是越来越小，一个数字a不停的&，a &= c;结果是a越来越小，所以只需要找到 a <= target的时刻，以及这个时刻的上一个a也就是pre = a’，这两者是最靠近target数字的

首先去重的，将连续且相等的数字变成一个数字，然后遍历数组，拿到一个数字的最小值mi，拿到最大值

若最大值mx小于 < target，那么数组的所有数字不管怎么&，结果只会越来越小，所以最靠近target数字的就是最大值mx，直接返回就行

两重循环的，第一重循环，若数字a = arr[i]小于 < target，则直接跳过，不停&越来越小导致越来越远离target

第二重循环，只考虑一种时刻 a <= target || j == n-1，此时才计算最小值，单调的结果a只有当a<=target时刻的当前值a和上一个值pre最靠近target

Code

class Solution { public: int closestToTarget(vector<int>& arr, int target) { int n = arr.size(), a, pre, c, di, mi = INT_MAX; vector<int> now{arr[0]}; for(int i = 1; i < n; i++) { a = arr[i]; if(now.back()!=a) now.push_back(a); } arr = std::move(now); n = arr.size(); int mx = -1; for(int i = 0; i < n; i++) { a = arr[i]; mi = min(abs(target - a), mi); if( mx < a ) mx = a; if(mi == 0) return mi; } if(target > mx) return abs(target - mx); for(int i = 0; i < n; i++) { a = arr[i]; if(a < target) continue; for(int j = i + 1; j < n; j++) { // c = arr[j]; a &= arr[j]; if(a <= target || j == n-1) { mi = min({abs(target - a), mi, abs(pre - target)}); if(a == target) return 0; if(mi == 1) return 1; break; } pre = a; } } return mi; } };