Number of high-quality number pairs [bit operation characteristics + abstract ability evaluation + grouping fast statistics]

Preface

Bit operation is the most basic calculation of computer , Is the fastest way to calculate , And or not have their own characteristics ; I understand the abstract ability test as a kind of Take the core to remove the burden The ability of ; Group fast statistics , We don't have to focus on numbers , Maybe it doesn't make sense , It's about what you need , Abstract grouping .

One 、 The number of high-quality pairs

Two 、 Ideas and optimization process

package competition.single303;

import java.util.HashSet;
import java.util.Set;

public class CountExcellentPairs {
    
    /*  What's the relationship between the front and back numbers ？ The number increases later ,  And will have 1 The place is , Or both 1,0/1 Count all .  When two numbers or , Non overlapping 1 Count it , Overlapping parts 1 Only half of it , But it doesn't exactly overlap with , And the overlapping part is counted as half .  So two numbers 1 The number of and , It is after it  +  Or later 1 The number of . */
    public long countExcellentPairs(int[] nums, int k) {
    
        //  The idea of grouping fast statistics .
        //  We don't care which number and which number make up a good pair , We only care about the number bit = 1, Care about both bit = 1 Whether the sum of the number of is greater than k nothing more .
        //  You can get rid of some cumbersome records irrelevant to the question  & context, Face the problem , It can reduce the time complexity , Even the key to solving problems .
        // idea： take bit = 1 The same number records how many , as long as bit Number equals to so and so and other numbers , This is the core message , Grasp the lifeline .
        int[] bit = new int[33];//  Grouping ideas , take bit Number abstracts , And don't care about other cumbersome information .
        Set<Integer> pool = new HashSet<>();//  duplicate removal .
        for (int num : nums) {
    
            if (!pool.contains(num)) bit[Integer.bitCount(num)]++;

            pool.add(num);
        }
        /* //  Why would I write such code , What if you find a way of thinking , I don't know what I want , Do not know the contact point with the problem , Still can't write low complexity code . int[] bit = new int[nums.length]; for (int i = 0; i < nums.length; i++) bit[i] = Integer.bitCount(nums[i]); */
        long ans = 0;
        for (int i = 0; i < 33; i++) {
    
            for (int j = Math.max(0, k - i); j < 33; j++) {
    
                ans += bit[i] * bit[j];
            }
        }
        return ans;
        /* review  More analysis , Find the operation / The connection between conditions and problems , Write more on paper , Find the law , Look for the feeling . */
    }
}

summary

1） Each operation has its own characteristics , Problems related to bit operation , Also write and draw more on paper , Find feelings and rules .
2） Usually practice more , During the competition, there is not so good energy condition to analyze too many and too deep things , Lower your thinking limit through practice / The lower limit of brain activity is raised .
3） Abstract ability can be simply understood as taking the core to remove impurities .
4） It's the second time to see such a grouping fast statistics routine , Greatly reduce the time complexity , The core is to grasp the lifeline , Get rid of useless information , Let useful information not be hampered by useless information irrelevant to this topic, and it cannot be compressed .

reference

[1] LeetCode The number of high-quality pairs