###### tags: `BiWeekly Contest`
# BiWeekly Contest 101

## [2605. Form Smallest Number From Two Digit Arrays](https://leetcode.com/problems/form-smallest-number-from-two-digit-arrays/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 &lt;= nums1.length, nums2.length &lt;= 9</code></li>
<li><code>1 &lt;= nums1[i], nums2[i] &lt;= 9</code></li>
<li>All digits in each array are <strong>unique</strong>.</li>
</ul>

### Solution
因為1位數比2位數小，所以要先尋找num1和num2有無交集，有交集要優先使用交集裡最小的數字做為答案。
#### 時間複雜度: ***O(n)***

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

程式碼:

class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        minn=[]
        for num in nums1:
            if num in nums2:
                minn.append(num)
        if(len(minn)):
            return min(minn)
        else:
            return min(min(nums1)*10+min(nums2), min(nums2)*10+min(nums1))

## [2606. Find the Substring With Maximum Cost](https://leetcode.com/problems/find-the-substring-with-maximum-cost/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= s.length &lt;= 10⁵</code></li>
<li><code>s</code> consist of lowercase English letters.</li>
<li><code>1 &lt;= chars.length &lt;= 26</code></li>
<li><code>chars</code> consist of <strong>distinct</strong> lowercase English letters.</li>
<li><code>vals.length == chars.length</code></li>
<li><code>-1000 &lt;= vals[i] &lt;= 1000</code></li>
</ul>

### Solution
本質上就是求array中subarray總和最大的問題，直接套用該演算法即可。
#### 時間複雜度: ***O(n)***

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

程式碼:

class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        map<char, int> mp;
        for(int i=0;i<chars.size();i++)
            mp[chars[i]]=vals[i];
        
        int val=0, ans=0;
        for(int i=0;i<s.size();i++){
            if(mp.count(s[i]))
                val+=mp[s[i]];
            else val+=s[i]-'a'+1;
            ans=max(ans, val);
            if(val<0)
                val=0;
        }
        return ans;
    }
};

## [2607. Make K-Subarray Sums Equal](https://leetcode.com/problems/make-k-subarray-sums-equal/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= k &lt;= arr.length &lt;= 10⁵</code></li>
<li><code>1 &lt;= arr[i] &lt;= 10⁹</code></li>
</ul>

### Solution

#### 時間複雜度: ***O(nlogn?)***

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

程式碼:

{
public:
    long long makeSubKSumEqual(vector<int>& arr, int k)
    {
        long long int ans=0;
        if(arr.size()%k==0)
        {
            for(int i=0; i<k; i++)
            {
                vector<int>reg;
                int r=i;
                while(1)
                {
                    if(r>=arr.size())
                        break;
                    reg.push_back(arr[r]);
                    r+=k;
                }
                sort(reg.begin(),reg.end());

                for(int j=0; j<reg.size(); j++)
                {
                    ans+=abs(reg[reg.size()/2]-reg[j]);
                }
            }
        }
        else if(gcd(arr.size(),k)==1)
        {
            sort(arr.begin(),arr.end());
            for(int i=0; i<arr.size(); i++)
            {
                ans+=abs(arr[arr.size()/2]-arr[i]);
            }
        }
        else
        {
            vector<int>check;
            for(int i=0; i<arr.size(); i++)
                check.push_back(0);
            for(int i=0; i<arr.size(); i++)
            {
                if(check[i]==0)
                {
                    vector<int>reg;
                    int r=i;
                    while(1)
                    {
                        if(check[r]==1)
                            break;
                        reg.push_back(arr[r]);
                        check[r]=1;
                        r+=k;
                        if(r>=arr.size())
                            r=r-arr.size();
                    }
                    sort(reg.begin(),reg.end());
                    for(int j=0; j<reg.size(); j++)
                    {
                        ans+=abs(reg[reg.size()/2]-reg[j]);
                    }
                }
            }
        }
        return ans;
    }
};

## [2608. Shortest Cycle in a Graph](https://leetcode.com/problems/shortest-cycle-in-a-graph/)(<font color=#FF375F>Hard</font>)

限制 :

<ul>
<li><code>2 &lt;= n &lt;= 1000</code></li>
<li><code>1 &lt;= edges.length &lt;= 1000</code></li>
<li><code>edges[i].length == 2</code></li>
<li><code>0 &lt;= u_i, v_i &lt; n</code></li>
<li><code>u_i != v_i</code></li>
<li>There are no repeated edges.</li>
</ul>

### Solution
每個點都DFS一次，並記錄每個路過的點的深度，如果走到第二次就計算這2個深度的差值，該差值就是cycle的長度

應該能優化，假設有多個不相連的cycle，做完時把那個點所在的迴圈中的所有點記錄起來，之後就不用重做一次這個迴圈, 不過如果全部都相連就沒用了

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

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

程式碼:

class Solution {
public:
    int ans = INT_MAX;
    vector<int> level;
    int deep = 0;
    unordered_map<int, vector<int>> graph;
    
    void dfs(int now){
        for(int& i : graph[now]){
            /*cout << now << " " << i << " " << ans << endl;
            for(int j : level){
                cout << j << " ";
            }
            cout << endl;*/
            if(level[i] != -1){
                if(deep - level[i] > 1)
                    ans = min(ans, deep - level[i] + 1);
            }
            else{
                ++deep;
                level[i] = deep;
                dfs(i);
                --deep;
            }
        }
    }
    
    int findShortestCycle(int n, vector<vector<int>>& edges) {
        for(auto& e : edges){
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        
        level = vector<int>(n, -1);
        
        for(int i = 0; i < n; ++i){
            level[i] = 0;
            dfs(i);
            level = vector<int>(n, -1);
        }
        
        return ans == INT_MAX ? -1 : ans;
    }
};