###### tags: `Weekly Contest`
# Weekly Contest 341
## [2643. Row With Maximum Ones](https://leetcode.com/problems/row-with-maximum-ones/)(<font color=#00B8A3>Easy</font>)
限制 :
<ul>
<li><code>m == mat.length</code> </li>
<li><code>n == mat[i].length</code> </li>
<li><code>1 <= m, n <= 100</code> </li>
<li><code>mat[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>
### Solution
#### 時間複雜度: ***O(m*n)***
#### 空間複雜度: ***O(1)***
順著題意解即可，只須注意當計數相等時取最小的index
程式碼:
```c++=class Solution {
public:
vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
int row=0;
int max=0;
for(int i=0;i<mat.size();i++)
{
int c=0;
for(int j=0;j<mat[i].size();j++)
{
if(mat[i][j]==1)
{
c++;
}
}
if(c>max)
{
max=c;
row=i;
}
}
vector<int>ans;
ans.push_back(row);
ans.push_back(max);
return ans;
}
};
```
## [2644. Find the Maximum Divisibility Score](https://leetcode.com/problems/find-the-maximum-divisibility-score/)(<font color=#00B8A3>Easy</font>)
限制 :
<ul>
<li><code>1 <= nums.length, divisors.length <= 1000</code></li>
<li><code>1 <= nums[i], divisors[i] <= 10<sup>9</sup></code></li>
</ul>
### Solution
#### 時間複雜度: ***O(nums.length * divisors.length)***
#### 空間複雜度: ***O(1)***
雙層迴圈遍歷，求出每一元素的score，檢查是否>當下最大值即可，不用額外空間儲存各score，故空間複雜度=constant。
程式碼:
```c++=class Solution {
public:
int maxDivScore(vector<int>& nums, vector<int>& divisors) {
int ans=-1;
int max=-1;
for(int i=0;i<divisors.size();i++)
{
int c=0;
for(int j=0;j<nums.size();j++)
{
if(nums[j]%divisors[i]==0)
{
c++;
}
}
if(c>max)
{
max=c;
ans=divisors[i];
}
else if(c==max&&ans>divisors[i])
{
ans=divisors[i];
}
}
return ans;
}
};
```
## [2645. Minimum Additions to Make Valid String](https://leetcode.com/problems/minimum-additions-to-make-valid-string/)(<font color=#FFC011>Medium</font>)
限制 :
<ul>
<li><code>1 <= word.length <= 50</code></li>
<li><code>word</code> consists of letters "a", "b" and "c" only. </li>
</ul>
### Solution
#### 時間複雜度: $O(n^2)$
#### 空間複雜度: $O(n)$
這題其實時間複雜度不是很確定，insert好像可能也許大概是複雜度n，上面是假設其複雜度為常數，頭尾塞44只是避免overflow，沒什麼作用，其實就是分case討論而已，然後記得index要跟著動不然會有問題，可以從程式碼中看出，如果insert在前面，i要加，後面則不用。
程式碼:
```c++=class Solution {
public:
int addMinimum(string word) {
int ans=0;
word+="44";
word.insert(0,"44");
for(int i=0;i<word.size();i++)
{
if(word[i]=='a')
{
if(i==word.size()-3)
{
word.insert(i+1,"bc");
ans+=2;
i+=2;
}
if(word[i+1]=='a')
{
word.insert(i+1,"bc");
i+=2;
ans+=2;
}
else if(word[i+1]=='b')
{
if(word[i+2]!='c')
{
ans+=1;
word.insert(i+2,"c");
i+=1;
}
}
else if(word[i+1]=='c')
{
ans+=1;
word.insert(i+1,"b");
i+=1;
}
}
else if(word[i]=='b')
{
if(word[i-1]!='a')
{
word.insert(i,"a");
ans+=1;
i+=1;
}
if(word[i+1]!='c')
{
word.insert(i+1,"c");
ans+=1;
}
}
else if(word[i]=='c')
{
if(i==2)
{
word.insert(i,"ab");
i+=2;
ans+=2;
}
if(word[i-1]=='c')
{
word.insert(i,"ab");
i+=2;
ans+=2;
}
else if(word[i-1]=='b')
{
if(word[i-2]!='a')
{
ans+=1;
word.insert(i-2,"a");
i+=1;
}
}
else if(word[i-1]=='a')
{
word.insert(i,"b");
ans+=1;
i+=1;
}
}
}
for(int i=2;i<word.size()-2;i++)
{
cout<<word[i];
}
cout<<endl;
return ans;
}
};
```
### Optimized Solution 1
做程式可讀性的優化。
#### 時間複雜度: $O(n^2)$
#### 空間複雜度: $O(n)$
程式碼:
```c++=
class Solution {
public:
int addMinimum(string word) {
int ans=0;
if(word[0] !='a')
word.insert(word.begin(), 'a'), ans++;
if(word.back() !='c')
word+='c', ans++;
for(int i=0;i<word.size()-1;i++){
if(word[i]=='a'&&word[i+1] !='b')
word.insert(word.begin()+i+1, 'b'), ans++;
else if(word[i]=='b'&&word[i+1] !='c')
word.insert(word.begin()+i+1, 'c'), ans++;
else if(word[i]=='c'&&word[i+1] !='a')
word.insert(word.begin()+i+1, 'a'), ans++;
}
return ans;
}
};
```
### Optimized Solution 2
參考[這篇](https://leetcode.com/problems/minimum-additions-to-make-valid-string/solutions/3421989/circular-matching/?orderBy=most_votes)和[這篇](https://leetcode.com/problems/minimum-additions-to-make-valid-string/solutions/3421709/c-java-python-o-n-greedy-solution-easy-to-understand/?orderBy=most_votes)，對每一個字母去match 'abc' 這個pattern，答案就等於沒有match到的次數。
#### 時間複雜度: $O(n)$
#### 空間複雜度: $O(1)$
程式碼:
```c++=
class Solution {
public:
int addMinimum(string word) {
int ans=0;
if(word.back() !='c')
word+='c', ans++;
char cur='a';
for(int i=0;i<word.size();){
if(cur==word[i])
i++;
else ans++;
cur='a'+(cur-'a'+1)%3;
}
return ans;
}
};
```
```c++=
class Solution {
public:
int addMinimum(string word) {
int n = word.size(), i = 0, res = 0;
while(i < n) {
int count = 0;
if(word[i] == 'a') {
count++;i++;
}
if(i < n and word[i] == 'b') {
count++;i++;
}
if(i < n and word[i] == 'c') {
count++;i++;
}
res += 3 - count;
}
return res;
}
};
```
## [2646. Minimize the Total Price of the Trips](https://leetcode.com/problems/minimize-the-total-price-of-the-trips/)(<font color=#FF375F>Hard</font>)
限制 :
<ul>
<li><code>1 <= n <= 50</code></li>
<li><code>edges.length == n - 1</code></li>
<li><code>0 <= a<sub>i</sub>, b<sub>i</sub> <= n - 1</code></li>
<li><code>edges</code> represents a valid tree.</li>
<li><code>price.length == n</code></li>
<li><code>price[i]</code> is an even integer.</li>
<li><code>1 <= price[i] <= 1000</code></li>
<li><code>1 <= trips.length <= 100</code></li>
<li><code>0 <= start<sub>i</sub>, end<sub>i</sub> <= n - 1</code></li>
</ul>
### Solution
計算出所有trip的路徑各走過每個點幾次，將每個點對應的price乘走過該點幾次。之後問題就被簡化為[這題](https://leetcode.com/problems/house-robber-iii/)。直接套用這題的解題演算法就能做了。
#### 時間複雜度: $O(t*logt)$ t = trips.length ?
#### 空間複雜度: $O(t)$ ?
程式碼:
```c++=
class Solution {
public:
map<pair<int, int>, int> mp;
vector<int> path;
vector<bool> isvisited;
vector<int> cnt;
void dfs(int now, vector<vector<int> > &graph){
if(path[0]<=path.back()){
int val=mp[{path[0], path.back()}];
for(auto &node: path)
cnt[node]+=val;
}
for(int i=0;i<graph[now].size();i++){
int next=graph[now][i];
if(!isvisited[next]){
isvisited[next]=true;
path.push_back(next);
dfs(next, graph);
path.pop_back();
}
}
}
unordered_map<int, int> dp;
int dfs2(int now, int parent, vector<vector<int> > &graph, vector<int> &price){
if(dp.count(now))
return dp[now];
int include=price[now], exclude=0;
bool flag=false;
for(int i=0;i<graph[now].size();i++){
int next=graph[now][i];
if(next !=parent){
exclude+=dfs2(next, now, graph, price);
for(int j=0;j<graph[next].size();j++){
int next2=graph[next][j];
if(now !=next2)
include+=dfs2(next2, next, graph, price);
}
flag=true;
}
}
if(flag==false)
return dp[now]=include;
return dp[now]=max(include, exclude);
}
int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
vector<vector<int> > graph(n);
for(auto &edge: edges){
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
for(auto &trip: trips){
if(trip[0]>trip[1])
swap(trip[0], trip[1]);
mp[{trip[0], trip[1]}]++;
}
cnt.resize(n);
isvisited.resize(n);
for(int i=0;i<n;i++){
fill(isvisited.begin(), isvisited.end(), 0);
isvisited[i]=true;
path.push_back(i);
dfs(i, graph);
path.pop_back();
}
int sum=0;
for(int i=0;i<n;i++){
price[i]*=cnt[i];
sum+=price[i];
}
int val=dfs2(0, -1, graph, price);
return sum-val+val/2;
}
};
```
## [337. House Robber III](https://leetcode.com/problems/house-robber-iii/)(<font color=#FFC011>Medium</font>)
限制 :
* The number of nodes in the tree is in the range $[1, 10^4]$.
* $0 <= Node.val <= 10^4$
### Solution
對於每一間的house，可以選擇搶或不搶。由此可以導出dp式。
$dp[i] = max(dp[i-1], val[i] + dp[i-2])$
根據此dp式更改成tree的版本即可。
#### 時間複雜度: $O(n)$
#### 空間複雜度: $O(n)$
程式碼:
```c++=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<TreeNode*,int> dp;
int dfs(TreeNode* now){
if(now==NULL)
return 0;
if(dp.count(now))
return dp[now];
int include=now->val,exclude=0;
if(now->left !=NULL)
include+=dfs(now->left->left)+dfs(now->left->right);
if(now->right !=NULL)
include+=dfs(now->right->left)+dfs(now->right->right);
exclude+=dfs(now->left)+dfs(now->right);
dp[now]=max(include,exclude);
return dp[now];
}
int rob(TreeNode* root) {
return dfs(root);
}
};
```
Sign in with Wallet
Connect another wallet