###### tags: `BiWeekly Contest`
# BiWeekly Contest 109

## [2784. Check if Array is Good](https://leetcode.com/problems/check-if-array-is-good/) (<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 <= nums.length <= 100</code></li>
<li><code>1 <= num[i] <= 200</code></li>
</ul>
### Solution

#### 時間複雜度: $O(nlogn)$

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

程式碼:

class Solution {
public:
    bool isGood(vector<int>& nums) {
        if(nums.size()==1)
            return false;
        sort(nums.begin(), nums.end());
        
        int n = nums.size();
        for(int i=0;i<n-1;i++){
            if(nums[i] != i+1)
                return false;
        }
        if(nums.back() !=n-1)
            return false;
        return true;
    }
};

## [2785. Sort Vowels in a String](https://leetcode.com/problems/sort-vowels-in-a-string/) (<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 <= s.length <= 10⁵</code></li>
<li><code>s consists only of letters of the English alphabet in uppercase and lowercase.</code></li>
</ul>
### Solution

#### 時間複雜度: $O(nlogn)$

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

程式碼:

class Solution {
public:
    bool isvowel(char c){
        return c=='a' || c=='e' || c=='i' || c=='o' || c=='u';
    }
    string sortVowels(string s) {
        vector<char> pvec;
        vector<int> idx;
        for(int i=0;i<s.size();i++){
            if(isvowel(tolower(s[i]))){
                pvec.push_back(s[i]);
                idx.push_back(i);
            }
        }
        sort(pvec.begin(), pvec.end());
        sort(idx.begin(), idx.end());
        for(int i=0;i<pvec.size();i++){
            s[idx[i]] = pvec[i];
        }
        return s;
    }
};

## [2786. Visit Array Positions to Maximize Score](https://leetcode.com/problems/visit-array-positions-to-maximize-score/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>2 <= nums.length <= 10⁵</code></li>
<li><code>1 <= nums[i], x <= 10⁶</code></li>
</ul>
### Solution

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

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

程式碼:

class Solution {
public:
    typedef long long ll;
    long long maxScore(vector<int>& nums, int x) {
        int n=nums.size();
        vector<vector<ll> > dp(n, vector<ll>(2, -1e9));
        
        dp[0][nums[0]%2] = nums[0];
        
        for(int i=1;i<n;i++){
            if(nums[i]%2==0){
                dp[i][0] = max(dp[i-1][0]+nums[i], dp[i-1][1]+nums[i]-x);
                dp[i][1] = dp[i-1][1];
            }
            else {
                dp[i][0] = dp[i-1][0];
                dp[i][1] = max(dp[i-1][0]+nums[i]-x, dp[i-1][1]+nums[i]);
            }
        }
        
        return max(dp[n-1][0], dp[n-1][1]);
    }
};

## [2787. Ways to Express an Integer as Sum of Powers](https://leetcode.com/problems/ways-to-express-an-integer-as-sum-of-powers/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 <= n <= 300</code></li>
<li><code>1 <= x <= 5</code></li>
</ul>
### Solution

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

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

程式碼:

class Solution {
public:
    const int MOD = 1e9+7;

    int numberOfWays(int n, int x) {
        vector<int> p;
        for(int i=1;pow(i,x)<=n;i++)
            p.push_back(pow(i,x));
        
        vector<int> dp(n+1);
        dp[0] = 1;
        dp[p[0]] = 1;
        
        for(int i=1;i<p.size();i++){
            vector<int> next = dp;
            for(int j=p[i];j<=n;j++)
                next[j] = (next[j]+dp[j-p[i]])%MOD;
            dp = next;
        }
        
        return dp[n];
    }
};