---
# System prepended metadata

title: Weekly Contest 341
tags: [Weekly Contest]

---

###### 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 &lt;= m, n &lt;= 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 &lt;= nums.length, divisors.length &lt;= 1000</code></li>
<li><code>1 &lt;= nums[i], divisors[i] &lt;= 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 &lt;= word.length &lt;= 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 &lt;= n &lt;= 50</code></li>
<li><code>edges.length == n - 1</code></li>
<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= 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 &lt;= price[i] &lt;= 1000</code></li>
<li><code>1 &lt;= trips.length &lt;= 100</code></li>
<li><code>0 &lt;= start<sub>i</sub>, end<sub>i</sub> &lt;= 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);
    }
};
```
