X

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.

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