###### tags: `BiWeekly Contest`
# BiWeekly Contest 106

## [2729. Check if The Number is Fascinating](https://leetcode.com/problems/check-if-the-number-is-fascinating/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>100 &lt;= n &lt;= 999</code></li>
</ul>

### Solution

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

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

程式碼:

class Solution {
public:
    bool isFascinating(int n) {
        bool result_array[10] = {};
        int temp[3] = {n,n*2,n*3};
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                int k=temp[i]%10;
                result_array[k] = true;
                temp[i]/=10;
            }
        }

        if(result_array[0] == true) return false;
        for(int i=1;i<10;i++)
        {
            if(result_array[i] == false)
            {
                return false;
            }
        }
        return true;

    }
};

## [2730. Find the Longest Semi-Repetitive Substring](https://leetcode.com/problems/find-the-longest-semi-repetitive-substring/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= s.length &lt;= 50</code></li>
<li><code>'0' &lt;= s[i] &lt;= '9'</code></li>
</ul>

### Solution
暴搜所有子字串，檢查他們是否是 *Semi-Repetitive String*，從中找出長度最長的子字串，並回傳長度即可。
#### 時間複雜度: $O(n^2)$

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

程式碼:

class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int ans = 0;
        for(int i=0;i<s.size();i++){
            for(int j=i;j<s.size();j++){
                if(j-i+1<ans)
                    continue;
                string t = s.substr(i, j-i+1);
                int p = 0;
                for(int k=0;k<t.size()-1;k++){
                    if(t[k] == t[k+1])
                        p++;
                }
                if(p<=1)
                    ans = j-i+1;
            }
        }
        return ans;
    }
};

## [2731. Movement of Robots](https://leetcode.com/problems/movement-of-robots/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>2 &lt;= nums.length &lt;= 10⁵</code></li>
<li><code>-2 * 10⁹ &lt;= nums[i] &lt;= 2 * 10⁹</code></li>
<li><code>0 &lt;= d &lt;= 10⁹</code></li>
<li><code>nums.length == s.length </code></li>
<li><code>s</code> consists of 'L' and 'R' only</li>
<li><code>nums[i]</code> will be unique.</li>
</ul>

### Solution
* Observation 1:
機器人碰撞可以看成沒撞但互相之間編號交換。
* Observation 2:
計算最終所有 pair 的距離的時候，可以利用 prefix sum 的概念將同一編號的機器人所屬的pair的距離一次全部算出來。

根據 Observation 1，可以很輕易的計算出機器人經過 $d$ 秒之後的位置，接下來再使用 Observation 2 快速計算所有 pair 的和，即是答案。

#### 時間複雜度: $O(n*logn)$

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

程式碼:

class Solution {
public:
    const int MOD = 1e9+7;
    int sumDistance(vector<int>& nums, string s, int d) {
        int n=nums.size();
        
        for(int i=0;i<nums.size();i++){
            if(s[i]=='R')
                nums[i]+=d;
            else nums[i]-=d;
        }
        
        sort(nums.begin(), nums.end());
        long long ans = 0, sum=0;
        for(long long i=0;i<n;i++){
            ans = (ans + nums[i]*i-sum)%MOD;
            sum+=nums[i];
        }
        return ans;
    }
};

## [2732. Find a Good Subset of the Matrix](https://leetcode.com/problems/find-a-good-subset-of-the-matrix/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>m == grid.length</code></li>
<li><code>n == grid[i].length</code></li>
<li><code>1 &lt;= m &lt;= 10⁴</code></li>
<li><code>1 &lt;= n &lt;= 5</code></li>
<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

### Solution

#### 時間複雜度: $O()$

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

程式碼: