leetcode
leetcode 1601 ~ 1650
统计异或值在范围内的数对有多少

统计异或值在范围内的数对有多少

难度:

标签:

题目描述

代码结果

运行时间: 252 ms, 内存: 18.7 MB


/* 
 * 思路:
 * 1. 使用Java Stream的flatMap和filter方法来实现。
 * 2. flatMap生成(i, j)的所有可能的组合,并计算其XOR值。
 * 3. filter筛选出XOR值在[low, high]范围内的组合。
 * 4. 计算符合条件的组合的数量。
 */
import java.util.stream.IntStream;

public class BeautifulPairsStream {
    public int countBeautifulPairs(int[] nums, int low, int high) {
        return (int) IntStream.range(0, nums.length)
            .flatMap(i -> IntStream.range(i + 1, nums.length)
                .map(j -> nums[i] ^ nums[j]))
            .filter(xor -> xor >= low && xor <= high)
            .count();
    }
}

解释

方法:

该题解采用了基于计数和二分字典树(Trie)的思想,但实际上未使用树结构。算法通过逐位考察数字,并使用计数器来跟踪相同值的出现次数。对每一位的处理,算法检查当前位的0或1是否会让XOR结果在low和high范围内,并相应地更新计数器。对每个数字,都尝试与可能的XOR匹配进行配对,并调整答案计数。这种方法在处理每一位时都减少了不必要的计算,从而提高效率。

时间复杂度:

O(n log C)

空间复杂度:

O(n)

代码细节讲解

🦆
在该算法中,为什么要将`high`增加1来简化比较?这样做的具体原理是什么?
在算法中将`high`增加1是为了将原本的`[low, high]`范围转换成`[low, high)`(半开区间),这使得在使用位运算处理时更加方便。具体来说,当我们检查二进制的每一位时,增加1后的`high`可以直接用来判断是否达到边界条件,而不需要额外的操作来处理边界情况。这种处理方法可以简化逻辑判断,使代码更易于理解和维护。
🦆
在题解中提到的`计数器`的使用方式是否意味着在每一位的处理过程中都会重新计算所有数字的计数?这种方法效率如何?
题解中的计数器用于跟踪每一位二进制上各数字的出现次数。在每一位的处理过程中,我们不是重新计算所有数字的计数,而是更新计数器来反映右移操作后的新值。这种方法通过避免重新计算已处理位的数字,大大提高了效率,因为它只处理当前需要考虑的位。
🦆
为什么在处理每一位时,需要检查`high & 1`和`low & 1`的值,并根据这些值来增加或减少计数?这种方法的逻辑基础是什么?
在算法中,`high & 1`和`low & 1`用于检查`high`和`low`的当前最低位是否为1。这种检查是因为我们需要确定当前位是否可以通过异或操作达到期望的0或1,从而使得结果仍然在[low, high)区间内。如果`high`的最低位为1,表示高边界在这一位上可以达到1,因此需要加上符合条件的数对计数。同理,如果`low`的最低位为1,表示低边界在这一位上要求至少为1,因此需要减去不符合条件的数对计数。这种基于位的处理方法使得算法在统计符合范围的数对时更加精确和高效。
🦆
题解中提到的`nxt[x >> 1] += c`操作是如何帮助减少不必要的计算的?这一步骤在算法中起什么作用?
在题解中,`nxt[x >> 1] += c`操作是将当前数字`x`右移一位后,将其计数加入到新的计数器`nxt`中。这一步骤的作用是为了在处理下一位之前,预先处理掉当前位的信息,从而只关注剩下的更高位。通过这种方式,算法可以在每一步只关注当前需要处理的位,而不用重新计算所有位,从而减少了不必要的计算量,并使得算法更加高效。

相关问题