###### tags: `Weekly Contest`
# Weekly Contest 339

## [2609. Find the Longest Balanced Substring of a Binary String](https://leetcode.com/problems/find-the-longest-balanced-substring-of-a-binary-string/)(<font color=#00B8A3>Easy</font>)

限制 :

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

### Solution
窮舉所有substring，check是否是balanced substring，接著更新最大長度回傳即可。

#### 時間複雜度: ***O(n^3)***

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

程式碼:

class Solution {
public:
    int findTheLongestBalancedSubstring(string s) {
        int ans=0;
        for(int i=0;i<s.size();i++){
            for(int j=i;j<s.size();j++){
                string t=s.substr(i, j-i+1);
                if(t.size()%2==0){
                    bool flag=false;
                    for(int k=0;k<t.size()/2;k++){
                        if(t[k] !='0'){
                            flag=true;
                            break;
                        }
                    }
                    for(int k=t.size()/2;k<t.size();k++){
                        if(t[k] !='1'){
                            flag=true;
                            break;
                        }
                    }
                    if(flag==false)
                        ans=max(ans, j-i+1);      
                }
            }
        }
        return ans;
    }
};

### 另解
#### 時間複雜度: ***O(n)***

#### 空間複雜度: ***O(1)***
程式碼:

class Solution {
public:
    int findTheLongestBalancedSubstring(string s) {
        int ans=0;
        for(int i=1;i<s.size();i++)
        {
            if(s[i-1]=='0'&&s[i]=='1')
            {
                int l=0;
                int r=0;
                int lcheck=i-1;
                int rcheck=i;
                while(lcheck>=0)
                {
                    if(s[lcheck]=='1')
                    {
                        break;
                    }
                    l++;
                    lcheck--;
                }
                while(rcheck<s.size())
                {
                    if(s[rcheck]=='0')
                    {
                        break;
                    }
                    r++;
                    rcheck++;
                }
                cout<<l<<' '<<r<<endl;
                int x=min(l,r);
                if(2*x>ans)
                {
                    ans=2*x;
                }
            }
        }
        return ans;
    }
};

## [2610. Convert an Array Into a 2D Array With Conditions](https://leetcode.com/problems/convert-an-array-into-a-2d-array-with-conditions/)(<font color=#FFC011>Medium</font>)

限制 :

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

### Solution
紀錄所有數字在nums中出現的頻率，接著確保每一個row裡的數字都不相同且盡可能的在每個row多擺數字。
#### 時間複雜度: ***O(nlogn)***

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

程式碼:

class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        map<int, int> mp;
        for(auto &num: nums)
            mp[num]++;
        
        vector<vector<int> > ans;
        bool flag=true;
        while(flag){
            flag=false;
            vector<int> temp;
            for(auto it=mp.begin();it !=mp.end();it++){
                if(it->second-->0){
                    flag=true;
                    temp.push_back(it->first);
                }
            }
            if(flag==false)
                break;
            ans.push_back(temp);
        }
        return ans;
    }
};

* 0907 更新

想法就是照著他的排列方式，由大到小的方式排列(因為在結果的二維陣列當中不考慮順序)

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

class Solution {
public:
    vector<vector<int>> findMatrix(vector<int>& nums) {
        int max_freq = 1;
        vector<int> record(201,0);
        vector<vector<int>> results(max_freq);
        for(int i:nums)
        {
            record[i]++;
            if(record[i]>max_freq)
            {
                max_freq = int(record[i]);
                vector<int> v = {i};
                results.push_back(v);
            }
            else
                results[record[i]-1].push_back(i);
        }
        return results;
    }
};

## [2611. Mice and Cheese](https://leetcode.com/problems/mice-and-cheese/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= n == reward1.length == reward2.length &lt;= 10⁵</code></li>
<li><code>1 &lt;= reward1[i], reward2[i] &lt;= 1000</code></li>
<li><code>0 &lt;= k &lt;= n</code></li>
</ul>

### Solution
因為cheese不是被1就是被2吃掉，所以衡量一個cheese是否該被1吃掉的標準就是***reward1\[i]-reward2\[i]***，該值越高該cheese在1的priority就越高。因此，算出每個cheese的值後，greedy的選前k個最該被1吃的cheese給1吃，剩下的給2吃即是答案。
#### 時間複雜度: ***O(nlogn)***

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

程式碼:

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int n=reward1.size();
        
        vector<pair<int, int > > cost(n);
        for(int i=0;i<n;i++)
            cost[i]={reward1[i]-reward2[i], i};
        
        sort(cost.begin(), cost.end(), greater<pair<int, int > >());
        
        int ans=0;
        for(int i=0;i<k;i++)
            ans+=reward1[cost[i].second];

        for(int i=k;i<n;i++)
            ans+=reward2[cost[i].second];
        
        return ans;
        
        
    }
};

### Optimized solution
因為只需要找出前k個元素，可以使用[nth_element](https://en.cppreference.com/w/cpp/algorithm/nth_element)這個函式將複雜度從O(nlogn)降到O(n)。
#### 時間複雜度: ***O(n)***

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

程式碼:

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int n=reward1.size();
        
        vector<pair<int, int > > cost(n);
        for(int i=0;i<n;i++)
            cost[i]={reward1[i]-reward2[i], i};
        
        nth_element(cost.begin(), cost.begin()+k, cost.end(), greater<pair<int, int> >());
        
        int ans=0;
        for(int i=0;i<k;i++)
            ans+=reward1[cost[i].second];

        for(int i=k;i<n;i++)
            ans+=reward2[cost[i].second];
        
        return ans;
        
        
    }
};

## [2612. Minimum Reverse Operations](https://leetcode.com/problems/minimum-reverse-operations/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>1 &lt;= n &lt;= 10⁵</code></li>
<li><code>0 &lt;= p &lt;= n - 1</code></li>
<li><code>0 &lt;= banned.length &lt;= n - 1</code></li>
<li><code>0 &lt;= banned[i] &lt;= n - 1</code></li>
<li><code>1 &lt;= k &lt;= n </code></li>
<li><code>banned[i] != p</code></li>
<li>all values in <code>banned</code> are <strong>unique</strong> </li>
</ul>

### Solution

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

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

程式碼: