###### tags: `Weekly Contest`
# Weekly Contest 351

## [2748. Number of Beautiful Pairs](https://leetcode.com/problems/number-of-beautiful-pairs/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>2 &lt;= nums.length &lt;= 100</code></li>
<li><code>1 &lt;= nums[i] &lt;= 9999</code></li>
<li><code>nums[i] % 10 != 0</code></li>
</ul>

### Solution

#### 時間複雜度: $O(n^2)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    int countBeautifulPairs(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        for(int i=0;i<n;i++){
            int digit;
            while(nums[i] !=0){
                digit = nums[i]%10;
                nums[i]/=10;
            }
            for(int j=i+1;j<n;j++){
                if(__gcd(digit, nums[j]%10)==1)
                    ans++;
            }
        }
        return ans;
    }
};

## [2749. Minimum Operations to Make the Integer Zero](https://leetcode.com/problems/minimum-operations-to-make-the-integer-zero/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= num1 &lt;= 10⁹</code></li>
<li><code><font face="monospace">-10⁹ &lt;= num2 &lt;= 10⁹</font></code></li>
</ul>

### Solution
這題看不出來的話非常難，但題目沒有太多額外的因素干擾，不像 hard 題會有很多可能的解法，這應該也是為什麼這題會被分在 medium。

可以想像簡化版的題目，如果 operation 從減去 $2^i + num2$ 變成減去 $2^i$ 呢。如果我們最少需要花 $k$ 次的 operation 才能將 $num1$ 變成 0，那 $num1$ 應該可以寫成以下的式子:

$num1 = (2^{i_1}+2^{i_2}+...+2^{i_k})$

那顯而易見的，如果要使 $k$ 最小，那 $k$ 就應該等於 $num1$ 的二進位裡 1 的數量。

從這點出發，我們需要排除每次 operation 會額外減去 $num2$ 的困擾，可以思考如果我們最少需要花 $k$ 次 operation 後 $num1=0$ 的情況下，以下這個式子會成立:

$num1=(num2*k)+(2^{i_1}+2^{i_2}+...+2^{i_k})$

其中的 $i_1\text{ ~ }i_k$ 是你這 $k$ 次 operation 中每一輪所選的數字。

那我們可以對以上的式子進行移項，得到:

$num1-(num2*k) = (2^{i_1}+2^{i_2}+...+2^{i_k})$

有了這個式子以後，這個問題又變回我們簡化版的題目了，因為我們只要從 $k=1$ 開始測試是否符合條件就行，那檢測條件就是看 $num1-(num2*k)$ 裡的 1 的數量是否小於等於 $k$，只要小於等於 k 那必可以找到一組合理的解。

有一個額外要注意的點是，還需要檢測 $num1-(num2*k)$ 是否大於等於 $k$，因為 $i$ 的最小值為 0，那 $2^0=1$，所以這段式子 $(2^{i_1}+2^{i_2}+...+2^{i_k})$ 無論如何都會大於等於 $k$，所以如果左式的值小於 $k$ 也是不合法的。可以 trace $num1=85, num2=42$ 這個 case 看看應該就可以理解了。

另外[這篇](https://leetcode.com/problems/minimum-operations-to-make-the-integer-zero/solutions/3679094/linear-search-on-answer-ft-bit-count/)有證明為什麼答案不會超過 60。
#### 時間複雜度: $O(1)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    int count_bit(long long num){ // Count the number of 1s in the binary representation of this number
        int ans = 0;
        while(num){
            if(num&1)
                ans++;
            num>>=1;
        }
        return ans;
    }
    int makeTheIntegerZero(int num1, int num2) {
        if(num2>=num1)
            return -1;
        
        long long sum=num1;
        for(int i=0;sum>0&&i<=65;i++){
            if(count_bit(sum)<=i&&sum>=i)
                return i;
            sum-=num2;
        }
        return -1;
    }
};

## [2750. Ways to Split Array Into Good Subarrays](https://leetcode.com/problems/ways-to-split-array-into-good-subarrays/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= nums.length &lt;= 10⁵</code></li>
<li><code>0 &lt;= nums[i] &lt;= 1</code></li>
</ul>

### Solution
array 中有幾個 1 就可以分幾段，而 1 旁邊的 0 則是每段可以浮動的範圍。
觀察之後得出規律，答案就等於**每個 1 之間的距離**相乘。

寫成數學式子長這樣，假設在這個 array 裡有 $n$ 個 1，而 $dis_i$ 代表第 $i$ 個 1 與第 $i+1$ 個 1 之間的距離。
$$
ans =
\begin{cases}
\prod\limits_{i=1}^{n-1}dis_i, \quad &\text{if }n>1\\
1, \quad &\text{if }n=1\\
0, \quad &\text{if }n=0\\
\end{cases}
$$
#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    int numberOfGoodSubarraySplits(vector<int>& nums) {
        long long ans = 1;
        const int MOD = 1e9+7;
        int idx=-1;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==1){
                if(idx !=-1)
                    ans = ans * (i-idx)%MOD;
                idx = i;
            }
        }
        if(idx == -1)
            return 0;
        else return ans;
    }
};

## [2751. Robot Collisions](https://leetcode.com/problems/robot-collisions/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>1 &lt;= positions.length == healths.length == directions.length == n &lt;= 10⁵</code></li>
<li><code>1 &lt;= positions[i], healths[i] &lt;= 10⁹</code></li>
<li><code>directions[i] == 'L'</code> or <code>directions[i] == 'R'</code></li>
<li>All values in <code>positions</code> are distinct</li>
</ul>

### Solution
這題一開始我以為是像 [BiWeekly Contest 106 的第三題](https://hackmd.io/98yelHNQTyGumeyByPqh0A?view#2731-Movement-of-RobotsMedium)，結果最後才發現跟括號配對問題很像。

在對位置排序的情況下，只有兩個機器人處於 RL 的情況下才會相撞，RR、LL、LR 都不會撞。

因此我們首先對機器人的位置做排序，然後從頭開始迭代，當遇到方向為 R 的機器人時，將它的生命值 push 進 stack 裡面。當遇到方向為 L 的機器人時，如果 stack 裡有東西就代表目前成立了一個 RL 的 pair。碰撞總共有三種情形:
$$
\begin{cases}
left\_health := left\_health-1 , \quad &\text{if }left\_health > right\_health\\
right\_health := right\_health-1, \quad &\text{if }left\_health < right\_health\\
left\_health :=0\ and\ right\_health :=0 , \quad &\text{if }left\_health = right\_health\\
\end{cases}
$$

在所有機器人都迭代結束後，沒有損壞的機器人就是還在 stack 裡方向為 R 的機器人與在迭代過程中將 stack 清空的方向為 L 的機器人，將其生命值照一開始的順序輸出即可。
#### 時間複雜度: $O(n*logn)$

#### 空間複雜度: $O(n)$

程式碼:

class Solution {
public:
    vector<int> survivedRobotsHealths(vector<int>& pos, vector<int>& heal, string dir) {
        int n = pos.size();
        stack<pair<int, int> > si;

        vector<pair<pair<int, int>, pair<int, int> > > pvec(n);
        for(int i=0;i<n;i++)
            pvec[i] = {{pos[i], i}, {heal[i], dir[i]}};
        sort(pvec.begin(), pvec.end());

        vector<int> temp(n), ans;
        for(int i=0;i<n;i++){
            int idx = pvec[i].first.second, d = pvec[i].second.second, h = pvec[i].second.first;
            if(d == 'R')
                si.push({h, idx});
            else {
                while(!si.empty()&&si.top().first<h)
                    h--, si.pop();
                if(si.empty())
                    temp[idx] = h;
                else if(si.top().first == h)
                    si.pop();
                else si.top().first--;
            }
        }
        while(!si.empty()){
            temp[si.top().second] = si.top().first;
            si.pop();
        }
        for(int i=0;i<n;i++){
            if(temp[i])
                ans.push_back(temp[i]);
        }
        return ans;
    }
};