###### tags: `Weekly Contest` # Weekly Contest 340 ## [2614. Prime In Diagonal](https://leetcode.com/problems/prime-in-diagonal/)(<font color=#00B8A3>Easy</font>) 限制 : <ul> <li><code>1 &lt;= nums.length &lt;= 300</code></li> <li><code>nums.length == nums<sub>i</sub>.length</code></li> <li><code>1 &lt;= nums<span style="font-size: 10.8333px;">[i][j]</span> &lt;= 4*10<sup>6</sup></code></li> </ul> ### Solution 就照題意檢查對角線是否是質數，但要注意找質數需要使用 ***O(sqrt(n))*** 的算法，不然會TLE。 #### 時間複雜度: ***O(n\*sqrt(m))*** #### 空間複雜度: ***O(1)*** 程式碼: ```c++= 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](https://leetcode.com/problems/sum-of-distances/)(<font color=#FFC011>Medium</font>) 限制 : <ul> <li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li> <li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li> </ul> ### Solution 可以先紀錄每個value相同的index。對於同一個value的index，如果想要快速的求出每個index的解，可以利用sliding window的方式，可以做到O(n)求解。 #### 時間複雜度: ***O(n)*** #### 空間複雜度: ***O(n)*** 程式碼: ```c++= 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; } }; ``` 參考[這篇](https://leetcode.com/problems/sum-of-distances/solutions/3395726/explained-with-images-easy-to-understand/?orderBy=most_votes)的寫法優化程式碼可讀性。 程式碼: ```c++= 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](https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/)(<font color=#FFC011>Medium</font>) 限制 : <ul> <li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li> <li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li> <li><code>0 &lt;= p &lt;= (nums.length)/2</code></li> </ul> ### 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)*** 程式碼: ```c++= 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](https://leetcode.com/problems/minimum-number-of-visited-cells-in-a-grid/)(<font color=#FF375F>Hard</font>) 限制 : <ul> <li><code>m == grid.length</code></li> <li><code>n == grid[i].length</code></li> <li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li> <li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li> <li><code>0 &lt;= grid[i][j] &lt; m * n</code></li> <li><code>grid[m - 1][n - 1] == 0</code></li> </ul> ### Solution 參考[這篇](https://leetcode.com/problems/minimum-number-of-visited-cells-in-a-grid/solutions/3397664/optimised-dp-using-priority-queue/?orderBy=most_votes&topicTags=heap-priority-queue)，運用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)*** 程式碼: ```c++= 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 類似[這篇](https://leetcode.com/problems/minimum-number-of-visited-cells-in-a-grid/solutions/3395695/bfs-with-skip-ahead/?orderBy=most_votes)的想法，想從前一篇的想法優化成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)*** 程式碼: ```c++= 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; } }; ```