leetcode第422场周赛

3340. 检查平衡字符串

给你一个仅由数字 0 - 9 组成的字符串 num。如果偶数下标处的数字之和等于奇数下标处的数字之和，则认为该数字字符串是一个 平衡字符串。

如果 num 是一个 平衡字符串，则返回 true；否则，返回 false。

示例

示例 1：

输入：num = "1234"

输出：false

解释：

偶数下标处的数字之和为 1 + 3 = 4
奇数下标处的数字之和为 2 + 4 = 6
由于 4 不等于 6，num 不是平衡字符串。

示例 2：

输入：num = "24123"

输出：true

解释：

偶数下标处的数字之和为 2 + 1 + 3 = 6
奇数下标处的数字之和为 4 + 2 = 6
由于两者相等，num 是平衡字符串。

提示

2 <= num.length <= 100
num 仅由数字 0 - 9 组成

Python代码实现

class Solution:
    def isBalanced(self, num: str) -> bool:
        # 初始化变量
        left = 0  # 偶数下标和
        right = 0  # 奇数下标和
        index = 0  # 当前下标

        # 遍历字符串
        while index < len(num):
            if index % 2 == 0:
                # 偶数下标处的数字累加到left
                left += int(num[index])
            else:
                # 奇数下标处的数字累加到right
                right += int(num[index])
            index += 1

        # 返回偶数和与奇数和是否相等
        return left == right

C语言实现

bool isBalanced(char* num) {
    int left = 0;  // 偶数下标和
    int right = 0; // 奇数下标和
    int length = strlen(num); // 获取字符串的长度

    // 遍历字符串
    for (int i = 0; i < length; i++) {
        int digit = num[i] - '0'; // 将字符转换为对应的数字
        if (i % 2 == 0) {
            left += digit; // 偶数下标处的数字累加到left
        } else {
            right += digit; // 奇数下标处的数字累加到right
        }
    }

    // 返回偶数和与奇数和是否相等
    return left == right;
}

题解分析

思路：使用两个变量分别记录偶数下标和奇数下标的数字之和。
循环遍历：遍历字符串中的每个字符，判断当前下标是偶数还是奇数，将对应的数字累加到对应的变量中。
判断：遍历完成后，检查偶数下标和与奇数下标和是否相等，相等则返回 True，否则返回 False。

这种方法的时间复杂度为 O(n)，其中 n 是字符串 num 的长度。

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

有一个地窖，其中包含 n*m个房间，它们呈网格状排布。

给你一个大小为 n*m 的二维数组 moveTime，其中 moveTime[i][j] 表示在这个时刻以后，你才可以开始往这个房间移动。你在时刻 t = 0从房间 (0, 0) 出发，每次可以移动到相邻的一个房间。在相邻房间之间移动需要的时间为 1 秒。

请你返回到达房间 (n - 1, m - 1) 所需要的最少时间。

如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么称这两个房间是相邻的。

示例

示例 1：

输入：moveTime = [[0,4],[4,4]]

输出：6

解释：

在时刻 ( t = 4 ) 从房间 (0, 0) 移动到房间 (1, 0)，花费 1 秒。
在时刻 ( t = 5 ) 从房间 (1, 0) 移动到房间 (1, 1)，花费 1 秒。

示例 2：

输入：moveTime = [[0,0,0],[0,0,0]]

输出：3

解释：

在时刻 ( t = 0 ) 从房间 (0, 0) 移动到房间 (1, 0)，花费 1 秒。
在时刻 ( t = 1 ) 从房间 (1, 0) 移动到房间 (1, 1)，花费 1 秒。
在时刻 ( t = 2 ) 从房间 (1, 1) 移动到房间 (1, 2)，花费 1 秒。

示例 3：

输入：moveTime = [[0,1],[1,2]]

输出：3

Java 代码实现

class Solution {
    public int minTimeToReach(int[][] moveTime) {
        int n = moveTime.length;
        int m = moveTime[0].length;

        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        queue.offer(new int[]{0, 0, 0 ,1});
        dp[0][0] = 0;

        int[] dirX = {1, -1, 0, 0};
        int[] dirY = {0, 0, 1, -1};

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0], y = current[1], time = current[2];

            if (x == n - 1 && y == m - 1) {
                return time;
            }

            for (int d = 0; d < 4; d++) {
                int newX = x + dirX[d];
                int newY = y + dirY[d];

                if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
                    int nextT = Math.max(time, moveTime[newX][newY]) + current[3];
                    if (nextT < dp[newX][newY]) {
                        dp[newX][newY] = nextT;
                        queue.offer(new int[]{newX, newY, nextT ,1});
                    }
                }
            }
        }
        return dp[n - 1][m - 1];
    }
}

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct {
    int x, y, time, step;
} Node;

// 交换两个节点的辅助函数
void swap(Node **a, Node **b) {
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

// 小根堆的向上调整
void heapifyUp(Node **heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[index]->time >= heap[parent]->time) break;
        swap(&heap[index], &heap[parent]);
        index = parent;
    }
}

// 小根堆的向下调整
void heapifyDown(Node **heap, int size, int index) {
    while (2 * index + 1 < size) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = index;

        if (left < size && heap[left]->time < heap[smallest]->time) {
            smallest = left;
        }
        if (right < size && heap[right]->time < heap[smallest]->time) {
            smallest = right;
        }
        if (smallest == index) break;

        swap(&heap[index], &heap[smallest]);
        index = smallest;
    }
}

// 插入节点到小根堆中
void push(Node **heap, int *size, Node node) {
    heap[*size] = (Node *)malloc(sizeof(Node));
    *(heap[*size]) = node;
    (*size)++;
    heapifyUp(heap, *size - 1);
}

// 从小根堆中取出最小元素
Node pop(Node **heap, int *size) {
    Node result = *heap[0];
    free(heap[0]);
    heap[0] = heap[*size - 1];
    (*size)--;
    heapifyDown(heap, *size, 0);
    return result;
}

int minTimeToReach(int **moveTime, int moveTimeSize, int *moveTimeColSize) {
    int n = moveTimeSize;
    int m = moveTimeColSize[0];

    // 初始化 dp 数组
    int dp[50][50];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j] = INT_MAX;
        }
    }

    // 方向数组
    int dirX[4] = {1, -1, 0, 0};
    int dirY[4] = {0, 0, 1, -1};

    // 初始化小根堆
    Node *heap[2500];
    int heapSize = 0;
    push(heap, &heapSize, (Node){0, 0, 0, 1});
    dp[0][0] = 0;

    while (heapSize > 0) {
        Node current = pop(heap, &heapSize);
        int x = current.x, y = current.y, time = current.time;

        // 检查是否是当前最短路径时间
        if (time > dp[x][y]) {
            continue;
        }

        // 如果到达终点，返回时间
        if (x == n - 1 && y == m - 1) {
            // 释放小根堆中剩余节点的内存
            for (int i = 0; i < heapSize; i++) {
                free(heap[i]);
            }
            return time;
        }

        // 遍历四个方向
        for (int d = 0; d < 4; d++) {
            int newX = x + dirX[d];
            int newY = y + dirY[d];

            // 检查边界
            if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
                int nextT = (time > moveTime[newX][newY] ? time : moveTime[newX][newY]) + current.step;
                if (nextT < dp[newX][newY]) {
                    dp[newX][newY] = nextT;
                    push(heap, &heapSize, (Node){newX, newY, nextT, 1});
                }
            }
        }
    }

    // 如果未找到路径，释放小根堆中剩余节点的内存
    for (int i = 0; i < heapSize; i++) {
        free(heap[i]);
    }

    return dp[n - 1][m - 1];
}

题解分析

优先队列：使用自定义的 Node 结构体保存节点信息（x、y、time）。优先队列确保每次处理的节点为当前时间最小的节点。
动态规划数组 dp：dp 数组保存每个房间的最短到达时间。
方向数组：dirX 和 dirY 实现四个方向的移动。
BFS遍历：从起点出发，使用优先队列和方向数组遍历所有房间，记录到达每个