Leetcode 每日一题练习

[ninijia]

2064. 分配给商店的最多商品的最小值

题解

本题初始可能会想到将产品的数量加和后按照商店个数均分，让每个商店分配到的产品个数尽可能接近平均数，这样就可以最小化单个商店可能分得的最大产品个数，但这样分配未必能保证每个商店都能分到产品，抑或在给每个商店分配完接近平均数的产品后产品仍有剩余（有的产品个数远小于平均数但每个商店只能分得一个产品）。

但这样的思路有其道理，其中可取的地方在于我们需要找到一个数字p，使得每个商店分配得到的产品数量都不大于p，同时能够将产品最终分配完，但p不一定是之前考虑的平均数，而且p肯定有多个，因为当p已经能够让商店完成产品分配时，比p大的数肯定同样可以。我们需要找到的是最小的p。

验证当每个商店分配的产品数量不大于p时能否分配完成比较简单，对每个产品，当个数大于p时，将p个分配给一个商店，否则将剩余全部产品分配给一个商店。若到最后产品能正好分配给全部商店没有剩余则分配成功。

则此时可以想到，要找的最小的p有如下的特性，大于p的产品个数限制可以让产品分配给商店，小于p则不行，p是二者的交界，则这其实就变成了一个查找问题，考虑一般的在有序数组中查找某个具体的数，其实也隐含了类似的性质，即该数字右侧的数都大于该数字，该数字左侧的数都小于该数字，这个数字本身是与它的相对大小的分界。因此这类有二分性质的问题都可以考虑用二分查找来解决。

代码

class Solution {
public:
    // 检查是否能在每个商店最多分配 mid 个产品的情况下完成分配
    bool canDistribute(int n, vector<int>& quantities, int mid) {
        int stores_needed = 0;
        for (int q : quantities) {
            stores_needed += (q + mid - 1) / mid;
        }
        return stores_needed <= n;
    }
    
    int minimizedMaximum(int n, vector<int>& quantities) {
        // 二分查找的左边界是1（每个商店至少能分配1个产品）
        int left = 1;
        // 右边界是单个产品的最大数量（因为最差情况下，最大的那堆产品也要能分完）
        int right = *max_element(quantities.begin(), quantities.end());
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canDistribute(n, quantities, mid)) {
                // 如果当前的mid可以完成分配，尝试减小mid
                right = mid;
            } else {
                // 如果当前的mid不能完成分配，需要增大mid
                left = mid + 1;
            }
        }
        
        return left;
    }
};

[ninijia]

1574. 删除最短的子数组使剩余数组有序

题解

本题需要移除一个子数组使得剩余的数组是一个非减数组。由于子数组一定是连续的，则我们需要从中间删去某个长度的子数组使得数组剩余的两边拼接在一起后满足题目条件，那么前后的两个子数组自身必须要满足非减条件，因此可以先找到以数组开头作为起始和以数组末尾作为末尾的两个最长的符合条件的子数组。

找到该符合条件的子数组后，需要让两个子数组拼接后满足题目条件，则需要找到前面子数组中以某个数字结尾的部分和后面子数组中以某个数字开头的部分拼接后可以得到完整的满足条件的数组，则这个结尾的数字需不大于后面的开头的数字。同时使得从这两个数组中被丢弃的部分的长度和最小。

在得到前后两个最长数组后，若找到符合要求的同时让被丢弃部分最小的拼接数组，可使用双指针，分别指向前后两个数组的开头，前面的指针不断向后移动，指向的数字不断变大，同时移动后面的指针直到找到符合不小于前面数字的数字位置，不断计算被丢弃的数组的长度和，如此反复，直到前面的指针指向前面数组的末尾或者后面的指针指向后面数组的末尾为止。

代码

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();
        int left = 0, right = n - 1;
        
        while (left < n - 1 && arr[left] <= arr[left + 1]) {
            left++;
        }
        
        if (left == n - 1) return 0;
        
        while (right > left && arr[right - 1] <= arr[right]) {
            right--;
        }
        
        int result = min(n - left - 1, right);
        
        int i = 0, j = right;
        while (i <= left && j < n) {
            if (arr[i] <= arr[j]) {
                result = min(result, j - i - 1);
                i++;
            } else {
                j++;
            }
        }
        
        return result;
    }
};

[ninijia]

3254. 长度为 K 的子数组的能量值 I

题解

本题子数组的长度是固定的，故可以使用滑动窗口，将窗口长度固定为k不断向后滑动，记录窗口中以最后一个数字结尾的递增子数组的长度和最后一个数字。这样将窗口向后移动时每当添加了一个新的数字进入窗口，将该数字和最后一个数字比较，如果和最后一个数字相邻且比最后一个数字大则将记录的递增子数组长度加一，比最后一个数字小或者不相邻则将子数组长度初始化为1。若以最后一个数字结尾的递增子数组长度和k相同则将最后一个数字（因为是递增数组，最后一个数字就是最大的数字）放入results数组中，否则放入-1。

代码

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int sortedlen = 0;
        int last = 0;
        for(int i=0;i<k;i++){
            if(nums[i] > last && nums[i] == last+1){
                sortedlen++;
            }else{
                sortedlen = 1;
            }
            last = nums[i];
        }
        vector<int> results;
        for(int i=k;i<nums.size();i++){
            if(sortedlen == k){
                results.push_back(last);
            }else{
                results.push_back(-1);
            }
            if(nums[i] > last && nums[i] == last+1){
                if(sortedlen < k){
                    sortedlen++;
                }
            }else{
                sortedlen = 1;
            }
            last = nums[i];
        }
        if(sortedlen == k){
            results.push_back(last);
        }else{
            results.push_back(-1);
        }
        return results;
    }
};

[ninijia]

862. 和至少为 K 的最短子数组

题解

本题求子数组的和满足大于等于K的全部子数组中长度最小的长度是多少。这种求子数组和的有关性质的题目首先可以想到使用前缀和来解决，但之前使用前缀和解题时是因为前缀和有一个很重要的性质即单调性，当所有数字均为非负数时前缀和是单调增的，因此我们可以根据题目要求来找到对应的下标，如同样是求子数组和至少为K的问题，若是单调增的前缀和，则根据下标为i对应的前缀和减去K的前缀和P来找到对应的小于等于P的前缀和对应的下标，即可知道所有子数组和至少为K的子数组。

但本题中存在负数，因此前缀和不是单调增的，这时可以考虑能否构造一个单调增的前缀和，则可使用单调栈来构造这样的前缀和，考虑栈顶前缀和的大小和新的前缀和的大小关系，若栈顶前缀和比新的前缀和大，则可弹出栈顶，因为对于还未访问到的前缀和，若后面的前缀和和栈顶的差大于等于k，则因为新的前缀和比栈顶小同时其对应的下标位置在栈顶的后面，则后面的前缀和和新前缀和的差必定也大于等于k且二者对应下标的差比和当前栈顶下标的差更小，故栈顶可以舍弃。

要求和不小于K的子数组就需要根据当前的前缀和计算出符合要求的前缀和大小，并在单调栈中找到不大于这个符合要求的前缀和大小的前缀和对应的下标，寻找这个符合要求的前缀和每次都要从头遍历单调栈，能否通过优化减少从头遍历的次数呢。很简单，题目要求找到满足要求的前缀和的最短长度，则我们只要找到刚好满足要求前缀和对应的下标位置，在这个下标之前的都可以直接丢弃，后续不再遍历这些位置。因为后面未遍历的前缀和要么比当前的大，要么比当前的小，比当前大则当前前缀和能取得的使子数组大于等于k的下标位置对于后面的同样是可以取得的，但后面到该下标的距离一定比当前下标大，如果比当前小，那么要取得使子数组大于等于k需要在当前前缀和对应的解的位置前面找更小的前缀和来使得子数组满足要求，这样得到的长度最多只能和当前前缀和对应的解的长度相同，不会更优。

根据这两个优化，可以构造一个单调的队列，使得两端都能弹出元素并满足上面的优化方法。先计算出前缀和，再不断遍历前缀和并求得满足条件的子数组长度与记录的最小长度比较并不断更新即可。

代码

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();

        vector<long long> preSum(n + 1);
        preSum[0] = 0;
        
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        
        int res = n + 1;
        // 使用双端队列存储下标
        deque<int> dq;
        
        // 遍历前缀和数组
        for (int i = 0; i <= n; i++) {

            while (!dq.empty() && preSum[i] <= preSum[dq.back()]) {
                dq.pop_back();
            }
            

            while (!dq.empty() && preSum[i] - preSum[dq.front()] >= k) {
                res = min(res, i - dq.front());
                dq.pop_front();
            }
            
            dq.push_back(i);
        }
        
        return res == n + 1 ? -1 : res;
    }
};

[ninijia]

1652. 拆炸弹

题解

本题是简单题，题目场景的设置非常有意思，题目本身只需按照题面将对应的数字按条件替换，只要了解循环数组即可，因为本题要么使用ith后面的k个数字要么使用ith前面的k个数字，即窗口大小是固定的，因此可使用滑动窗口。当k大于0时，从头遍历数组向后滑动，k小于0则从尾部遍历数组向前滑动，使用滑动窗口每次去掉一个数字再加上新加入窗口的数字即得当前窗口内的数字和。可以避免重复计算已有的部分数字和。

代码

class Solution {
public:
    vector<int> decrypt(vector<int>& code, int k) {
        int n = code.size();
        if (k == 0) {
            return vector<int>(n, 0);
        } else if (k > 0) {
            int sumnow = 0;
            vector<int> result;
            for (int i = 1; i <= k; i++) { 
                sumnow += code[i];
            }
            for (int j = 1; j <= n; j++) {
                result.push_back(sumnow);
                sumnow -= code[j % n];
                sumnow += code[(j + k) % n];
             }
            return result;
        } else { 
            k = -k;
            int start = n - k;
            int end = n - 1;
            int sumnow = 0;
            vector<int> result;
             for (int i = start; i <= end; i++) { // Calculate initial sum
                sumnow += code[i];
            }
            for (int j = 0; j < n; j++) {
                result.push_back(sumnow);
                sumnow -= code[(j + n -k)%n];
                sumnow += code[j];
            }
            return result;
        }
    }
};

[ninijia]

2461. 长度为 K 子数组中的最大和

题解

对于这样固定长度的子数组问题，首先肯定要使用滑动窗口，再思考本题中的限制条件，子数组中所有的数字都必须是不相同的，那么可以用一个数组来记录窗口中所有数字的个数，但仅记录某个数字自身的出现次数仍不方便我们了解窗口中有重复的数字有多少个。因此还可以用一个变量记录窗口中有重复的数字个数，个数为0时说明窗口中不再有重复数字。向前不断滑动窗口，根据移出数字和移入数字处理相关情况，在窗口内没有重复数字时更新窗口数字和的最大值即可。

代码

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int exist[100001] = {};
        long long int maxsum = 0;
        int repeat = 0;
        long long int arraysum = 0;
        for(int i=0;i<k;i++){
            if(exist[nums[i]] == 1){
                repeat++;
                exist[nums[i]]++;
                arraysum += nums[i];
            }else{
                exist[nums[i]]++;
                arraysum += nums[i];
            }
        }
        if(repeat == 0){
            maxsum = arraysum;
        }
        int left = 0;
        int right = k;
        while(right < nums.size()){
            if(exist[nums[right]] == 1){
                repeat++;
            }
            exist[nums[right]]++;
            arraysum += nums[right];
            if(exist[nums[left]] == 2){
                repeat--;
            }
            exist[nums[left]]--;
            arraysum -= nums[left];
            if(repeat == 0){
                maxsum = max(maxsum, arraysum);
            }
            right++;
            left++;
        }
        return maxsum;
    }
};

[ninijia]

2516. 每种字符至少取 K 个

题解

本题要求返回能取得k个a,b,c字符需要的最少拿取次数，并不能使用贪心，因为选择从左面或者右面拿取字符会影响后面能得到目标结果时拿取的总个数，如左右都是字符a，但左侧第二个字符是b，右侧第二个字符是a，如果只需要每个字符拿1个，拿左侧的a后就可以继续拿取左侧的b，但若拿取右侧的a则想拿取b就要再拿掉左侧的a后才能拿到b。

因此需要考虑左侧的选择会对右侧的选择造成什么影响，要把这种影响全部找出来并记录下来。因此可以找到刚好可以满足题目条件的左侧数组的长度，并将左侧指针指向这个子数组的末尾，在此情况下，当左侧指针向左移动时，左侧数组会不满足题目条件，因此需要右侧数组来补充缺少的字符使得总体满足题目条件，因此右侧指针向左移动直到移动过的部分的右侧数组包含的字符和左侧数组包含的字符和满足题目条件。计算此时左右子数组的长度和，如此反复，直到左侧指针移动到数组开头。

但有可能数组本身就不可能满足题目要求，因此要先判断一下数组中存在的各个字符的个数，如果不满足要求直接返回-1。

代码

class Solution {
public:
    int takeCharacters(string s, int k) { 
      int ca=0,cb=0,cc=0;
        int n=s.size();
        int ans=n;
        for(int i=0;i<n;i++){
            if(s[i]=='a') ca++;
            if(s[i]=='b') cb++;
            if(s[i]=='c') cc++;
        }
        if(ca<k||cb<k||cc<k) return -1;
        int i=n-1,j=n-1;
        while(i>=0){
            if(s[i]=='a') ca--;
            if(s[i]=='b') cb--;
            if(s[i]=='c') cc--;
            while(ca<k||cb<k||cc<k){
            if(s[j]=='a') ca++;
            if(s[j]=='b') cb++;
            if(s[j]=='c') cc++;
                j--;
            }
            ans=min(ans,i+n-1-j); i--;
        }
        return ans;
    
    }
};

[ninijia]

2257. 统计网格图中没有被保卫的格子数

题解

本题模拟守卫能看到的区域，首先创建mxn的数组，先遍历所有墙的位置将对应位置的值设置为2，记录墙的个数，再遍历守卫，对每个守卫所在的位置向四个方向遍历直到到数组边界或者遇到墙为止，将这些位置的值设置为1，同时记录遍历过程中将0变为1的个数，最终用数组总数减去墙和守卫以及守卫看守的位置数的和得最终结果。

这种遍历并且按照属性设置对应位置的值的方法可以得到正确的结果，但对有些示例会超时，思考为什么会超时以及如何优化，可以想到如果从某个守卫出发开始向某一方向（比如向右）遍历数组时遇到了另一个守卫，起始没有必要再继续向该方向遍历了，因为后面的位置遇到的新守卫同样也可以看到，此时可以直接结束遍历，因此我们可以将墙的位置值设置为3，将守卫位置的值先全部设置为2，在遍历数组时判断要遍历的位置的值是否小于2，这样就避免了多个守卫看同一个方向时对重叠看守的部分进行多次重复遍历。当然这里不会完全不重复，只是大大减少了重复量。

代码

class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        vector<vector<int>> cells(m,vector<int>(n,0));
        for (auto wall : walls){
            cells[wall[0]][wall[1]] = 3;
        }
        int guardpos = 0;
        int direction[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        for (auto guard : guards){
            cells[guard[0]][guard[1]] = 2;
        }
        for (auto guard : guards){
            for(int i=0;i<4;i++){
                int pos[2] = {guard[0]+direction[i][0], guard[1]+direction[i][1]};
                while(pos[0]>=0&&pos[0]<m&&pos[1]>=0&&pos[1]<n&&cells[pos[0]][pos[1]]<2){
                    if(cells[pos[0]][pos[1]] == 0){
                        guardpos++;
                        cells[pos[0]][pos[1]] = 1;
                    }
                    pos[0] += direction[i][0];
                    pos[1] += direction[i][1];
                }
            }
        }
        return m*n-guardpos-guards.size()-walls.size();
    }
};

[ninijia]

1072. 按列翻转得到最大值等行数

题解

本题先思考简单例子，对于两行01串，在什么情况下通过多次翻转同一个位置上的数字最终可以使得两行行内数字完全相同，如00，10显然无论怎么翻转都只可能有一行数字是完全相同的，另一行则不可能相同，再考虑10，01，只需翻转任意一列，两行数字都会相同。由此可以猜测对于任意两行数字，若这两行数字每一位上的数都不相同，则这两行数字最终可以通过翻转实现两行数字行内完全相同，注意数字只能取0，1两种，因此若两行数字满足每一位都不相同，要想三行数字满足行内相同，第三行数字必定和这两行数字中的某一行完全相同。

则若能通过翻转使得任意两行的行内数字完全相同，这两行要么相同，要么相反。我们只需统计相同行和对应的相反行的数量和，找到最大值就得到本题的解。

问题在于如何统计，考虑要统计的行要么完全相同，要么相反，则可以将二者用一个同样的值来表示，此处就要用到哈希，问题是如果将每一行中的每一位视为简单的二进制位，考虑行的长度最大为300，显然不能用整数直接装下，因此要么使用分块哈希，要么充分利用c++中已有的哈希实现，将每一行转换为字符串再作为哈希的键。由于相反的行我们想使用同一个键值来表示，因此对每一行都构造出该行对应的字符串和该行对应的相反行的字符串，取两个字符串中字典序小的字符串，这样就将相反行都用二者中字典序小的字符串来表示，进而统计满足相同或者相反行的总数。

代码

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        unordered_map<string, int> count;
        int m = matrix.size(), n = matrix[0].size();
        
        for (const auto& row : matrix) {
            string pattern(n, '0');
            string flipped(n, '0');
            
            for (int j = 0; j < n; j++) {
                pattern[j] = row[j] + '0';
                flipped[j] = (1 - row[j]) + '0';
            }
            
            count[min(pattern, flipped)]++;
        }
        
        int maxCount = 0;
        for (const auto& [_, cnt] : count) {
            maxCount = max(maxCount, cnt);
        }
        return maxCount;
    }
};

[ninijia]

1861. 旋转盒子

题解

本题图里的石头挺有意思的，像哪里来的魔法石。题目直观的想象是将一个容器翻转90°，翻转后石头会自由落体直到落到一块比较坚实的“地面”上。考虑原来的行和翻转后的列的关系，原来的第一行翻转后会变为第一列，如果共有m行n列，那么原来位于(p,q)位置的会变为位于(q,m-p-1)。先构建一个n x m的空数组，遍历原始的m x n数组，当按行遍历时统计该行中遇到过的石头的个数直到遇到一个障碍物，此时将该障碍物按照转换后的位置填入空数组中，并根据该障碍物前面的石头个数在空数组中该障碍物的位置向上填充对应数量的石头。如此反复，即得最终转换后的数组。

代码

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int m = box.size();
        int n = box[0].size();
        vector<vector<char>> rotate(n,(vector<char>(m,'.')));
        int stones = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if (box[i][j] == '#'){
                    stones++;
                }else if(box[i][j] == '*'){
                    rotate[j][m-i-1] = '*';
                    while(stones > 0){
                        rotate[j-stones][m-i-1] = '#';
                        stones--;
                    }
                }
            }
            while(stones > 0){
                rotate[n-stones][m-i-1] = '#';
                stones--;
            }
        }
        return rotate;
    }
};

[ninijia]

1975. 最大方阵和

题解

本题通过不断将相邻数字变为自己的相反数的操作，最终一定可以将负数变为相邻位置(相当于对负号进行了传递)，这时再进行一次操作即可使得两个负数都变为正数。因此遍历并记录数组中负数的个数，同时记录下绝对值最小的数（在加和时减少的最少）。若负数个数为偶数则直接将数字全部变为正数加和，若为奇数则除绝对值最小的保持为负数外其余均按照正数加和。

因此本题可以直接将所有负数均变为正数并加和，最后根据总体负数的奇偶性再对绝对值最小的数进行加减。这样仅需遍历一遍数组就能得到结果。

这样计算没有考虑包含0的情况，在包含0的情况下，所有负数均可通过将负号最终传递给0从而变成正数，0自身是没有符号的，就像黑洞一样吸掉了全部符号。因此在包含0的情况下无需考虑负数个数的奇偶性，直接将所有数字按绝对值加和就得到了最终结果。

代码

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        int addsmall = 100001;
        int nums = 0;
        long long int sum = 0;
        bool zero = false;
        for (const auto& row : matrix){
            for(const auto& num : row){
                if(num > 0){
                    if(num < addsmall){
                        addsmall = num;
                    }
                    sum += num;
                }else if(num < 0){
                    nums++;
                    if (-num < addsmall){
                        addsmall = -num;
                    }
                    sum += -num;
                }else{
                    zero = true;
                }
            }
        }
        if(nums % 2 == 1 && !zero){
            sum += -2 * addsmall;
        }
        return sum;
    }
};

[ninijia]

773. 滑动谜题

题解

本题是一道难题，可以将其视为一个搜索问题，但这种搜索问题正因非常经典从而非常难。类似这种问题比较出名的场景是围棋，但围棋的棋子是属于不同方的，因此在构建棋盘状态时除了棋子自身的位置还要加上棋子的归属这一属性，而本题相对简化，不存在这个问题，相当于每个棋子仅有数字作为自身的属性。最终搜索的目标也是固定的状态。

则可以一边构造出状态树一边搜索，状态树中每个节点是棋盘当前的布局，边表示边相连的节点可以通过一次0的移动互相转换。通过广度优先搜索不断遍历树的每一层，直到找到目标节点，此时遍历的深度即为需要的移动步数，而若全部遍历完后仍未达到目标状态，则返回-1。

难点在于，在展开这棵状态树时，我们不想让底层的节点重复已经构造过的状态节点，如何记录已经构造过的状态节点呢，可以将棋盘上的数字按顺序写成一个字符串，将字符串放入set中，这样只需查看set中是否已经包含这个字符串即可知道是否已经构造过这个状态。

另一方面，对于每个位置可以替换的数字的位置是固定的，因此将每个位置可以替换的数字的位置在字符串中的下标保存起来，使用时直接将字符串的当前位置与可替换的位置进行交换即得到构造的两个新字符串。

本题如果能想到将状态作为节点，将边作为状态之间关联的连接，后续其实相当比较容易，将这个模型提炼出来本身就是一个难点。这要求我们要更深入的理解数据结构，如图，图中的节点未必只能表示一个值，它可以是一种抽象的状态，只要状态之间有某种关联就可以构造边来连接，树同理。

代码

class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        string target = "123450";
        string start;
        for (const auto& row : board) {
            for (int num : row) {
                start += to_string(num);
            }
        }
        
        vector<vector<int>> neighbors = {
            {1, 3},    
            {0, 2, 4}, 
            {1, 5},    
            {0, 4},    
            {3, 1, 5}, 
            {2, 4}     
        };
        
        queue<pair<string, int>> q;
        unordered_set<string> visited;
        
        q.push({start, 0});
        visited.insert(start);
        
        while (!q.empty()) {
            auto [state, moves] = q.front();
            q.pop();
            
            if (state == target) {
                return moves;
            }
            
            int zero_pos = state.find('0');
            for (int neighbor : neighbors[zero_pos]) {
                string new_state = state;
                swap(new_state[zero_pos], new_state[neighbor]);
                
                if (visited.find(new_state) == visited.end()) {
                    q.push({new_state, moves + 1});
                    visited.insert(new_state);
                }
            }
        }
        
        return -1;
    }
};

[ninijia]

2924. 找到冠军 II

题解

本题使用简化版拓扑排序可以解决，拓扑排序在以前的题目中曾经讲解过，在有向无环图中，拓扑排序表示的是一种抽象的先后关系，如若节点均表示数字，则这种先后关系就可以是数字之间的相对大小，若把节点看成一个个在排队的人，则这种先后关系可以是一个人排在另一个人的前面。这种抽象的关系可以对应到各种实际情况中。对于本题，一条有向边相当于一支队伍打赢了另外一支队伍，那么拓扑排序的起始队伍就相当于打赢了其他队伍但没人打赢它，如果这样的队伍只有一个，显然就是冠军，不止有一个那说明还需要更多比赛。

之所以说是简化的拓扑排序，在于本题理解题面可以用拓扑排序的思想，但实际解题，只需要记录下所有节点（队伍）的入度（即有几支队伍打赢了它），最终找到所有入度为0的队伍，只有一个直接返回，否则返回-1。

代码

class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        vector<int> nodein(n,0);
        for(const auto& edge : edges){
            nodein[edge[1]]++;
        }
        int zero = -1;
        for(int i=0;i<n;i++){
            if(nodein[i] == 0 && zero == -1){
                zero = i;
            }else if(nodein[i] == 0){
                return -1;
            }
        }
        return zero;
    }
};

[ninijia]

3243. 新增道路查询后的最短距离 I

题解

本题每次在增加了一条新路线后可以使用dijistra算法从0节点开始寻找到其他节点的最短路径，一旦找到到n-1节点的最短路径就停止dijistra算法。

最初会想到在添加新路径后可以直接从最初的距离减去添加的新路径中间节省的距离，但这种做法的问题在于新添加的路径可能会与之前添加过的路径有交叉，则无法确定应该减去的节省的距离是多少（如a->b为4,b->c为3，但a->d为5,d->c为1，实际选择d这条路径总距离更短）。而用dijistra算法求出的到每个节点的距离已经是最短距离，一旦确定了到n-1的距离就得到了最终结果。

代码

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<vector<pair<int, int>>> adj(n);
        
        for(int i = 0; i < n-1; i++) {
            adj[i].push_back({i+1, 1}); 
        }
        
        vector<int> answer;

        for(const auto& query : queries) {
            int u = query[0];
            int v = query[1];
            
            adj[u].push_back({v, 1});
            
            answer.push_back(dijkstra(adj, n, 0, n-1));
        }
        
        return answer;
    }
    
private:
    int dijkstra(const vector<vector<pair<int, int>>>& adj, int n, int start, int end) {
        vector<int> dist(n, INT_MAX);
        dist[start] = 0;
        
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({0, start});
        
        while(!pq.empty()) {
            int d = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            
            if(u == end) return d;
            
            if(d > dist[u]) continue;
            
            for(const auto& [v, weight] : adj[u]) {
                if(dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }
        
        return dist[end];
    }
};

[ninijia]

2290. 到达角落需要移除障碍物的最小数目

题解

本题是一道难题，关键在于如何建模寻路的过程，一般提到寻路或者路径规划相关的问题，都会想到这是一个图问题，本题中如何将在数组中寻路转换为在图上寻路，并能得到最小成本就是解题的关键。在图上找到成本最小的路径无异于在图上寻找两个节点之间的最短路径，由于边的权重不存在负值，这就是一道典型的可以用dijistra算法解决的问题。

问题在于如何转换，考虑从任何一个位置出发向四个方向移动，如果遇到墙，想要经过墙就必须要花费移除墙的“成本”。最终要求的是移除最少数量的墙的路径，则每个墙都可以视为要花费1点成本。对于没有墙的位置，移动过去不需要花费成本，则将矩阵中每个位置都视为一个独立的节点，如果某个位置有墙，则向这个位置移动的成本就为1，每个位置都和四个方向的其他位置节点之间存在边，如果移动的成本为1，则边权为1，否则为0，此时就转化成了在图上寻找最短路径的问题，可以使用dijistra算法解决。

代码

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        vector<int> dx = {-1, 1, 0, 0};
        vector<int> dy = {0, 0, -1, 1};

        // 优先级队列实现dijistra算法
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        
        dist[0][0] = grid[0][0];
        pq.push({dist[0][0], 0}); 
        
        while (!pq.empty()) {
            auto [cost, pos] = pq.top();
            pq.pop();
            
            int x = pos / n;
            int y = pos % n;
            
            if (cost > dist[x][y]) continue;
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int newCost = cost + grid[nx][ny];
                    
                    if (newCost < dist[nx][ny]) {
                        dist[nx][ny] = newCost;
                        pq.push({newCost, nx * n + ny});
                    }
                }
            }
        }
        
        return dist[m-1][n-1];
    }
};

[ninijia]

2577. 在网格图中访问一个格子的最少时间

题解

本题仍可以使用dijistra算法解决，像昨天的问题一样，将每个位置视为节点，只不过将每个位置对应的时间视为到这个节点的总成本，同时因为可以在两个节点间来回移动直到时间足够能移动到下一个节点，则只要能从原始位置通过一个时间间隔移动到相邻的位置就可以通过来回移动直到时间足够能移动到下一个相邻可移动位置。但要注意，在来回移动的时候要想继续向当前位置的下一个相邻位置移动，需要移动偶数次步数，因为奇数次步数会移动回当前位置的前一个位置，偶数才会移动回当前位置。

在最开始，只要能从初始位置移动到相邻位置，后面就可以使用dijistra找到到达右下角的最短路径。

代码

class Solution {
public:
    int minimumTime(vector<vector<int>>& grid) {
        // 如果一开始就无法移动，直接返回-1
        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
        
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        dist[0][0] = 0;
        
        vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        priority_queue<pair<int, pair<int, int>>, 
                      vector<pair<int, pair<int, int>>>, 
                      greater<>> pq;
        pq.push({0, {0, 0}});
        
        while (!pq.empty()) {
            auto [time, pos] = pq.top();
            auto [x, y] = pos;
            pq.pop();
            
            if (time > dist[x][y]) continue;
            
            for (const auto& dir : dirs) {
                int nx = x + dir.first;
                int ny = y + dir.second;
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int nextTime = time + 1;
                    // 需要等待到满足要求的时间
                    if (grid[nx][ny] > nextTime) {
                        // 如果时间差是奇数，需要多等一步
                        nextTime = grid[nx][ny];
                        if ((grid[nx][ny] - time) % 2 == 0) {
                            nextTime++;
                        }
                    }
                    
                    if (nextTime < dist[nx][ny]) {
                        dist[nx][ny] = nextTime;
                        pq.push({nextTime, {nx, ny}});
                    }
                }
            }
        }
        
        return dist[m-1][n-1] == INT_MAX ? -1 : dist[m-1][n-1];
    }
};

[ninijia]

2097. 合法重新排列数对

题解

本题是一道典型的图问题，每一个pair有一个start和end相当于一个有向边的起始和终止节点。而本题即找图中一条可以一次性经过图中全部边且不重复的路径问题，也就是一个欧拉图问题。这种图问题如果不了解相关知识是比较难解的，像在一个欧拉图中寻找欧拉路径的问题当前已经有比较经典的算法，故本题可以使用Hierholzer算法解决。注意本题中要寻找的是欧拉通路而不是欧拉回路。对于欧拉图的简单介绍可以参考

欧拉图

代码

class Solution {
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        unordered_map<int, vector<int>> graph;
        unordered_map<int, int> inDegree, outDegree;
        
        for (const auto& pair : pairs) {
            int u = pair[0], v = pair[1];
            graph[u].push_back(v);
            outDegree[u]++;
            inDegree[v]++;
        }

        int start = pairs[0][0];
        for (const auto& [node, _] : graph) {
            if (outDegree[node] > inDegree[node]) {
                start = node;
                break;
            }
        }
        
        deque<int> path;
        stack<int> stk;
        stk.push(start);
        
        while (!stk.empty()) {
            int u = stk.top();
            if (graph[u].empty()) {
                path.push_front(u);
                stk.pop();
            } else {
                stk.push(graph[u].back());
                graph[u].pop_back();
            }
        }

        vector<vector<int>> result;
        for (auto it = path.begin(); it != prev(path.end()); ++it) {
            result.push_back({*it, *next(it)});
        }
        
        return result;
    }
};

[ninijia]

1346. 检查整数及其两倍数是否存在

题解

本题可以使用集合，在遍历数组的过程中将每个数的2倍和1/2都放入集合中，在继续遍历的过程中一旦碰到了集合中已有的数字就返回true，否则返回false。本题只要求返回是否存在这样的组合不要求返回具体的组合对应的下标，故使用集合记录满足条件的数字即能得到最终结果，若要返回具体的下标，则可以构造结构体将每个数对应的原始下标也保存下来。

代码

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        set<int> sets;
        for(const int& num : arr){
            if (sets.find(num) != sets.end()){
                return true;
            }
            if(num % 2 == 0){
                sets.insert(num/2);
            }
            sets.insert(num*2);
        }
        return false;
    }
};

[ninijia]

1455. 检查单词是否为句中其他单词的前缀

题解

本题将待搜索的单词直接与句子中的单词比较，遇到不同的字符就跳到下一个被空格分隔的单词重新比较，直到遇到能比对成功的单词（计数并返回单词的下标）或者遍历到句子结尾为止。

代码

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        int n = searchWord.size();
        int curindex = 1;
        int curchar = 0;
        bool success = true;
        for (const auto& ch : sentence){
            if(!success && ch!=' '){
                continue;
            }
            if(ch == ' '){
                success = true;
                curchar = 0;
                curindex++;
                continue;
            }
            if(ch == searchWord[curchar]){
                curchar++;
                if(curchar == n){
                    return curindex;
                }
            }else{
                success = false;
            }

        }
        return -1;
    }
};

[CRI4250 (虚无)]

感谢你的分享