JZX 轻语

LeetCode 1443 - 收集树上所有苹果的最少时间

不难得知，如果一个子树中没有苹果可摘，那么就没必要经过；否则，进去和出来都要花费2个单位时间(指的是进去和离开这个子树的用时，不包括内部的采摘时间)。因此，我们可以使用DFS进行后序遍历，递归计算每个子树所需的采摘时间。如果子树中至少一个子树有苹果可摘(即返回值不为0)，或者当前子树的根节点有苹果，则消耗时间为2 + 所有子树的采摘时间；否则，消耗时间为0。最后，返回从根节点出发的总采摘时间...

Posted by Jeza Chen on August 22, 2024

LeetCode 1442 - 形成两个异或相等数组的三元组数目

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

不难得知，对于满足条件的三元组(i,j,k)，由于arr[i..j-1]的异或结果a等于arr[j..k]的异或结果a，那么a和b的异或结果为0，换句话说，子数组arr[i..k]所有的元素异或结果为0。反过来思考，如果某个长度为l的子数组中，所有元素异或的结果为0，那么该子数组中可以构造l - 1个满足条件的三元组。因此，题目转化为寻找所有元素异或结果为0的子数组，并计算其长度l，然后累加...

Posted by Jeza Chen on August 22, 2024

LeetCode 1441 - 用栈操作构建数组

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

根据栈后进先出的特点，不难得知栈内的元素必定为递增序列，且对于栈中两个相邻的元素a和b，如果b - a > 1，那么a和b之间的元素（已经被弹出了）必定是在bPush前，发生了b - a - 1次Push和Pop操作（即这些中间的元素进栈后又出栈了，然后b入栈前，栈顶元素为a）。因此，我们可以使用prev记录上一个元素(初始值可为0)，然后遍历target数组，对于每个元素num，如果...

Posted by Jeza Chen on August 22, 2024

LeetCode 3152 - 特殊数组 II

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

一开始的想法是：先从左到右遍历数组，将不满足nums[i] % 2 != nums[i + 1] % 2的下标存入invalid_inx_vec；然后对于每个查询，使用二分法找到from和to之间的第一个不满足条件的下标，如果存在则返回false，否则返回true。这种做法的时间复杂度为O(nlogn)。后面参考了官方题解，发现可以使用动态规划的方法，时间复杂度为O(n)：使用dp[i]...

Posted by Jeza Chen on August 14, 2024

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

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

有两种做法：第一种则是动态规划，记dp[i][j](其中j = 0, 1)为数组后i个元素构成的子数组(只考虑这i个元素，不考虑前面的翻转影响)翻转为j的最少次数，则如果nums[i] == j，则dp[i][j] = dp[i - 1][j]；否则dp[i][j] = dp[i - 1][1 - j] + 1。最后返回min(dp[n][0], dp[n][1])。第二种做法，则是基于...

Posted by Jeza Chen on August 13, 2024

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

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

使用贪心法，从左到右遍历数组，如果当前元素为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 1443 - 收集树上所有苹果的最少时间

LeetCode 1442 - 形成两个异或相等数组的三元组数目

LeetCode 1441 - 用栈操作构建数组

LeetCode 3152 - 特殊数组 II

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

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

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

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

LeetCode 3206 & 3208 - 交替组

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

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04