###### 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 <= n <= 1000</code></li>
<li><code>0 <= player1[i], player2[i] <= 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 <= m, n <= 10<sup>5</sup></code></li>
<li><code>1 <= m * n <= 10<sup>5</sup></code></li>
<li><code>1 <= arr[i], mat[r][c] <= 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 <= startX <= targetX <= 10<sup>5</sup></code></li>
<li><code>1 <= startY <= targetY <= 10<sup>5</sup></code></li>
<li><code>1 <= specialRoads.length <= 200</code></li>
<li><code>specialRoads[i].length == 5</code></li>
<li><code>startX <= x1<sub>i</sub>, x2<sub>i</sub> <= targetX</code></li>
<li><code>startY <= y1<sub>i</sub>, y2<sub>i</sub> <= targetY</code></li>
<li><code>1 <= cost<sub>i</sub> <= 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 <= n == s.length <= 10<sup>5</sup></code></li>
<li><code>4 <= k <= 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 "";
}
};
```
Sign in with Wallet
Connect another wallet