###### tags: `Weekly Contest`
# Weekly Contest 347

## [2710. Remove Trailing Zeros From a String](https://leetcode.com/problems/remove-trailing-zeros-from-a-string/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 &lt;= num.length &lt;= 1000</code></li>
<li><code>num</code> consists of only digits.</li>
<li><code>num</code> doesn't have any leading zeros.</li>
</ul>

### Solution
照題意做，移除後綴0即可。
#### 時間複雜度: $O(n)$

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

程式碼:

class Solution {
public:
    string removeTrailingZeros(string num) {
        for(int i=num.size()-1;i>=0;i--){
            if(num[i] == '0')
                num.pop_back();
            else break;
        }
        return num;
    }
};

## [2711. Difference of Number of Distinct Values on Diagonals](https://leetcode.com/problems/difference-of-number-of-distinct-values-on-diagonals/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>m == grid.length</code></li>
<li><code>n == grid[i].length</code></li>
<li><code>1 &lt;= m, n, grid[i][j] &lt;= 50</code></li>
</ul>

### Solution
這題難點應該是看懂題目，看懂題目後，用set去統計不同元素有幾個之後，即可算出ans。
> p.s.在n, m很大且grid[i][j]的範圍很小時，可以考慮用counting sort將時間複雜度壓成$O(n*m*min(n, m)*range(grid[i][j]))$
#### 時間複雜度: $O(n*m*min(n, m)*log(min(n, m)))$

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

程式碼:

class Solution {
public:
    vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
        int n=grid.size(), m=grid[0].size();
        vector<vector<int> > ans(n, vector<int>(m));
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                set<int> si;
                int nowi = i+1, nowj = j+1, sum;
                while(nowi<n&&nowj<m){
                    si.insert(grid[nowi][nowj]);
                    nowi++, nowj++;
                }
                sum = si.size();
                
                si.clear();
                nowi = i-1, nowj = j-1;
                while(nowi>=0&&nowj>=0){
                    si.insert(grid[nowi][nowj]);
                    nowi--, nowj--;
                }
                sum -= si.size();
                sum = abs(sum);
                
                ans[i][j] = sum;
            }
        }
        
        return ans;
    }
};

## [2712. Minimum Cost to Make All Characters Equal](https://leetcode.com/problems/minimum-cost-to-make-all-characters-equal/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= s.length == n &lt;= 10⁵</code></li>
<li><code>s[i]</code> is either <code>'0'</code> or <code>'1'</code></li>
</ul>

### Solution
使用複雜的dp解，令$dp[i][j] 等於將前i個字元全部轉成j所需要的cost$，由此可以導出dp式是:

$\begin{cases}
dp[i][0] = min(dp[i-1][1]+i, dp[i-1][0]),\qquad\qquad\qquad\qquad\quad \text{if}\quad s[i]=\text{'0'} \\
dp[i][1] = min(dp[i-1][1]+i+i+1, dp[i-1][0]+i+1),\qquad\ \ \text{if}\quad s[i]=\text{'0'} \\
\end{cases}$

$\begin{cases}
dp[i][0] = min(dp[i-1][1]+i+1, dp[i-1][0]+i+i+1),\qquad\ \ \text{if}\quad s[i]=\text{'1'} \\
dp[i][1] = min(dp[i-1][1], dp[i-1][0]+i),\qquad\qquad\qquad\qquad\quad \text{if}\quad s[i]=\text{'1'} \\
\end{cases}$

因為這個dp式只考慮到第一個操作，但題目是有第二個操作的，所以需要再建立第二個dp array存取只考慮第二個操作的結果。

$dp1[i][j]的意義是將前i個字元全部轉成j所需要的cost，dp2[i][j]的意義是將第i+1個字元後全部轉成j所需要的cost。$
所以答案就是:
$ans = min\{\ min(dp1[i][0]+dp2[i][0], dp1[i][1]+dp2[i][1])\ \}$
#### 時間複雜度: $O(n)$

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

程式碼:

class Solution {
public:
    long long minimumCost(string s) {
        long long dp1[100005][2] = {0};
        long long dp2[100005][2] = {0};
        
        for(int i=1;i<=s.size();i++){
            if(s[i-1] == '1'){
                dp1[i][1] = min(dp1[i-1][1], dp1[i-1][0]+i-1);
                dp1[i][0] = min(dp1[i-1][0]+i+i-1, dp1[i-1][1]+i);
            }
            else {
                dp1[i][1] = min(dp1[i-1][1]+i-1+i, dp1[i-1][0]+i);
                dp1[i][0] = min(dp1[i-1][0], dp1[i-1][1]+i-1);
            }
        }
        
        for(int i=s.size(), j=0;i>=1;i--,j++){
            if(s[i-1] == '1'){
                dp2[i][1] = min(dp2[i+1][1], dp2[i+1][0]+j);
                dp2[i][0] = min(dp2[i+1][0]+j+j+1, dp2[i+1][1]+j+1);
            }
            else {
                dp2[i][1] = min(dp2[i+1][1]+j+j+1, dp2[i+1][0]+j+1);
                dp2[i][0] = min(dp2[i+1][0], dp2[i+1][1]+j);
            }
        }
        
        long long ans = 1e18;
        
        for(int i=1;i<=s.size();i++)
            ans = min(ans, min(dp1[i][0]+dp2[i+1][0], dp1[i][1]+dp2[i+1][1]));
        
        return ans;
        
    }
};

### Optimized Solution
參考[這篇](https://leetcode.com/problems/minimum-cost-to-make-all-characters-equal/solutions/3570185/single-pass-iterative-easy-explanation-think-greedy-one-line-clean-code-c/)，只需要pass string一次，檢查operation 1與operation 2哪個需要的cost低，將其加總就是答案了。
#### 時間複雜度: $O(n)$

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

程式碼:

class Solution {
public:
    long long minimumCost(string s) {
        long long ans = 0;
        for(int i=0;i<s.size()-1;i++){
            if(s[i] !=s[i+1])
                ans += min(i+1, int(s.size())-i-1);
        }
        return ans;
    }
};

## [2713. Maximum Strictly Increasing Cells in a Matrix](https://leetcode.com/problems/maximum-strictly-increasing-cells-in-a-matrix/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>m == mat.length </code></li>
<li><code>n == mat[i].length </code></li>
<li><code>1 &lt;= m, n &lt;= 10⁵</code></li>
<li><code>1 &lt;= m * n &lt;= 10⁵</code></li>
<li><code>-10⁵ &lt;= mat[i][j] &lt;= 10⁵</code></li>
</ul>

### Solution

很明顯的dp題，最單純的想法就是將每個node可以跳的最大格數算出來，如果其他node可以跳到該node，他可以跳的最大格數就等於該node可以跳的最大格數+1。

dp的pseudo式是:

$當前node可以跳到的最大格數 = max\{當前node可以跳到的node可以跳到的最大格數\} + 1$

但如果是最單純的想法去dp的話，每一次狀態轉移要check $n+m$ 次，整體複雜度變$O(n*m*(n+m))$。

要解決這題的話，可以參考[這次周賽](https://hackmd.io/ATJaMTDWQuOUoFVB9gzANQ)裡第四題的解法，**使用priority queue降低狀態轉移所需要的時間**。

因此使用priority queue去降低找到最大值的所需的時間，從$O(n+m)降低到O(log(n)+log(m))$。

但由於實務上的一些問題，我以下實作的程式碼遇到極端測資例如 **\[ \[1\]\*100000 \]**，複雜度會退化到$O(n*m*(n+m))$，實在十分抱歉。如果要看時間複雜度正確的解，可以觀看下一個使用不同方法的 Optimized Solution。
#### 時間複雜度: $O(n*m*(n+m))$

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

程式碼:

class Solution {
public:
    int maxIncreasingCells(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        
        vector<pair<int, pair<int, int> > > arr;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                arr.push_back({mat[i][j], {i, j}});
            }
        }
        
        sort(arr.begin(), arr.end(), greater<pair<int, pair<int, int> > >());
        vector<priority_queue<pair<int, int> > > row(n), col(m);
        int ans = 0;
        
        for(auto &[val, pos]: arr){
            int sum = 0, i = pos.first, j = pos.second;
            
            vector<pair<int, int> > temp;
            while(!row[i].empty()&&row[i].top().second == val){
                temp.push_back(row[i].top());
                row[i].pop();
            }
            if(!row[i].empty())
                sum = max(sum, row[i].top().first);

            for(int k=0;k<temp.size();k++)
                row[i].push(temp[k]);
            temp.clear();
            
            while(!col[j].empty()&&col[j].top().second == val){
                temp.push_back(col[j].top());
                col[j].pop();
            }
            if(!col[j].empty())
                sum = max(sum, col[j].top().first);
            
            for(int k=0;k<temp.size();k++)
                col[j].push(temp[k]);
            temp.clear();

            sum++;
            
            ans = max(ans, sum);
            row[i].push({sum, val});
            col[j].push({sum, val});
        }
        
        return ans;
    }
};

### Optimized Solution

參考[這篇](https://leetcode.com/problems/maximum-strictly-increasing-cells-in-a-matrix/solutions/3570296/java-c-python-dp-solution/)的解。

想法其實非常相似，都是從dp出發。

$不過這邊的dp[i][j]的意義與我上個解不太一樣，\\這邊dp[i][j]的意思是從任意點出發到mat[i][j]這點可以跳到的最大格數，\\上一個解的dp[i][j]是從mat[i][j]開始跳，可以跳到的最大格數。$

這個解法對於每個row或column只需要使用一個變數來存取該row或column的最大值，有了最大值後只要使用dp式:

$dp[i][j] = max(row[i], col[j]) + 1$

就可以計算出該點的解答，之後利用這個解答去重新更新row[i]與col[j]的最大值，這樣重複的算，最後只要找出每個row與每個col裡的最大值就是題目所求的答案。

這個解巧妙的地方在於使用了**map來避免mat[i][j]相同值互相干擾的問題**，一次就處理完相同值的所有結果，如果套用到上一個解法的話，就不需要重新將同一個值的結果重新push回去與該元素同row與column的priority queue裡。

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

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

程式碼:

class Solution {
public:
    int maxIncreasingCells(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        
        map<int, vector<pair<int, int> > > mp;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                mp[mat[i][j]].push_back({i, j});
            }
        }
        
        vector<int> row(n), col(m);
        vector<vector<int> > dp(n, vector<int>(m));
        int ans = 0;
        
        for(auto &[val, pos]: mp){
            for(auto &[i, j]: pos)
                dp[i][j] = max(row[i], col[j]) + 1;
            
            for(auto &[i, j]: pos){
                row[i] = max(row[i], dp[i][j]);
                col[j] = max(col[j], dp[i][j]);
            }
        }
        
        for(auto &val: row)
            ans = max(ans, val);
        for(auto &val: col)
            ans = max(ans, val);
        return ans;
    }
};