第422场周赛(3/4)

Q1:3340:检查平衡字符串

分别计算所有奇数下标与偶数下标的和，判断是否相等即可

class Solution {
public:
    bool isBalanced(string num) {
        int num1=0;
        int num2=0;
        for(int i=0;i<num.size();i++)
            {
                if(i%2==0)
                    num1+=num[i]-'0';
                else num2+=num[i]-'0';
            }
        if(num1==num2)
            return true;
        else return false;
    }
};

Q2 3341.到达最后一个房间的最少时间 I

思路

1. **优先队列 (Priority Queue)**：使用优先队列（最小堆）来存储 `(时间, x, y)`，优先访问时间较小的房间。 2. **移动限制**：每次从一个房间到相邻房间时，如果相邻房间的 `moveTime` 小于等于当前时间，则可以直接进入；否则，需要等待到指定的 `moveTime` 才能进入。 3. **标记访问**：用一个二维数组 `visited` 记录到达每个房间的最小时间，以避免重复访问较大的时间路径。 4. **终止条件**：一旦到达 `(n-1, m-1)` 房间，返回当前时间即为所需的最短时间。

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
           int n = moveTime.size();
        int m = moveTime[0].size();
        vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        pq.emplace(0, 0, 0);
        vector<vector<int>> visited(n, vector<int>(m, INT_MAX));
        visited[0][0] = 0;

        while (!pq.empty()) {
            auto [time, x, y] = pq.top();
            pq.pop();
            
            if (x == n - 1 && y == m - 1) {
                return time;
            }
            
            for (auto [dx, dy] : directions) {
                int nx = x + dx;
                int ny = y + dy;
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    int waitTime = max(time, moveTime[nx][ny]); 
                    if (visited[nx][ny] > waitTime) { 
                        visited[nx][ny] = waitTime;
                        pq.emplace(waitTime+1, nx, ny); 
                    }
                }
            }
        }
        
        return -1; 
    }
};

Q3 3342 到达最后一个房间的最少时间 II

思路：

在上题的基础上加一个判断即可

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
          int n = moveTime.size();
        int m = moveTime[0].size();
        vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<>> pq; 
        pq.emplace(0, 0, 0, 0); 
        vector<vector<int>> visited(n, vector<int>(m, INT_MAX));
        visited[0][0] = 0;

        while (!pq.empty()) {
            auto [time, x, y, moves] = pq.top(); 
            pq.pop();
            
            if (x == n - 1 && y == m - 1) {
                return time;
            }
            
            for (auto [dx, dy] : directions) {
                int nx = x + dx;
                int ny = y + dy;
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    
                    int waitTime = max(time, moveTime[nx][ny]);
                  
                    int moveCost = (moves % 2 == 0) ? 1 : 2; 
                    if (visited[nx][ny] > waitTime + moveCost) { 
                        visited[nx][ny] = waitTime + moveCost; 
                        pq.emplace(waitTime + moveCost, nx, ny, moves + 1); 
                    }
                }
            }
        }
        
        return -1; 

    }
};

Q4 3343.统计平衡排列的数目

（不会，本来想补题，结果发现好像看不太懂题解）