---
# System prepended metadata

title: Weekly Contest 343
tags: [Weekly Contest]

---

###### tags: `Weekly Contest`
# Weekly Contest 343

## [2660. Determine the Winner of a Bowling Game](https://leetcode.com/problems/determine-the-winner-of-a-bowling-game/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>n == player1.length == player2.length</code></li>
<li><code>1 &lt;= n &lt;= 1000</code></li>
<li><code>0 &lt;= player1[i], player2[i] &lt;= 10</code></li>
</ul>

### Solution
模擬題，照題意做就好。
#### 時間複雜度: $O(n)$

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

程式碼:

```c++=
class Solution {
public:
    int calculateSum(vector<int> &player){
        int sum=player[0];
        for(int i=1;i<player.size();i++){
            sum+=player[i];
            if(player[max(i-1, 0)] == 10 || player[max(i-2, 0)] == 10)
                sum+=player[i];
        }

        return sum;
    }
    int isWinner(vector<int>& player1, vector<int>& player2) {
        int sum1=calculateSum(player1), sum2=calculateSum(player2);

        if(sum1<sum2)
            return 2;
        else if(sum1>sum2)
            return 1;
        else return 0;
    }
};
```


## [2661. First Completely Painted Row or Column](https://leetcode.com/problems/first-completely-painted-row-or-column/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>m == mat.length</code></li>
<li><code>n = mat[i].length</code></li>
<li><code>arr.length == m * n</code></li>
<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
<li><code>1 &lt;= arr[i], mat[r][c] &lt;= m * n</code></li>
<li>All the integers of <code>arr</code> are <strong>unique</strong>.</li>
<li>All the integers of <code>mat</code> are <strong>unique</strong>.</li>
</ul>

### Solution
**每個row被完整塗滿的時間是這個row的元素在arr裡index最大的那一個元素的index**，column也是同理。使用這個性質去check所有row與column被塗滿的時間，從中取最小的即可。
#### 時間複雜度: $O(m*n*log(m*n))$

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

程式碼:

```c++=
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        map<int, int> mp;
        int n=mat.size(), m=mat[0].size();
        for(int i=0;i<arr.size();i++)
            mp[arr[i]]=i;
        
        int ans=INT_MAX;
        for(int i=0;i<n;i++){
            int row=-1;
            for(int j=0;j<m;j++)
                row=max(row, mp[mat[i][j]]);
            
            ans=min(ans, row);
        }
        for(int j=0;j<m;j++){
            int col=-1;
            for(int i=0;i<n;i++)
                col=max(col, mp[mat[i][j]]);
            
            ans=min(ans, col);
        }
        
        return ans;
    }
};
```

### Optimized Solution
基本上是同樣的想法，但直接使用index將建表時間壓到$O(m*n)$。
#### 時間複雜度: $O(m*n)$

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

程式碼:

```c++=
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int n=mat.size(), m=mat[0].size();
        vector<pair<int, int> > pos(n*m+1);
        
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                pos[mat[i][j]]={i, j};

        vector<int> col(m), row(n);
        for(int i=0;i<arr.size();i++){
            pair<int, int> &now=pos[arr[i]];
            if(++col[now.second] == n||++row[now.first] == m)
                return i;
        }
        
        return -1;
    }
};
```

## [2662. Minimum Cost of a Path With Special Roads](https://leetcode.com/problems/minimum-cost-of-a-path-with-special-roads/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>start.length == target.length == 2</code></li>
<li><code>1 &lt;= startX &lt;= targetX &lt;= 10<sup>5</sup></code></li>
<li><code>1 &lt;= startY &lt;= targetY &lt;= 10<sup>5</sup></code></li>
<li><code>1 &lt;= specialRoads.length &lt;= 200</code></li>
<li><code>specialRoads[i].length == 5</code></li>
<li><code>startX &lt;= x1<sub>i</sub>, x2<sub>i</sub> &lt;= targetX</code></li>
<li><code>startY &lt;= y1<sub>i</sub>, y2<sub>i</sub> &lt;= targetY</code></li>
<li><code>1 &lt;= cost<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

### Solution
**將起點與終點及捷徑的兩端點看成node，捷徑與直接走就是edge**，利用Dijkstra最短路徑演算法即可計算出從起點到每個node的最短路徑。

$n=specialRoads.length$
#### 時間複雜度: $O(n^2*log(n))$

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

程式碼:

```c++=
typedef pair<int, pair<int, int> > Node;
class cmp{
public: 
    bool operator()(Node &a, Node &b){
        return a.first>b.first;
    }
};
class Solution {
public:
    int dis(pair<int, int> &a, pair<int, int> &b){
        return abs(a.first-b.first)+abs(a.second-b.second);
    }
    int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
        map<pair<int, int>, int> mp; // 從起點走到某一點的最短路徑長
        priority_queue<Node, vector<Node>, cmp> pq;
        pair<int, int> s = {start[0], start[1]};
        pair<int, int> e = {target[0], target[1]};

        pq.push({0, s});
        mp[s] = 0;
        int ans = dis(s, e);
        
        while(!pq.empty()){
            Node now=pq.top();
            pq.pop();
            mp[now.second] = min(mp[now.second], dis(now.second, s)); // 從起點直接走去now的時間

            for(auto &road: specialRoads){
                pair<int, int> cur = {road[0], road[1]};
                pair<int, int> next = {road[2], road[3]};
                int cost = road[4];
                int val = mp[now.second] + min(dis(now.second, next), dis(now.second, cur)+cost);
                // 從起點走到next的時間 = 起點走到now的時間 + min(now直接走到next的時間, 從now走到cur的時間加走捷徑的時間)
                if(!mp.count(next) || (mp.count(next) && mp[next] > val)){
                    mp[next] = val;
                    ans = min(ans, val+dis(next, e)); // 從next走到終點的時間
                    pq.push({mp[next], next});
                }
            }
        }
        
        return ans;
    }
};
```


## [2663. Lexicographically Smallest Beautiful String](https://leetcode.com/problems/lexicographically-smallest-beautiful-string/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>1 &lt;= n == s.length &lt;= 10<sup>5</sup></code></li>
<li><code>4 &lt;= k &lt;= 26</code></li>
<li><code>s</code> is a beautiful string.</li>
</ul>

### Solution
參考[這篇](https://leetcode.com/problems/lexicographically-smallest-beautiful-string/solutions/3468265/weird-problem/?orderBy=most_votes)。
 
>引理:
如果一個字串裡不包含迴文的話 $\Leftrightarrow s[i] \neq s[i-1] \quad and \quad s[i] \neq s[i-2] \quad \forall i \in [0, s.length-1]$

根據這個引理，我們只需要由字串的右邊往左遞增字符，找到第一個符合該引理的字符且該字符是英文字母順序的第k個以前的字符，再確保該字符之後的字串是符合引理且 **Lexicographically** 的，那最後出來的字串就會是一個 **Lexicographically beautiful string**。


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

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

程式碼:

```c++=
class Solution {
public:
    bool valid(int i, string &s){
        return i==0 || (i==1 && s[i] !=s[i-1]) || (s[i] !=s[i-1] && s[i] !=s[i-2]);
    }
    string smallestBeautifulString(string s, int k) {
        for(int i=s.size()-1;i>=0;i--){
            ++s[i];
            while(!valid(i, s))
                ++s[i];
            if(s[i]-'a'<k){
                for(i=i+1;i<s.size();i++){
                    s[i]='a';
                    while(!valid(i, s))
                        ++s[i];
                }
                return s;
            }
        }
        return "";
    }
};
```

