tags: BiWeekly Contest

BiWeekly Contest 101

2605. Form Smallest Number From Two Digit Arrays(Easy)

限制 :

• 1 <= nums1.length, nums2.length <= 9
• 1 <= nums1[i], nums2[i] <= 9
• All digits in each array are unique.

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(Medium)

限制 :

• 1 <= s.length <= 105
• s consist of lowercase English letters.
• 1 <= chars.length <= 26
• chars consist of distinct lowercase English letters.
• vals.length == chars.length
• -1000 <= vals[i] <= 1000

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(Medium)

限制 :

• 1 <= k <= arr.length <= 105
• 1 <= arr[i] <= 109

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(Hard)

限制 :

• 2 <= n <= 1000
• 1 <= edges.length <= 1000
• edges[i].length == 2
• 0 <= ui, vi < n
• ui != vi
• There are no repeated edges.

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;
    }
};