JZX 轻语

LeetCode 3191 - 使二进制数组全部等于 1 的最少操作次数 I

使用贪心法，从左到右遍历数组，如果当前元素为0，则将其及后面两个元素都进行翻转。最后判断最后两个元素是否为1(满足全1条件)，如果是则返回操作次数，否则返回-1。证明上述做法的翻转次数什么是最优的：首先不难得知，每个(长度为3)子数组的翻转次数至多为1：因为翻转两次相当于不反转，没意义。其实，我们将翻转操作看作一个序列：如a1->a2->...(即翻转数组nums...

Posted by Jeza Chen on August 13, 2024

LeetCode 3209 - 子数组按位与值为 K 的数目

Flash 此文章属于Flash闪念部分的短文

第四题反而没那么难想，其实就是计数DP。记dp[i][j]为以nums[i]结尾的子数组中，按位与值为j的数目。那么有状态转移方程：dp[i][j & nums[i]] += dp[i - 1][j]。由于j的范围是0~2^10，因此可以使用dict来存储dp数组。 class Solution: def countSubarrays(self, nums: List[...

Posted by Jeza Chen on August 10, 2024

LeetCode 3207 - 与敌人战斗后的最大分数

Flash 此文章属于Flash闪念部分的短文

需要仔细理解题意：需要分数至少为1的时候才能使用操作2(并不是能量至少为1…)！因为无论敌人能量如何，战胜敌人的分数都为1分。因此可以使用贪心法解决：首先对敌人的能量进行排序，然后每次选择能量最小的敌人进行战斗，直到自己的能量不足以战斗为止。这样可以保证每次战斗的分数最大。如果自己的能量不足以继续战斗，那么就选择能量最大的敌人进行标记，以获得尽可能多的能量。可以使用队列解决，也可以使用双指针...

Posted by Jeza Chen on August 10, 2024

LeetCode 3206 & 3208 - 交替组

Flash 此文章属于Flash闪念部分的短文

交替组I由于只需求连续3块瓷砖的交替，做法很简单，直接枚举模拟判断colors[i] == colors[(i + 2) % n] and colors[i] != colors[(i + 1) % n]即可；交替组II将瓷砖组的数量泛化为任意数量k，则需要考虑双指针的方法：left指针指向当前组的起始位置，right指针指向当前组的下一个比较位置。如果colors[right] != ...

Posted by Jeza Chen on August 10, 2024

LeetCode 2940 - 找到 Alice 和 Bob 可以相遇的建筑

Flash 此文章属于Flash闪念部分的短文

一开始自然地想到了单调栈：先假定bi > ai(如果bi == ai，已经相遇，则直接返回ai即可)，如果bi比ai高，则Alice直接走到bi即可；否则，Bob需要找到第一个比ai高的建筑。此类找到右侧第一个比当前位置高的建筑的问题，可以使用单调栈解决: 如果第一个比bi高的建筑(即为ci)也比ai高，则Alice可以直接走到这个建筑；否则，Bob需要继续找到右侧第一个比ai高的建筑...

Posted by Jeza Chen on August 10, 2024

LeetCode 3240 - 最少翻转次数使二进制矩阵回文 II

Flash 此文章属于Flash闪念部分的短文

在3239的基础上，条件升级为行回文且列回文，且1的次数必须被4整除。分析可知，由于两种方向都对称，每个元素都可能会有3个镜像位置，也就是题目中为什么要求能被4整除: 无论该位置是0还是1，通过翻转满足题目要求后，这四个位置要么全0，要么全1，1的个数都会被4整除。这样就解决了吗？并不是！我们还需要考虑奇数行和奇数列的情况：如果行数和列数都是奇数，那么中心位置必须为0，否...

Posted by Jeza Chen on August 9, 2024

LeetCode 3239 - 最少翻转次数使二进制矩阵回文 I

Flash 此文章属于Flash闪念部分的短文

直接计算两种方法(要么保证所有行回文，要么保证列回文)的翻转次数，取最小值即可: 遍历每一行/列，使用双指针判断是否回文，如果不是则累加翻转次数。 class Solution: def minFlips(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) ...

Posted by Jeza Chen on August 9, 2024

LeetCode 3238 - 求出胜利玩家的数目

Flash 此文章属于Flash闪念部分的短文

每个玩家都用一个哈希表记录每个颜色的次数，如果次数大于等于2就将其加入胜利玩家的集合(set)中。最后返回集合的长度即可。 class Solution: def winningPlayerCount(self, n: int, pick: List[List[int]]) -> int: cnt_map = [defaultdict(int) for _...

Posted by Jeza Chen on August 9, 2024

LeetCode 3212 - 统计 X 和 Y 频数相等的子矩阵数量

Flash 此文章属于Flash闪念部分的短文

二维前缀和问题，由于子矩阵需要包含位置(0,0)，直接判断二维前缀0计数和1计数是否相等即可。 class Solution: def numberOfSubmatrices(self, grid: List[List[str]]) -> int: m, n = len(grid), len(grid[0]) prev_x = [[0] *...

Posted by Jeza Chen on August 8, 2024

LeetCode 3211 - 生成不含相邻零的二进制字符串

Flash 此文章属于Flash闪念部分的短文

直接回溯法，如果上一个字符为'0'，则当前字符只能为'1'，否则可以为'0'或'1'。 class Solution: def validStrings(self, n: int) -> List[str]: ans = [] def traceback(cur_idx: int, cur_str: str): i...

Posted by Jeza Chen on August 8, 2024

LeetCode 3191 - 使二进制数组全部等于 1 的最少操作次数 I

LeetCode 3209 - 子数组按位与值为 K 的数目

LeetCode 3207 - 与敌人战斗后的最大分数

LeetCode 3206 & 3208 - 交替组

LeetCode 2940 - 找到 Alice 和 Bob 可以相遇的建筑

LeetCode 3240 - 最少翻转次数使二进制矩阵回文 II

LeetCode 3239 - 最少翻转次数使二进制矩阵回文 I

LeetCode 3238 - 求出胜利玩家的数目

LeetCode 3212 - 统计 X 和 Y 频数相等的子矩阵数量

LeetCode 3211 - 生成不含相邻零的二进制字符串

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04