LEETCODE 1521. Find a Value of a Mysterious Function Closest to Target 解题思路分析

题目大意：

找到最接近目标值的函数值

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1521

解题思路分析：

这道题我们可以使用暴力枚举大法来解题。既然是暴力解，那么剪枝操作是必须的。因此我们首先要了解到位运算的两个概念：

1. 两个相同数字进行按位与的结果仍是该数字
2. 任意一串数字进行按位与操作，他们的前缀按位与值一定越来越小。解释：按位与与并运算类似，只有两数都是1结果才会是1，除此之外结果都是0，因此按位与操作后，数字上每一位变成0的概率越来越高，数字也相对越变越小。其实换成并运算也不难理解，我们写if文时，并且的条件越多，条件就变得越苛刻，符合条件的范围也越来越小。

搞清上述两个条件后，我们开始暴力求解。题目给出的方程实际上是求一个子数组内所有数字按位与的值。因此我们可以使用2层循环枚举每一个子数组，求出按位与后与target进行比较，找到一个最小值即可。

解题时，第一层循环代表区间左下标，第二层循环代表区间右下标。简单来看，这两层循环实际上就是求以数组中每一位开头的前缀按位与，这并不难理解。关键在于剪枝部分，第一个剪枝点在第一层循环处，根据上文提到的第一个概念，如果两个相同数字的按位与相同的话，那么第一层循环处，当前右区间等于前一个右区间时，可以跳过。比如：[1,1,1,1,1,2,3]，前面一共有5个1，因此，不论1，1&1，1&1&1，1&1&1&1还是1&1&1&1&1都是相同的，他们在与之后的数字进行与操作，也都是相同的结果，这里没有必要重复计算。

第二个剪枝点在第二层循环中，由于前缀按位与的数值是非递增的，因此，当target-前缀按位与的值大于等于全局最小值时，可以中断当前循环。

实现代码：

public int closestToTarget(int[] arr, int target) {
    int min=Integer.MAX_VALUE; // 最小值
    for(int l=0;l<arr.length;l++){ // 循环左边界
        int val = arr[l]; // 区间首元素
        if(l>0&&arr[l]==arr[l-1]) continue; // 剪枝：当前元素等于前元素，跳过
        for(int r=l;r<arr.length;r++){ // 循环右边界
            val &= arr[r]; // 计算当前区间内按位与
            min=Math.min(min,Math.abs(val-target)); // 更新全局最小值
            // 剪枝：因为val会越来越小，所以target-val会越来越大，此时可以跳出
            if(target-val>=min) break;
        }
    }
    return min;
}

本题解法执行时间为211ms。

Runtime: 211 ms, faster than 24.24% of Java online submissions for Find a Value of a Mysterious Function Closest to Target.

Memory Usage: 90.2 MB, less than 23.73% of Java online submissions for Find a Value of a Mysterious Function Closest to Target.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1521-find-a-value-of-a-mysterious-function-closest-to-target-解题思路分析/