LeetCode Weekly Contest 281

1. Count Integers With Even Digit Sum

Naive.

c++

class Solution
{
public:
    
    int digitSum(int x)
    {
        int ret = 0;
        
        while (x > 0)
        {
            ret += x % 10;
            x = x / 10;
        }
        
        return ret;
    }
    
    int countEven(int num)
    {
        int ans = 0;
        
        for (int i = 1; i <= num; i++)
        {
            if (digitSum(i) % 2 == 0)
            {
                ans++;
            }
        }
        
        return ans;
    }
};

2. Merge Nodes in Between Zeros

Naive.

c++

/**
 * 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)
    {
        vector<int> nums;
        
        int current = 0;
        
        for (ListNode *p = head->next; p != NULL; p = p->next)
        {
            if (p->val == 0)
            {
                nums.push_back(current);
                current = 0;
            }
            else
            {
                current += p->val;
            }
        }
        
        ListNode *ret = NULL;
        
        for (int i = nums.size() - 1; i >= 0; i--)
        {
            ret = new ListNode(nums[i], ret);
        }
        
        return ret;
    }
};

3. Construct String With Repeat Limit

Greedy.

c++

class Solution
{
public:
    string repeatLimitedString(string s, int repeatLimit)
    {
        unordered_map<char, int> cnt;
        
        for (auto &c : s)
        {
            cnt[c]++;
        }
        
        char lastChr = '?';
        int lastCnt = 0;
        
        string ans = "";
        
        while (true)
        {
            char opt = '?';
            
            for (char c = 'z'; c >= 'a'; c--)
            {
                if (cnt[c] == 0)
                {
                    continue;
                }
                
                if (lastChr == c && lastCnt + 1 > repeatLimit)
                {
                    continue;
                }
                
                opt = c;
                break;
            }
            
            if (opt == '?')
            {
                break;
            }
            
            ans.push_back(opt);
            cnt[opt]--;
            
            if (lastChr == opt)
            {
                lastCnt++;
            }
            else
            {
                lastChr = opt;
                lastCnt = 1;
            }
        }
        
        return ans;
    }
};

4. Count Array Pairs Divisible by K

Let's say $C_i$ represents the number of integers where $num \mod k = i$ .
First, let's count the pairs $(a, b)$ where $a \mod k = 0 \land b \mod k = 0$ : $C_0 * (C_0 - 1) \div 2$ .
Then, let's count the pairs $(a, b)$ where $a \mod k = 0 \land b \mod k \neq 0$ : $C_0 * \sum_{i = 1}^{k - 1}{C_i}$ .
And now, let's dicuss the pairs where $(a, b)$ $(a, b)$ where two $a \mod k \neq 0 \land b \mod k \neq 0$ $a mod k \neq = 0 \land b mod k \neq = 0$ :
- We know there must be $1 \leq p \leq k$ to make $a \times b = k \times p$ where.
- A simple idea is to enumerate $a$ and $k \times p$ where the time complexity is $O(k^2)$ .
- And we can further improve the enumeration of $k \times p$ by $delta = gcd(a, k)$ so the time complexity is $O(k \log(k))$ .

c++

#pragma GCC optimize ("O3")

typedef long long ll;

class Solution
{
public:
    
    ll gcd(int a, int b)
    {
        if (b == 0)
        {
            return a;
        }
        
        return gcd(b, a % b);
    }
    
    long long coutPairs(vector<int>& nums, int k)
    {
        ll cnt[100000] = { 0 };
        
        for (auto &num : nums)
        {
            cnt[num % k]++;
        }
        
        ll ans = (cnt[0] * (cnt[0] - 1)) / 2;
        
        for (ll i = 1; i < k; i++)
        {
            ans += cnt[i] * cnt[0];
        }
        
        for (ll a = 2; a < k; a++)
        {
            ll t = gcd(a, k);
            ll d = k * a / t;
            
            for (ll kp = d; kp <= ((ll) (k - 1)) * k; kp += d)
            {
                if (kp % a != 0)
                {
                    continue;
                }
                
                ll b = kp / a;
                
                if (b >= k)
                {
                    continue;
                }
                
                if (a < b)
                {
                    ans += cnt[a] * cnt[b];
                }
                else if (a == b)
                {
                    ans += (cnt[a] * (cnt[a] - 1)) / 2;
                }
            }
        }
        
        return ans;
    }
};

LeetCode Weekly Contest 281

1. Count Integers With Even Digit Sum

2. Merge Nodes in Between Zeros

3. Construct String With Repeat Limit

4. Count Array Pairs Divisible by K

COMMAND INTERFACE

:help aguang.xyz