###### tags: `Weekly Contest`
# Weekly Contest 336

## [2586. Count the Number of Vowel Strings in Range](https://leetcode.com/problems/count-the-number-of-vowel-strings-in-range/) (<font color=#00B8A3>Easy</font>)

### Solution

直接遍歷從 left 到 right 的所有字串，並檢查所有字串是否符合 vowel string 的特徵。

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

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

程式碼:

class Solution {
public:
    int vowelStrings(vector<string>& words, int left, int right) {
        set<char> vowel = {'a', 'e', 'i', 'o', 'u'};
        int ans = 0;
        for(int i=left;i<=right;i++){
            if(vowel.count(words[i][0]) && vowel.count(words[i].back()))
                ans++;
        }
        return ans;
    }
};

## [2587. Rearrange Array to Maximize Prefix Score](https://leetcode.com/problems/rearrange-array-to-maximize-prefix-score/) (<font color=#FFC011>Medium</font>)

### Solution

比較正負數的順序，發現**要使 prefix array 正數最多的話，在 nums 裡的非負數就必須放在負數的前面**。再來是**負數之間的排序，會希望負數越小的排在越前面**，這樣 prefix sum 的 decresing 會越慢。
綜合以上條件，只要將整個 nums 陣列由大排到小之後，計算 prefix sum 有幾個大於 0 即是答案。

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

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

程式碼:

class Solution {
public:
    int maxScore(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>()); // 將nums陣列從大排到小
        
        vector<long long> prefix={0};
        for(int i=0;i<nums.size();i++) // 產生 prefix array
            prefix.push_back(prefix.back()+nums[i]);
        
        int ans = 0;
        for(int i=1;i<prefix.size();i++){
            if(prefix[i]>0)
                ans++;
            else break;
        }
        
        return ans;
    }
};

### Optimized solution

同樣的想法，但在空間上可以只用一個 prefix 變數，而不需要建構整個 prefix array。

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

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

程式碼:

class Solution {
public:
    int maxScore(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        
        long long prefix = 0, ans = 0;
        for(int i=0;i<nums.size();i++, ans++){
            prefix+=nums[i];
            if(prefix<=0)
                break;
        }
        
        return ans;
    }
};

## [2588. Count the Number of Beautiful Subarrays](https://leetcode.com/problems/count-the-number-of-beautiful-subarrays/) (<font color=#FFC011>Medium</font>)

### Solution

#### Observation 1

將 beautiful array 的每個元素的每個bit是 1 的數量統計出來。
> 以範例測資 \[4,3,1,2,4] 來舉例
> 100 4
> 011 3
> 001 1
> 010 2
> 100 4
> \-------
> 222

根據 beautiful array 的定義，beautiful array 的每個 bit 1的數量必是偶數。
而將一個 array 所有元素 xor，如果值等於 0，該陣列就是 beautiful array。

#### Observation 2

直接窮舉所有 subarray 的時間複雜度是 ***O(n^2)***，所以需要一個更快速的方法來計算，不然會 TLE。
這時候可以使用類似 prefix sum 的概念，只是這次需要計算的不是 sum 而是 xor。

> arr 1 2 3 4 5
> prefix sum 0 1 3 6 10 15
> prefix\[i] = nums\[0] xor nums\[1] ... xor nums\[i]
nums\[i] xor nums\[i+1] ... xor nums\[j] = prefix\[i-1] xor prefix\[j]

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

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

程式碼:

class Solution {
public:
    long long beautifulSubarrays(vector<int>& nums) {
        int prefix = 0;
        map<int, long long> mp;
        mp[0]++;
        
        cout<<prefix<<' ';
        for(int i=0;i<nums.size();i++){
            prefix = prefix ^ nums[i];
            cout<<prefix<<" ";
            mp[prefix]++;
        }
        cout<<"\n";

        long long ans = 0;
        for(auto &it: mp){
            ans += it.second*(it.second-1)/2;
        }
        
        return ans;
    }
};

## [2589. Minimum Time to Complete All Tasks](https://leetcode.com/problems/minimum-time-to-complete-all-tasks/description/) (<font color=#FF375F>Hard</font>)

### Solution(參考[這篇](https://leetcode.com/problems/minimum-time-to-complete-all-tasks/solutions/3286311/intuition-explained-video-solution-just-sort-greedy-c-java/?orderBy=most_votes))

#### Observation

對於整個排序好的區間來說，將電腦運行的時間盡可能的往後推是最好的，這樣可以使更多的區間可能被覆蓋，進而讓整體開機時間 minimize。

解題演算法
1. 先將 tasks 照結束時間由小到大排好。
2. 遍歷所有 tasks，假設當下task的區間有 t 時間被使用過，如果有的話就將該 task 所需時間減去 t。
3. 接著盡可能的將電腦使用的時間往後推遲，並同時記錄使用了多長的時間。
4. 最終紀錄的時間即是答案

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

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

程式碼:

class Solution {
    #define MAX 2005
public:
    static bool cmp(vector<int> &a, vector<int> &b){
        if(a[1] !=b[1])
            return a[1] < b[1];
        else return a[0] < b[0];
    }
    int findMinimumTime(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), cmp);

        bool isUsed[MAX] = {0};
        int ans = 0;

        for(auto &t: tasks){
            int useTime = 0;
            for(int i=t[0];i<=t[1];i++){
                if(isUsed[i])
                    useTime++;
            }

            for(int i=t[1];useTime<t[2];i--){
                if(!isUsed[i]){
                    isUsed[i] = true;
                    ans++;
                    useTime++;
                }
            }
        }

        return ans;
    }
};