Leetcode one problem of the day and the next problem of the day brush problem notes 23/30

Writing in the front

This is the 23rd day of my participation in Gwen Challenge

About to graduate, only to find himself in the interview algorithm hanging hammer. There is no way to zero based identity and classmates to join the force buckle brush problem army. My classmates are very good, they are usually just modest, verbally said that they will not, and I really will not… Nuggets encourage new people to blog every day, I also join in a lively, record every day brush the first two questions, these two questions I do. I plan to brush five questions every day. For the other questions, I can only memorize the routine by force and will not post them in my blog.

I am really just a vegetable chicken, what do not want to solve the problem from my reference, coding habits also need to improve, if you want to find brush problem master ask questions, I think it is better to go to the palace water sanye brush problem diary this big guy. I try not to see the solution of the problem before I make it, so as not to collide with the content of the big guy.

In addition, I also hope to have the leisure of the big guy to provide some higher clear problem-solving ideas to me, welcome to discuss ha!

Good nonsense does not say to begin the first two questions of the twenty-third day!

2021.6.23 One question of the day

Offer 15. Number of 1s in binary

This question is a simple question, but there are a lot of gameplay, the interview can be given according to the question requirements of a variety of optimization, this reference link gives a lot of interesting solutions, you can go to have a look.

I’m going to count the last 1 by adding the adjacent bits.

class Solution {
public:
    int hammingWeight(uint32_t n) {
        n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
        n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
        n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
        n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
    returnn ; }};Copy the code

And this is easy to explain, if you expand out the hexadecimal numbers, you can see a full binary tree, layer by layer, and you add up the number of 1s and you end up with all the 1s at the root node.

0101 0101 0101 0101 0101 0101 0101 0101 (0x55555555) ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ (n) ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^  (n >> 1) 0^0^ 0^0^ 0^0^ 0^0^ 0^0^ 0^0^ 0^0^ 0^0^ (result) 0011 0011 0011 0011 0011 0011 0011 0011 (0x33333333) ^ ^ ^ ^ ^ ^ ^ ^ (n) ^ ^ ^ ^ ^ ^ ^ ^ (n >> 2) 000^ 000^ 000^ 000^ 000^ 000^ 000^ 000^ (result) 0000 1111 0000 1111 0000 1111 0000  1111 (0x0f0f0f0f) ^ ^ ^ ^ (n) ^ ^ ^ ^ (n >> 4) 0000 000^ 0000 000^ 0000 000^ 0000 000^ (result) 0000 0000 1111 1111 0000 0000 1111 1111 (0x00ff00ff) ^ ^ (n) ^ ^ (n >> 8) 0000 0000 0000 000^ 0000 0000 0000 000^ (result) 0000 0000 0000 0000 1111 1111 1111 1111 (0x0000ffff) ^ (n) ^ (n >> 16) 0000 0000 0000 0000 0000 0000 0000 000^ (result)Copy the code

One of the following questions per day

Refer to Offer 56-ii. Number of occurrences in array II

We can still do it in the top position, so let’s do it this way

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0, sub = 0; i < 32; ++i, sub = 0) {
            for (auto &n : nums) sub += ((n >> i) & 1);
            if (sub % 3) res |= (1 << i);
        }
        returnres; }};Copy the code

For example, the 32-bit representation of a number is still used, using nums = [9,1,7,9,7,9,7].

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 (7) 0000 0000 0000 0000 0000 0000 (9) 0000 0000 0000 0000 0000 0000 (7 0000 0000 0000 0000 0000 0000 0000 (9) 0000 0000 0000 0000 0000 0111 (7) 0000 0000 0000 0000 0000 3337 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001Copy the code

summary

Bitwise calculations are a fun thing to do, but if you have a binary calculator or a piece of paper handy, just draw a picture of it and you can get some ideas. Bit operation is only a more clever method, but the efficiency is not necessarily the best, it still depends on the specific topic and specific algorithm.

Refer to the link

Algorithm – Find the number of 1’s in binary