Leetcode weekly buckle 281

6012. Count the number of integers whose sum of figures is even

Ideas Preprocessing

Time complexity Inquire about $O(1)$, Preprocessing $O(n)$

Spatial complexity $O(n)$

Preprocess the answers of all numbers before querying , In this way, you can $O(1)$ Get the answer .

With the help of std::call_once The preprocessing logic can be executed only once .

// cnt  Store answers 
int cnt[1001] = {
    0};
//  Preprocessing functions 
void init() {
    
    for (int i = 1; i <= 1000; i++) {
    
        int sum = 0;
        for (int j = i; j; j /= 10) {
    
            sum += j % 10;
        }
        cnt[i] = cnt[i-1] + ((sum%2) ? 0 : 1);
    }
}
// std::call_once  Tag variables required by the function 
std::once_flag flag;

class Solution {
    
public:
    int countEven(int num) {
    
        //  Try calling a preprocessor 
        std::call_once(flag, init);
        //  Return to the answer 
        return cnt[num];
    }
};

6013. Merge nodes between zeros

Ideas The basic operation of the linked list

Time complexity $O(n)$

Spatial complexity $O(1)$

I think this problem mainly focuses on the traversal and deletion of linked lists .

Equipped with ListNode *cur Initially, it points to the head node . Use cur Traverse the linked list from beginning to end .

Equipped with ListNode *zero Point to the last zero node in the traversed nodes . Initially, it points to the head node .

According to the definition of the above variables , In the process of traversing ：

• The merge logic becomes ： zero->val += cur->val.
• The deletion logic becomes ： whenever cur Point to a zero node , Will zero->next = cur; zero = cur. Namely throw away Last zero node And Current zero node The node between , And update the zero.

It's not hard to find out , After the traversal is over , The value of the last node is still zero , Need to delete .

Equipped with ListNode *truncate Point to the penultimate zero node in the traversed nodes . Initially, point to the head node . When the traversal is over , perform tuncate->next = nullptr The above problems can be solved .

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
class Solution {
    
public:
    ListNode* mergeNodes(ListNode* head) {
    
        ListNode *truncate = head;
        for (ListNode *zero = head, *cur = head->next; cur != nullptr;cur = cur->next) {
    
            if (cur->val == 0) {
    
                // zero  It's going to jump .
                //  Before jumping , to update  truncate.
                //  such  truncate  It points to the penultimate zero node .
                truncate = zero;
                
                //  Delete node 
                zero->next = cur;
                // zero  Jump to the  cur
                zero = cur;
            } else {
    
                //  Merge 
                zero->val += cur->val;
            }
        }
        //  Discard the last zero node 
        truncate->next = nullptr;
        return head;
    }
};

6014. Construct a string that restricts repetition

Ideas greedy

Time complexity $O(n\ast c)$.$n$ Is the length of a string ,$c$ Is the number of character types .

Spatial complexity $O(n+c)$

Set the string $anw$ Store answers , Initially empty .

Because if the dictionary order is the largest , So always choose as large a character as possible to append to $anw$ The tail .

The process of selecting characters at one time is as follows ：

• If , $s$ The maximum characters in the and $anw$ The tail characters are different , Or the repetition limit will not be exceeded after adding , The character is changed from $s$ Delete , And added to $anw$.
• otherwise , Change a sub large character from $s$ Delete in , And added to $anw$.

Most repeat $n$ Second selection process , The largest $anw$.

class Solution {
    
public:
    string repeatLimitedString(string s, int repeatLimit) {
    
        //  Count the number of occurrences of each character 
        int cnt[26] = {
    0};
        for (auto c : s) {
    
            cnt[c-'a']++;
        }
        
        // anw  Store answers 
        string anw;
        // rep anw The number of consecutive repeated characters in the tail 
        int rep = 0; 
        // pre anw  Number of trailing characters , Easy to handle anw Empty .
        char pre = -1;
        // n  Second selection process 
        for (int op = 0; op < s.size(); op++) {
    
            //  Start with the big ones 
            for (int i = 25; i >= 0; i--) {
    
                //  Check the  i  Whether the characters meet the conditions 
                if (cnt[i] <= 0) continue;
                if (i == pre && rep >= repeatLimit) continue;
                
                //  Update data 
                anw += char(i+'a');
                if (i == pre) rep++;
                else rep = 1;
                pre = i;
                cnt[i]--;
                
                //  Only one character can be selected at a time 
                break;
            }
        }
        return anw;
    }
};

6015. Statistics can be K The number of subscript pairs divisible

Ideas greatest common divisor

Time complexity $O(n\sqrt{V})$

Spatial complexity $O(V)$

If three positive integers $x$, $y$,$k$ Satisfy $x\ast y$ By $k$ to be divisible by .

be $k$ All the prime factors of must be contained in $x\ast y$ In the prime factor set of . such as ,

• $k=60=2\ast 2\ast 3\ast 5$
• $x=6=2\ast 3$
• $y=10=2\ast 5$

obviously $6\ast 10$ Can be $60$ to be divisible by .

According to the above conclusion , We can enumerate $num{s}_i$, Find out what's not there $num{s}_i$ Medium $k$ The quality factor of , Let the product of these prime factors be $p_i$, Then there are
$$p_i=\frac{k}{gcd(num{s}_i,k)}$$

then , According to the statistics $nums[0..i-1]$ How many numbers in are $p_i$ to be divisible by , The quantity is recorded as $c_i$. The answer is ：
$$anw=\sum _{i=0}^{n-1}{c}_i$$

It can be understood together with notes ~

class Solution {
    
public:
    // cnt[i]  Express  nums  Middle energy quilt  i  Number of divisible numbers 
    int cnt[100001] = {
    0};
    
    long long coutPairs(vector<int>& nums, int k) {
    
        // anw  Record answer 
        int64_t anw = 0;
        //  Start enumerating numbers  nums[i]
        for(int i = 0; i < nums.size(); i++) {
    
            //  Calculation  p
            int p = k / __gcd(nums[i], k);
            //  Add up  nums[0..i-1]  Within the interval , Can be  p  The number of divisible numbers .
            anw += cnt[p];
            
            //  to update  cnt. take  nums[i]  Count it in , Be careful  nums[i]  Can be divided by multiple numbers .
            for (int j = 1, s = sqrt(nums[i]); j <= s; j++) {
    
                if (nums[i]%j == 0) {
    
                    // j  aliquot  nums[i], be  nums[i]/j  Can also divide  nums[i].
                    //  But pay attention to  j == nums[i]/j  The circumstances of , Avoid duplicate Statistics .
                    cnt[j]++;
                    if (nums[i]/j != j) {
    
                        cnt[nums[i]/j]++;
                    }
                } 
            }
        }
        return anw;
    }
};