###### tags: `Weekly Contest`
# Weekly Contest 338

## [2600. K Items With the Maximum Sum](https://leetcode.com/problems/k-items-with-the-maximum-sum/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>0 &lt;= numOnes, numZeros, numNegOnes &lt;= 50</code></li>
<li><code>0 &lt;= k &lt;= numOnes + numZeros + numNegOnes</code></li>
</ul>

### Solution
簡單的數學運算，知道在幹嘛就會了~
#### 時間複雜度: ***O(1)***

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

程式碼:

class Solution {
public:
    int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        int ans = 0;
        if(numOnes < k)
        {
            ans+=numOnes;
            if(numOnes+numZeros < k)
            {
                if(numOnes+numZeros +numNegOnes > k)
                    ans -= k-(numOnes+numZeros);
                else
                    ans-= numNegOnes;
            }
        }
        else
        {
            ans = k;
        }
        return ans;
    }
};

## [2601. Prime Subtraction Operation](https://leetcode.com/problems/prime-subtraction-operation/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>
<li><code><font face="monospace">nums.length == n</font></code></li>
</ul>

### Solution
先建質數表，因為題目條件要減掉某質數；但因為題目最大值是1000，所以做到1000就好。
接下來順著題目所提供的數列往下走，算出大於前項的最小值，一路走到底就計算完成。
最後再檢查數列一次，如果找到後項比前項小的就return false，反之 return true。
#### 時間複雜度: ***O(n^2)***

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

程式碼:

class Solution {
public:
    vector<int>prime_record;

    void set_prime_record()
    {
        int now_number = 1;
        prime_record.push_back(now_number);
        now_number = 2;
        prime_record.push_back(now_number);
        while (now_number < 1000)
        {
            now_number++;
            bool isInsert = true;
            for (int i = 1; i < prime_record.size() && prime_record[i] < (pow(now_number, 0.5) + 1); i++)
            {
                if (now_number % prime_record[i] == 0)
                {
                    isInsert = false;
                    break;
                }
            }
            if (isInsert)
                prime_record.push_back(now_number);
        }
    }

    bool primeSubOperation(vector<int>& nums) {
        set_prime_record();

        int size = nums.size();
        for (int i = 0; i < size; i++)
        {
            int size = prime_record.size();
            int min_num = nums[i];
            // binary search, C++ STL:lower_bound()
            for (int j = 1; j < prime_record.size(); j++)
            {
                int temp_num = nums[i] - prime_record[j];
                if (temp_num <= 0)
                    break;
                else
                {
                    if (i == 0 || (nums[i - 1] < temp_num))
                    {
                        min_num = temp_num;
                    }
                }
            }

            nums[i] = min_num;
            if (i > 0 && nums[i] < nums[i - 1])
                return false;
        }

        for (int i = 1; i < nums.size(); i++)
        {
            cout << nums[i] << ' ';
            if (nums[i] <= nums[i - 1])
            {
                cout << "false" << endl;
                return false;
            }
        }

        cout << "true" << endl;
        return true;
    }
};

## [2602. Minimum Operations to Make All Array Elements Equal](https://leetcode.com/problems/minimum-operations-to-make-all-array-elements-equal/)(<font color=#FFC011>Medium</font>)

限制 :

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

### Solution
先計算出 prefix sum ，再利用 prefix sum 讓每個測資在計算時可以更方便。
接下來 去看每個 query ，去相加左子數列與 query 的差和右子數列與 query 的差。
#### 時間複雜度: ***O(nlog(n))***

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

程式碼:

class Solution {
public:
    int binary_search(vector<int>& nums, int key) {
        int front = 0, back = nums.size() - 1;
        while (front <= back)
        {
            int mid = int((front + back) / 2);
            if (key == nums[mid])
                return mid;
            else if (key > nums[mid])
                front = mid + 1;
            else
                back = mid - 1;
        }
        return back;
    }

    vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
        sort(nums.begin(), nums.end());
        vector<long long> ans_list(queries.size());

        vector<long long> record(nums.size());
        record[0] = (nums[0]);
        // prefix sum 的第一個職建議使用 0 
        for (int i = 1; i < nums.size(); i++)
        {
            record[i] = record[i - 1] + (nums[i]);
        }
        long long split_index = 0;
        for (int i = 0; i < queries.size(); i++)
        {
            split_index = binary_search(nums, queries[i]);
            long long left_result = 0, right_result = 0;
            // cout <<split_index<<endl;
            if (split_index >= 0 && split_index < record.size())
            {
                left_result = (split_index+1) * queries[i] - record[split_index];
                // cout << "left " << left_result<<endl;
                long long right_presum = record[record.size()-1] -  record[split_index];
                right_result = right_presum - (nums.size() - split_index - 1)*queries[i];
                // cout <<"right_result " << right_result<<endl;
            }
            else{
                right_result = record[record.size()-1] - nums.size() *queries[i];
            }
            

            ans_list[i] = left_result + right_result;
            // cout << ans_list[i] << ' ';
        }
        return ans_list;

    }
};

## [2603. Collect Coins in a Tree](https://leetcode.com/problems/collect-coins-in-a-tree/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>n == coins.length</code></li>
<li><code>1 &lt;= n &lt;= 3 * 10⁴</code></li>
<li><code>0 &lt;= coins[i] &lt;= 1</code></li>
<li><code>edges.length == n - 1</code></li>
<li><code>edges[i].length == 2</code></li>
<li><code>0 &lt;= a_i, b_i &lt; n</code></li>
<li><code>a_i != b_i</code></li>
<li><code>edges</code> represents a valid tree.</li>
</ul>

### Solution
參考[這篇](https://leetcode.com/problems/collect-coins-in-a-tree/solutions/3342036/c-java-python3-trim-the-tree/?orderBy=most_votes)，因為有coin的節點才是必須走訪到的節點，所以先把無關的節點砍掉，也就是先砍掉沒有coin的葉節點。接下來因為可以拿到距離2以內的節點的coin，所以只要再砍掉所有葉節點兩次即可，剩下的edge就都是必要的edge。最後再根據剩下的edge數量計算出答案。

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

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

程式碼:

bool DEBUG = true;
class Solution {
public:
    void trimLeaf(vector<set<int> > &graph, vector<int> &coins){ // 砍掉沒有coin的葉節點
        int n=graph.size();
        queue<int> qi;
        for(int i=0;i<n;i++){
            if(graph[i].size()==1&&!coins[i])
                qi.push(i);
        }

        while(!qi.empty()){
            int now=qi.front(), parent=*graph[now].begin();
            graph[parent].erase(now);
            graph[now].erase(parent);

            if(graph[parent].size()==1&&!coins[parent])
                qi.push(parent);

            qi.pop();
        }
    }
    void trimLeaf(vector<set<int> > &graph){ // 砍掉所有葉節點
        int n=graph.size();
        queue<int> qi;
        for(int i=0;i<n;i++){
            if(graph[i].size()==1)
                qi.push(i);
        }

        while(!qi.empty()){
            int now=qi.front(), parent=*graph[now].begin();
            graph[parent].erase(now);
            graph[now].erase(parent);
            qi.pop();
        }
    }
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n=coins.size();
        vector<set<int> > graph(n);

        for(auto &edge: edges){
            graph[edge[0]].insert(edge[1]);
            graph[edge[1]].insert(edge[0]);
        }

        trimLeaf(graph, coins);
        trimLeaf(graph);
        trimLeaf(graph);
        
        int ans=0;
        for(int i=0;i<n;i++)
            ans+=graph[i].size();

        return ans;
    }
};

reference :
- [What is the difference between vector.back() and vector.end()](https://stackoverflow.com/questions/44831793/what-is-the-difference-between-vector-back-and-vector-end)
- [lower_bound](https://cplusplus.com/reference/algorithm/lower_bound/)
- [C++中for auto的用法](https://blog.csdn.net/gulosityer/article/details/112554056)