###### tags: `BiWeekly Contest`
# BiWeekly Contest 102

## [2639. Find the Width of Columns of a Grid](https://leetcode.com/problems/find-the-width-of-columns-of-a-grid/)(<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 &lt;= 100 </code></li>
<li><code>-10⁹ &lt;= grid[r][c] &lt;= 10⁹</code></li>
</ul>

### Solution
找出每一個colume中長度最長的是多少
負號長度算1

就是每個colume都掃一遍
然後找最大值
如果跟我一樣用 **/=10** 來判斷
要注意 **數字0** 長度是1
如果轉成字串好像就不會有這個問題了

#### 時間複雜度: ***O(n^2)***

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

程式碼:

class Solution {
public:
    vector<int> findColumnWidth(vector<vector<int>>& grid) {
        int temp = 0;
        vector<int> ans(grid[0].size());
        for(int i = 0; i < grid[0].size(); ++i){
            for(int j = 0; j < grid.size(); ++j){
                if(grid[j][i] == 0) ++temp;
                if(grid[j][i] < 0)  ++temp;
                while(grid[j][i]){
                    grid[j][i] /= 10;
                    ++temp;
                }
                ans[i] = max(ans[i], temp);
                temp = 0;
            }
        }
        return ans;
    }
};

## [2640. Find the Score of All Prefixes of an Array](https://leetcode.com/problems/find-the-score-of-all-prefixes-of-an-array/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= nums.length &lt;= 10⁵</code></li>
<li><code>1 &lt;= nums[i] &lt;= 10⁹</code></li>
</ul>

### Solution
陣列中的每個數字都有自己的分數
分數的算法是**從陣列開始的位置到自己的位置之中的最大值**加上**自己的值**

題目要求的是**從陣列開始的位置到自己的位置**的**分數總合**
用prefix sum的算法就可以算出來了

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

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

程式碼:

class Solution {
public:
    vector<long long> findPrefixScore(vector<int>& nums) {
        long long max_num = 0;
        vector<long long> ans(nums.size());
        for(int i = 0; i < nums.size(); ++i){
            if(nums[i] > max_num)   max_num = nums[i];
            ans[i] = nums[i] + max_num;
        }
        for(int i = 1; i < ans.size(); ++i){
            ans[i] += ans[i - 1];
        }
        return ans;
    }
};

## [2641. Cousins in Binary Tree II](https://leetcode.com/problems/cousins-in-binary-tree-ii/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li>The number of nodes in the tree is in the range <code>[1, 10⁵]</code>.</li>
<li><code>1 &lt;= Node.val &lt;= 10⁴</code></li>
</ul>

### Solution
先記錄每層的總和
再減去位在同一個父節點的點的值
最後把值寫入節點

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

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

程式碼:

/**
 * 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:
    vector<int> level_sum;
    int temp;
    void get_sum(TreeNode* n, int depth){
        if(!n)  return;
        level_sum[depth] += n->val;
        ++depth;
        get_sum(n->left, depth);
        get_sum(n->right, depth);
        --depth;
    }
    void set_sum(TreeNode* n, int depth){
        if(!n || (!n->left && !n->right))   return;
        else if(n->left && !n->right)    n->left->val = level_sum[depth + 1] - n->left->val;
        else if(n->right && !n->left)   n->right->val = level_sum[depth + 1] - n->right->val;
        else{
            temp = level_sum[depth + 1] - n->left->val - n->right->val;
            n->left->val = temp;
            n->right->val = temp;
        }
        
        ++depth;
        set_sum(n->left, depth);
        set_sum(n->right, depth);
        --depth;
        
    }
    TreeNode* replaceValueInTree(TreeNode* root) {
        level_sum = vector<int>(1e5);
        get_sum(root, 0);
        set_sum(root, 0);
        root->val = 0;
        // for(int i : level_sum){
        //     cout << i << " " ;
        // }
        // cout << endl;
        return root;
    }
};

### Optimized Solution
對程式碼可讀性進行優化。

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

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

程式碼:

/**
 * 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:
    vector<int> level_sum;
    void get_sum(TreeNode* n, int depth){
        if(!n)  return;

        if(depth >= level_sum.size()) level_sum.push_back(0);
        level_sum[depth] += n->val;

        get_sum(n->left, depth + 1);
        get_sum(n->right, depth + 1);
    }
    void set_sum(TreeNode* n, int depth){
        if(!n || (!n->left && !n->right))   return;

        int sum = level_sum[depth + 1];
        if(n->left)    sum -= n->left->val;
        if(n->right)   sum -= n->right->val;
        
        if(n->left)    n->left->val = sum;
        if(n->right)   n->right->val = sum;
        
        set_sum(n->left, depth + 1);
        set_sum(n->right, depth + 1);
    }
    TreeNode* replaceValueInTree(TreeNode* root) {
        level_sum.reserve(1e5);

        get_sum(root, 0);
        set_sum(root, 0);
        root->val = 0;
        return root;
    }
};

## [2642. Design Graph With Shortest Path Calculator](https://leetcode.com/problems/design-graph-with-shortest-path-calculator/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>1 &lt;= n &lt;= 100</code></li>
<li><code>0 &lt;= edges.length &lt;= n * (n - 1)</code></li>
<li><code>edges[i].length == edge.length == 3</code></li>
<li><code>0 &lt;= from_i, to_i, from, to, node1, node2 &lt;= n - 1</code></li>
<li><code>1 &lt;= edgeCost_i, edgeCost &lt;= 10⁶</code></li>
<li>There are no repeated edges and no self-loops in the graph at any point.</li>
<li>At most <code>100</code> calls will be made for <code>addEdge</code>.</li>
<li>At most <code>100</code> calls will be made for <code>shortestPath</code>.</li>
</ul>

### Solution
參考[這篇](https://leetcode.com/problems/design-graph-with-shortest-path-calculator/solutions/3421164/c-graph-dijkstra-algo/)
前兩個function是建立和新增
應該不會太難

找最短成本路徑概念是dijkstra
用BFS來找到開始節點到當前節點的成本
並**記錄下來取最小值**
等到能跑到的節點都跑完之後就可以得到開始節點到所有點的最小成本

#### 時間複雜度: ***O()***

#### 空間複雜度: ***O()***

程式碼:

class Graph {
public:
    unordered_map<int, vector<pair<int, int>>> graph; // from -> <to, cost>
    int k;
    Graph(int n, vector<vector<int>>& edges) {
        for(auto& e : edges){
            graph[e[0]].push_back({e[1], e[2]});
        }
        k = n;
    }
    
    void addEdge(vector<int> e) {
        graph[e[0]].push_back({e[1], e[2]});
    }
    
    int shortestPath(int n1, int n2) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, n1});
        vector<int> dist(k + 1, INT_MAX);
        dist[n1] = 0;
        while(pq.size()){
            int node = pq.top().second;
            int dis = pq.top().first;
            pq.pop();
            for(auto& i : graph[node]){
                if(dist[i.first] > i.second + dis){
                    dist[i.first] = i.second + dis;
                    pq.push({dist[i.first], i.first});
                }
            }
            // cout << node << " : " << endl;
            // for(auto& i : dist){
            //     cout << i << " ";
            // }
            // cout << endl;
        }
        if(dist[n2] == INT_MAX) return -1;
        return dist[n2];
    }
};

/**
 * Your Graph object will be instantiated and called as such:
 * Graph* obj = new Graph(n, edges);
 * obj->addEdge(edge);
 * int param_2 = obj->shortestPath(node1,node2);
 */