tags: Weekly Contest

Weekly Contest 340

2614. Prime In Diagonal(Easy)

限制 :

• 1 <= nums.length <= 300
• nums.length == numsi.length
• 1 <= nums[i][j] <= 4*106

Solution

就照題意檢查對角線是否是質數，但要注意找質數需要使用 O(sqrt(n)) 的算法，不然會TLE。

時間複雜度: O(n*sqrt(m))

空間複雜度: O(1)

程式碼:

class Solution {
public:
    bool isPrime(int n){
        if(n==1)
            return false;
        for(int i=2;i<=sqrt(n);i++){
            if(n%i==0)
                return false;
        }
        return true;
    }
    int diagonalPrime(vector<vector<int>>& nums) {
        int n=nums.size();
        int ans=0;
        for(int i=0;i<n;i++){
            if(isPrime(nums[i][i]))
                ans=max(ans, nums[i][i]);
            if(isPrime(nums[i][n-i-1]))
                ans=max(ans, nums[i][n-i-1]);
        }
        return ans;
    }
};

2615. Sum of Distances(Medium)

限制 :

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

Solution

可以先紀錄每個value相同的index。對於同一個value的index，如果想要快速的求出每個index的解，可以利用sliding window的方式，可以做到O(n)求解。

時間複雜度: O(n)

空間複雜度: O(n)

程式碼:

class Solution {
public:
    vector<long long> distance(vector<int>& nums) {
        map<int, vector<long long> > mp;
        vector<long long> ans(nums.size(), -1);
        for(int i=0;i<nums.size();i++){
            if(mp[nums[i]].empty())
                mp[nums[i]].push_back(i);
            else mp[nums[i]].push_back(i+mp[nums[i]].back());
        }
        
        
        for(int i=0;i<nums.size();i++){
            long long sum=mp[nums[i]].empty()?0:mp[nums[i]].back();
            long long temp=0;
            if(ans[i]==-1){
                for(int j=0;j<mp[nums[i]].size();j++){
                    long long val=mp[nums[i]][j];
                    long long idx=j==0?val:val-mp[nums[i]][j-1];
                    ans[idx]=(idx*(j+1)-val)+(sum-(mp[nums[i]].size()-j)*idx);
                    sum-=idx;
                }
            }
        }
        return ans;
    }
};

參考這篇的寫法優化程式碼可讀性。
程式碼:

class Solution {
    typedef long long ll;
public:
    vector<long long> distance(vector<int>& nums) {
        int n=nums.size();
        map<int, vector<int> > mp;
        for(int i=0;i<n;i++)
            mp[nums[i]].push_back(i);

        vector<ll> ans(n);
        for(auto &it: mp){
            ll totalSum=0, preSum=0;
            vector<int>& indexes=it.second;

            for(auto &num: indexes)
                totalSum+=num;

            for(int i=0;i<indexes.size();i++){
                ll idx=indexes[i];
                ll postSum=totalSum-preSum-idx;

                ans[idx]=(idx*i-preSum)+(postSum-idx*(indexes.size()-i-1));
                preSum+=idx;
            }

        }
        return ans;
        
    }
};

2616. Minimize the Maximum Difference of Pairs(Medium)

限制 :

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= p <= (nums.length)/2

Solution

看到求minimum，就思考到可以使用binary search來思考最終的答案。這題的難點是怎麼確認nums裡是否有p個pair之間的差值小於等於某個值c。為了解決這個問題，我們可以採用greedy的做法。
演算法如下:

1. sort整個陣列。
2. 檢查相鄰的元素之間的差值是否<=c，如果<=c，就代表這一對pair可以被採用，所以要跳過這兩個pair所包含的元素，如果>c，就代表這一對pair不符合條件，接著檢查下一對pair即可。
3. 比對到底有幾對pair被採用，如果被採用的pair數量>=p，就代表在nums裡有p個pair之間的差值小於等於某個值c。反之則否。

時間複雜度: O(n*log(m))

空間複雜度: O(1)

程式碼:

class Solution {
public:
    bool canDo(vector<int> &nums, int limit, int p){
        int cnt=0;
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i+1]-nums[i]<=limit)
                cnt++, i++;
        }
        return cnt>=p;
    }
    int minimizeMax(vector<int>& nums, int p) {
        sort(nums.begin(), nums.end());

        int l=0, r=nums.back()-nums[0];
        while(l<r){
            int mid=(l+r)/2;

            if(canDo(nums, mid, p))
                r=mid;
            else l=mid+1;
        }
        return l;
    }
};

2617. Minimum Number of Visited Cells in a Grid(Hard)

限制 :

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 0 <= grid[i][j] < m * n
• grid[m - 1][n - 1] == 0

Solution

參考這篇，運用priority_queue優化dp的流程，將複雜度從O(n*m*(n+m))降低到O(n*m*(log(n)+log(m)))。

時間複雜度: O(n*m*(log(n)+log(m)))

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

程式碼:

class Solution {
    typedef pair<int, long long> pii;
public:
    int minimumVisitedCells(vector<vector<int>>& grid) {
        int n=grid.size(), m=grid[0].size();
        if(n==1&&m==1)
            return 1;
        vector<priority_queue<pii, vector<pii>, greater<pii> > > row(n), col(m);

        // {step, nextIdx}
        col[0].push({1, grid[0][0]});
        row[0].push({1, grid[0][0]});

        int ans;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0&&j==0)
                    continue;
                while(!row[i].empty()&&row[i].top().second<j)
                    row[i].pop();
                while(!col[j].empty()&&col[j].top().second<i)
                    col[j].pop();

                int step=INT_MAX;
                if(!row[i].empty())
                    step=min(row[i].top().first, step);
                if(!col[j].empty())
                    step=min(col[j].top().first, step);

                if(i==n-1&&j==m-1)
                    ans=step==INT_MAX?-1:step+1;
                
                if(step !=INT_MAX){
                    row[i].push({step+1, j+grid[i][j]});
                    col[j].push({step+1, i+grid[i][j]});
                }
            }
        }
        return ans;
    }
};

Incorrect solution

類似這篇的想法，想從前一篇的想法優化成bfs+greedy降低時間複雜度。對於每個row與column，紀錄他們已被探索的cell的最遠點，下一次要找該row或column時，直接從最遠點往後找即可。
但這個方法在遇到不連續的case會出問題，詳情請見以下測資。
[
[1,1,1,1,1],
[1,0,0,0,5],
[4,0,0,0,2],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0]
]

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

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

程式碼:

class Solution {
    typedef pair<int, long long> pii;
public:
    int minimumVisitedCells(vector<vector<int>>& grid) {
        int n=grid.size(), m=grid[0].size();
        
        queue<pii> qp;
        vector<int> rowmaxpos(n), colmaxpos(m);
        int step=1;

        rowmaxpos[0]=1, colmaxpos[0]=1;
        qp.push({0, 0});
        while(!qp.empty()){
            int sz=qp.size();
            while(sz--){
                int row=qp.front().first, col=qp.front().second;
                int nextRowIdx=col+grid[row][col]+1, nextColIdx=row+grid[row][col]+1;
                if(row==n-1&&col==m-1)
                    return step;

                for(int i=rowmaxpos[row];i<min(nextRowIdx, m);i++){
                    colmaxpos[i]=max(colmaxpos[i], row+1);
                    qp.push({row, i});
                }
                rowmaxpos[row]=max(rowmaxpos[row], min(nextRowIdx, m));

                for(int i=colmaxpos[col];i<min(nextColIdx, n);i++){
                    rowmaxpos[i]=max(rowmaxpos[i], col+1);
                    qp.push({i, col});
                }
                colmaxpos[col]=max(colmaxpos[col], min(nextColIdx, n));
                qp.pop();
            }
            step++;
        }
        
        return -1;
    }
};