###### tags: `Weekly Contest`
# Weekly Contest 349

## [2733. Neither Minimum nor Maximum](https://leetcode.com/problems/neither-minimum-nor-maximum/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 &lt;= nums.length &lt;= 100</code></li>
<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
<li>All values in <code>nums</code> are distinct</li>
</ul>

### Solution
先找出最大值與最小值，再檢查陣列是否有既非最大值也非最小值的數。
#### 時間複雜度: $O(n)$

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

程式碼:

class Solution:
    def findNonMinOrMax(self, nums: List[int]) -> int:
        maxx, minn = max(nums), min(nums)
        for num in nums:
            if num != maxx and num != minn:
                return num
        return -1

雞婆寫了一下C++的:

class Solution {
public:
    int findNonMinOrMax(vector<int>& nums) {
        auto max = max_element(nums.begin(), nums.end());
        auto min = min_element(nums.begin(), nums.end());
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i] != *min && nums[i] != *max)
            return nums[i];
        }
        return -1;
    }
};

## [2734. Lexicographically Smallest String After Substring Operation](https://leetcode.com/problems/lexicographically-smallest-string-after-substring-operation/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= s.length &lt;= 3 * 10⁵</code></li>
<li><code>s</code> consists of lowercase English letters</li>
</ul>

### Solution
從字串的頭開始找，直到第一個是 $a$ 的 index，就是需要做 operation 的部分。注意有一個特例是全是 $a$ 的字串，那就只需要對最後一個 $a$ 做 operation 就好。
#### 時間複雜度: $O(n)$

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

程式碼:

class Solution {
public:
    string smallestString(string s) {
        bool flag = false;
        for(int i=0;i<s.size();i++){
            if(s[i] !='a'){
                while(i<s.size()&&s[i] !='a')
                    s[i++]--;
                flag=true;
                break;
            }
        }
        if(!flag)
            s[s.size()-1] = 'z';
        return s;
    }
};

## [2735. Collecting Chocolates](https://leetcode.com/problems/collecting-chocolates/)(<font color=#FFC011>Medium</font>)

限制 :

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

### Solution
最多轉 $n-1$ 輪。

對於第 $k$ 輪，$nums[i]$ 的最佳買價是 $min(nums[i-k...i])$，注意這裡的陣列是循環陣列，也就是如果 $i-k < 0$，會自動替換成 $n + i - k$。

所以第 $k$ 輪的最佳解公式是 $所有nums[i]的最佳買價和 + x*k$。

計算出這 $n-1$ 輪每輪所對應的答案，其中最小者即是題目所求。
#### 時間複雜度: $O(n^2)$

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

程式碼:

class Solution {
    typedef long long ll;
public:
    long long minCost(vector<int>& nums, int x) {
        // n*minn + x*n-1
        // (n-1)*minn + x*n-2 +
        int n = nums.size();
        vector<vector<int> > dp(n, vector<int>(n, 2e9));
        for(int i=0;i<n;i++){
            for(int j=i, k=0;k<n;k++){
                dp[i][k] = k==0?nums[j]:min(dp[i][k-1], nums[j]);
                if(j==0){
                    j = n-1;
                }
                else {
                    j--;
                }
            }
        }
        
        long long ans = 1e18;
        for(int i=0;i<n;i++){
            long long sum = 0;
            for(int j=0;j<n;j++)
                sum+=dp[j][i];
            ans = min(ans, sum + ll(i)*x);
        }
        return ans;
    }
};

## [2736. Maximum Sum Queries](https://leetcode.com/problems/maximum-sum-queries/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>nums1.length == nums2.length</code> </li>
<li><code>n == nums1.length </code></li>
<li><code>1 &lt;= n &lt;= 10⁵</code></li>
<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 10⁹ </code></li>
<li><code>1 &lt;= queries.length &lt;= 10⁵</code></li>
<li><code>queries[i].length == 2</code></li>
<li><code>x_i == queries[i][1]</code></li>
<li><code>y_i == queries[i][2]</code></li>
<li><code>1 &lt;= x_i, y_i &lt;= 10⁹</code></li>
</ul>

### Solution

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

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

程式碼: