梅州生态建设有限公司网站,定南建设银行网站点,境外注册网站,建德建设局官方网站掩码异或的作用前言一、按位与为零的三元组二、统计分组1、map统计分组2、异或掩码总结参考资料前言
当a b 0时#xff0c;我们能够很清楚的知道b是个什么值#xff0c;b 0 - a -a#xff0c;如果当a b 0时#xff0c;我们能够很清楚的知道b是什么值吗#xf…
掩码异或的作用前言一、按位与为零的三元组二、统计分组1、map统计分组2、异或掩码总结参考资料前言
当a b 0时我们能够很清楚的知道b是个什么值b 0 - a -a如果当a b 0时我们能够很清楚的知道b是什么值吗
一、按位与为零的三元组 二、统计分组
1、map统计分组
像这种组合题纯靠for循环遍历出来的都会超时一般用map/切片统计通过乘法/加法快速组合或者说抽象的方式组合只在乎组合的次数不在乎具体的组合情况。 方法先两层for循环进行统计两数与完之后的分组情况再来两层for循环来寻找分组数据和第3个数与的情况。
func countTriplets(nums []int) int {// 分组cnt : map[int]int{}for i : 0;i len(nums);i {for j : 0;j len(nums);j {cnt[nums[i] nums[j]]}}// 计数ans : 0for k,v : range cnt {if k 0 {ans v * len(nums)continue}for _,n : range nums {if n k 0 {ans v}}}return ans
}2、异或掩码
上面的解法只是进行了简单的分组但是并未利用到与操作的特性我们可以仔细分析与操作的特性看能不能将第二个双层for循环变成单层for循环。
与操作为0说明了三个数的每一位必定有一个0及以上。 假设第一个双层for循环得到了一些数这些数要和nums再组合一次当前者的任意一位为1时后者必须是0当前者的任意一位为0时后者可0可1。
可0可1那怎么记录前者的“相反数”啊 将一个值整成多份每份将一个0变1并记录这种数有一个这样就不管匹配的什么可0可1了。 我们需要记录所谓的相反数可通过掩码异或的方式来将0变11变0再不断组合1的情况并记录这些相反数的个数。
func countTriplets(nums []int) int {// 分组统计cnt : make([]int,1 16)cnt[0] len(nums)const MAX 1 16 - 1for i : 0;i len(nums);i {mask : nums[i] ^ MAXfor j : mask;j 0;j (j - 1) mask {cnt[j]}}// 计数ans : 0for _,a : range nums {for _,b : range nums {ans cnt[a b] // 刚好01互补mask异或是个好东西}}return ans
}总结
1困难题都是各种组件组合而成所以训练好各种问题的解决方式再分析困难题的组合情况就能快速解答困难题。 2异或的作用蛮大的配合掩码能将一个数的所有二进制取反。
参考资料
[1] LeetCode 按位与为零的三元组
