5467. 找到最接近目标值的函数值 [hard]
5467. 找到最接近目标值的函数值 [hard]
198场周赛题目，微软赛场
Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。
请你返回 |func(arr, l, r) - target| 的最小值。
请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。
示例 1：
输入：arr = [9,12,3,7,15], target = 5
输出：2
解释：所有可能的 [l,r] 数对包括 [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]]， Winston 得到的相应结果为 [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0] 。最接近 5 的值是 7 和 3，所以最小差值为 2 。
示例 2：
输入：arr = [1000000,1000000,1000000], target = 1
输出：999999
解释：Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000 ，所以最小差值为 999999 。
示例 3：
输入：arr = [1,2,4,8,16], target = 0
输出：0
提示：
- 1 <= arr.length <= 10^5
- 1 <= arr[i] <= 10^6
- 0 <= target <= 10^7
通过次数885 | 提交次数3,051
Third Try
2020-07-20
这又是看题解才了解到的另一种解法，太简洁了。
首先依然是“位与”的操作只会导致数字越来越小，其次对于每个固定的R边界值，最多只有log(arr[R])个不同的结果。因为arr[R]&arr[?]任何值，都会导致其位置上的1越来越少，但0却不会变成1。对于10^6最大值的元素，最多只有20个bit. 因此遍历过程中，对于每个遍历到的R边界，前面有效的数值只有20种可能，遍历完该元素最多也只有20种可能。因此总的遍历次数最多是20 * n， 相比N^2来说要简略多了。 某种意义上仍然属于O(N)等级的算法。
每次循环过程中，维护的只是前面的最多20种可能，而不需要考虑r之前的r种可能。 本来的思维是固定l，然后不断往后走遍历r。这里的思路是一遍遍历的过程中，把每个瞬间的r固定住了，认为前面遍历的是不同的l，这也是思维的一点不同。
bingo, 没想到还有这么简略的写法。
不过这写法跟目标找到l/r不符，如果要找到具体的l和r，也是挺麻烦。
class Solution(object):
def closestToTarget(self, arr, target):
"""
:type arr: List[int]
:type target: int
:rtype: int
"""
valid = set()
rv = float('inf')
for a in arr:
nvalid = set()
valid.add(a)
for t in valid:
r = t & a
nvalid.add(r)
rv = min(rv, abs(r - target))
valid = nvalid
return rv
Second Try
2020-07-19
重点依然是需要理解到“位与(bit and, &)”操作，是一个只会不断变小的运算符。 其次是当两侧元素相等时，结果不变。
要是没有相关背景知识和经验，谁会想到这题其实是进行暴力搜索，然后利用这一点进行强行跳出。
其次在测试过程中可以发现重复元素会极大的浪费测试，因此需要去掉相邻的重复元素，毕竟不会影响到结果。
第一波直接去掉相邻的重复元素，仅保留一个。不关注如果在窗口中出现已经出现的元素是否要跳过。另外对于本来的left， right已经不关心，要找回left, right感觉还是有点麻烦，感觉跟题意背道而驰了。
而且如果构造出其他合适的但不重复的测试集，没法暴力方法通过才对。
class Solution:
def closestToTarget(self, arr: List[int], target: int) -> int:
# 第一波直接去掉相邻的重复元素，仅保留一个。
# 不关注如果在窗口中出现已经出现的元素是否要跳过
# 其次对于本来的left， right已经不关心
narr = []
for i in range(len(arr)):
if i > 0 and arr[i] == arr[i - 1]:
continue
narr.append(arr[i])
rv = float('inf')
for i in range(len(narr)):
t = narr[i]
for j in range(i, len(narr)):
t &= narr[j]
rv = min(rv, abs(t - target))
if t <= target:
break
return rv
First Try
本来还以为要考虑到二进制里面位的操作，感觉有点头疼，也没有时间了，周赛中直接放弃了尝试，也是看题解才理解到的该题的特点。
具体特点看Second Try中的内容。
class Solution:
def closestToTarget(self, arr: List[int], target: int) -> int:
# 负数呢？ 靠，提示里面发现arr没有负数
# 发现没有用上set的那一步，这里遇到一个10万长度的相同数组，还是超时了
# print("len", len(arr))
arr = list(set(arr))
rv = [float('inf'), 0, 0]
n = len(arr)
for i in range(n):
if i > 0 and arr[i] == arr[i - 1]:
continue
window = set()
t = arr[i]
for j in range(i, n):
if j > i and arr[j] == arr[j - 1]:
continue
if arr[j] in window:
continue
t &= arr[j]
if abs(t - target) < rv[0]:
rv = [abs(t - target), i, j]
if t <= target:
break
# 不是在t <=target的时候才找到最小值，可能在前一个刚好大于target的地方才是最小值
# if t <= target:
# if abs(t - target) < rv[0]:
# rv = [abs(t - target), i,j]
# print("catch one", t, rv)
# break
window.add(arr[j])
# print("rv", rv)
return rv[0]
- failed try
不是在t <=target的时候才找到最小值，可能在前一个刚好大于target的地方已经最小值，因此每个临时结果都需要进行比较才行。 于是又贡献了一个一开始莫名其妙的bug.
class Solution:
def closestToTarget(self, arr: List[int], target: int) -> int:
# 负数呢？ 靠，提示里面发现arr没有负数
rv = [float('inf'), 0, 0]
n = len(arr)
for i in range(n):
window = set()
t = arr[i]
for j in range(i, n):
if arr[j] in window:
continue
t &= arr[j]
if t <= target:
if abs(t - target) < rv[0]:
rv = [abs(t - target), i,j]
print("catch one", t, rv)
break
window.add(arr[j])
if abs(t - target) < rv[0]:
rv = [abs(t - target), i, n - 1]
print('catch ano', rv)
print("rv", rv)
return rv[0]