###### tags: `Weekly Contest`
# Weekly Contest 344

## [2670. Find the Distinct Difference Array](https://leetcode.com/problems/find-the-distinct-difference-array/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 &lt;= n == nums.length &lt;= 50</code></li>
<li><code>1 &lt;= nums[i] &lt;= 50</code></li>
</ul>

### Solution
照題意做，用map去統計集合裡總共有多少不同的數字，兩個集合的大小相減就是答案了。
#### 時間複雜度: $O(nlogn)$

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

程式碼:

class Solution {
public:
    vector<int> distinctDifferenceArray(vector<int>& nums) {
        map<int, int> si,sj;
        vector<int> ans;
        for(auto &num: nums)
            sj[num]++;
        for(auto &num: nums){
            si[num]++;
            if(--sj[num]==0)
                sj.erase(num);
            ans.push_back(int(si.size())-sj.size());
        }
        return ans;
    }
};

## [2671. Frequency Tracker](https://leetcode.com/problems/frequency-tracker/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= number &lt;= 10⁵</code></li>
<li><code>1 &lt;= frequency &lt;= 10⁵</code></li>
<li>At most, <code>2 * 10⁵</code> calls will be made to <code>add</code>, <code>deleteOne</code>, and <code>hasFrequency</code> in <strong>total</strong>.</li>
</ul>

### Solution
設定一個array紀錄每個數字出現幾次，再設定一個map紀錄每個頻率有多少數字，去維護這兩個物件，就可以在達到題目所需的時間複雜度。

$n = number.length$
#### 時間複雜度:
add: $O(log(sqrt(n)))$
deleteOne: $O(log(sqrt(n)))$
hasFrequency: $O(log(sqrt(n)))$
#### 空間複雜度: $O(n)$

程式碼:

class FrequencyTracker {
public:
    map<int, int> mp;
    vector<int> ivec;
    FrequencyTracker() {
        ivec.resize(100005);
    }
    
    void add(int number) {
        int val=ivec[number]++;
        mp[val+1]++;
        if(val)
            mp[val]--;
    }
    
    void deleteOne(int number) {
        if(ivec[number]>0){
            int val=ivec[number]--;
            mp[val]--;
            if(val-1 !=0)
                mp[val-1]++;
        }
    }
    
    bool hasFrequency(int frequency) {
        return mp[frequency]>0;
    }
};

/**
 * Your FrequencyTracker object will be instantiated and called as such:
 * FrequencyTracker* obj = new FrequencyTracker();
 * obj->add(number);
 * obj->deleteOne(number);
 * bool param_3 = obj->hasFrequency(frequency);
 */

## [2672. Number of Adjacent Elements With the Same Color](https://leetcode.com/problems/number-of-adjacent-elements-with-the-same-color/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= n &lt;= 10⁵</code></li>
<li><code>1 &lt;= queries.length &lt;= 10⁵</code></li>
<li><code>queries[i].length == 2</code></li>
<li><code>0 &lt;= index_i &lt;= n - 1</code></li>
<li><code>1 &lt;=  color_i &lt;= 10⁵</code></li>
</ul>

### Solution
**題目記得要看清楚**，是要求pair的數量，而不是求整個array裡最大連續的顏色有幾個。

**對於一個$queries[i]$，會影響到的pair數量只有 $i-1$, $i+1$ 這兩個地方而已。**
假設 $color[i]$ 是目前那格的顏色，如果 $color[i]$ 更改前與 $color[i-1]$ 同色，那pair的數量會減一，如果 $color[i]$ 更改後與 $color[i-1]$ 同色，那pair的數量會加一，同理 $color[i]$ 與 $color[i+1]$ 也會有一樣的性質。

考慮以上後就可以算出答案。

$q = queries.length$
#### 時間複雜度: $O(q)$

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

程式碼:

class Solution {
public:
    vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
        vector<int> ans, ivec(n);
        int cnt=0;
        for(auto &q: queries){
            int idx=q[0], val=q[1];
            if(ivec[idx]){
                if(idx !=0&&ivec[idx-1]==ivec[idx])
                    cnt--;
                if(idx !=n-1&&ivec[idx+1]==ivec[idx])
                    cnt--;
            }
            ivec[idx]=val;
            if(idx !=0&&ivec[idx-1]==ivec[idx])
                cnt++;
            if(idx !=n-1&&ivec[idx+1]==ivec[idx])
                cnt++;
            ans.push_back(cnt);
        }
        return ans;
    }
};

## [2673. Make Costs of Paths Equal in a Binary Tree](https://leetcode.com/problems/make-costs-of-paths-equal-in-a-binary-tree/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>3 &lt;= n &lt;= 10⁵</code></li>
<li><code>n + 1</code> is a power of <code>2</code></li>
<li><code>cost.length == n</code></li>
<li><code>1 &lt;= cost[i] &lt;= 10⁴</code></li>
</ul>

### Solution
**因為我們只能增加某一個node的值，所以最終每一條路徑長一定會等於原本的樹最長的那條路徑長，以下將原本的樹最長的那條路徑長稱為目標路徑長**。

因為增加越靠近root的node一定會增加到越多條路徑的值，所以我們會傾向由上開始增加node的值。但要如何找出這個node應該要增加多少值呢?只要去找出當前node所對應到的所有路徑長其中的最大值，拿目標路徑長減去該值，就是當前node應該要增加的數量。

將所有node增加的數量加總，就是答案。
#### 時間複雜度: $O(nlogn)$

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

程式碼:

class Solution {
public:
    int path_sum, ans;
    int sz;
    vector<int> node_sum;
    void dfs1(int now, int sum, vector<int> &cost){
        if(now>sz){
            path_sum=max(path_sum, sum);
            node_sum[now/2]=sum;
            return ;
        }
        sum+=cost[now-1];
        dfs1(now*2, sum, cost);
        dfs1(now*2+1, sum, cost);
        sum-=cost[now-1];
    }
    void dfs2(int now, int sum, vector<int> &cost){
        if(now>sz)
            return ;

        int left=now, right=now;
        while(left<=sz) // 找到目前node對應的leaf左界
            left*=2;
        while(right<=sz) // 找到目前node對應的leaf右界
            right=right*2+1; 
        
        left/=2, right/=2;
        int n_sum=0;
        for(int i=left;i<=right;i++) // 找到目前node對應的leaf最大值
            n_sum=max(n_sum, node_sum[i]);

        if(n_sum<path_sum){ // 如果目前node對應的最大值小於最大的路徑長，代表可以增加該node的值，應該要增加的值是兩個值之間的差值。
            int val=path_sum-n_sum;
            for(int i=left;i<=right;i++)
                node_sum[i]+=val;
            ans+=val;
        }

        sum+=cost[now-1];
        dfs2(now*2, sum, cost);
        dfs2(now*2+1, sum, cost);
    }
    int minIncrements(int n, vector<int>& cost) {
        sz=n;
        path_sum=0;
        node_sum.clear();
        node_sum.resize(sz+5);
        dfs1(1, 0, cost);
        ans=0;
        dfs2(1, 0, cost);
        return ans;
    }
};

### Optimized Solution
參考[這篇](https://leetcode.com/problems/make-costs-of-paths-equal-in-a-binary-tree/solutions/3494915/java-c-python-bottom-up-and-follow-up/?orderBy=most_votes)，從非leaf node由下往上做，對每個node的兩個child，使比較少的那個child的值等於較大的那個child的值，如此便是答案。

原文還有講解題目如果變成可以對node的值加一或減一的話，該如何處理。
#### 時間複雜度: $O(n)$

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

程式碼:

int minIncrements(int n, vector<int>& A) {
        int res = 0;
        for (int i = n / 2 - 1; i >= 0; --i) {
            int l = i * 2 + 1, r = i * 2 + 2;
            res += abs(A[l] - A[r]);
            A[i] += max(A[l], A[r]);
        }
        return res;
}