JZX 轻语

LeetCode 954 - 二倍数对数组

类似于题目2007，使用贪心法从小到大处理数字。但该题涉及到负数，因此，排序的逻辑需要改为按绝对值递增处理。先使用哈希表cnt_map对数字计数。然后按绝对值从小到大遍历数字num，尝试抽取cnt_map[num]次组(num, num * 2)，如果数字num * 2的计数小于cnt_map[num]，则无法完成题目要求，直至所有的牌处理完毕。对于特殊情况num == 0，需要特殊处理，即...

Posted by Jeza Chen on May 28, 2024

LeetCode 951 - 翻转等价二叉树

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

典型的树上递归问题，根据题目描述，只需要判断两棵树的根节点是否相同，然后递归判断左子树和右子树是否相同即可。在比较子树的等价时，需要考虑两种情况：1. 左子树和右子树的根节点相同；2. 左子树和右子树的根节点不同。对于第二种情况，需要交换左右子树的比较顺序。 class Solution: def flipEquiv(self, root1: Optional[TreeNode...

Posted by Jeza Chen on May 28, 2024

LeetCode 950 - 按递增顺序显示卡牌

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

该题目正向构造比较困难，可以考虑逆向思考，模拟分析结果数组中按照题目要求的那样弹出的下标顺序(0,2,4,...)(首先弹出第0个，然后第1个放在后面，弹出第2个，第3个放在后面，…)，然后将牌从小到大依次填入到这些下标即可。我们可以使用队列先维护下标(0..deck.length-1)，计算按题目要求弹出的下标顺序，然后对牌进行排序，按这些下标顺序构造结果即可。 class Solu...

Posted by Jeza Chen on May 28, 2024

LeetCode 949- 给定数字能组成的最大时间

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

这道题没啥比较高效的做法，官方题解也是暴力枚举。因为时间的范围是固定的，所以可以直接暴力枚举所有可能的时间，然后找到最大的时间即可。为了尽可能减少枚举的次数，可以先对输入的数字进行排序，然后按照HH:MM的格式，从大到小枚举所有可能的时间，找到第一个合法的时间即可。 class Solution: def largestTimeFromDigits(self, arr: Lis...

Posted by Jeza Chen on May 28, 2024

LeetCode 922 - 按奇偶排序数组 II

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

题目说的是“排序”，实际上不是严格按照递增或递减顺序排，而是说将奇数元素放在奇数位置上，偶数元素放在偶数位置上。朴素的做法就是使用两个数组，分别存放奇数和偶数元素，然后再合并。但是这样的空间复杂度是O(n)，无法就地完成。可以利用双指针的方法，一个指针遍历奇数位置，一个指针遍历偶数位置，然后分别停在不符合要求的位置上，然后交换即可。 class Solution: def so...

Posted by Jeza Chen on May 28, 2024

LeetCode 937 - 重新排列日志文件

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

简单的字符串处理题，首先按第一个空格分割每个日志，取出标识符和内容，然后检查内容是否全为数字或空格判断是否为数字日志：如果是，则按序加入到数字日志列表中，否则，加入(内容, 日志全文)到字母日志列表中(如果内容相同，进而比对日志全文，实际上就是在比对标识符了，没必要单独放标识符在元组里面)。最后，对字母日志列表进行排序，然后按序取出日志全文并追加数字日志组成即可。官解的答案也非常简洁：自...

Posted by Jeza Chen on May 27, 2024

LeetCode 2028 - 找出缺失的观测数据

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

首先根据平均值mean和需要插入的元素数量n计算缺失的元素总和remaining = mean * (len(rolls) + n) - sum(rolls)。如果remaining不满足插入的最低/最高要求，即remaining < n或remaining > 6 * n(全都插入1，都超过总和 or 全都插入6，都不够)。然后均匀地构造缺失数组即可，即首先每个元素都初始化为r...

Posted by Jeza Chen on May 27, 2024

LeetCode 934 - 最短的桥

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

搜索题目，首先找到其中一个岛屿，并将其进行“染色”以便于和另一个岛屿区分 - 例如将其所有的元素都置为2，并记录下所有的边界元素。然后使用BFS搜索，将边界元素加入队列，不断扩展，直至找到另一个岛屿。第一个找到的岛屿的距离即为最短的桥长。 from collections import deque class Solution: moves = ((-1, 0), (1, ...

Posted by Jeza Chen on May 26, 2024

LeetCode 932 - 漂亮数组

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

一个需要点巧思的分治构造题目，如何将一个漂亮数组分解为两个漂亮子数组A和B的构造，且对于任一选取于漂亮数组A的元素a和任一选取于漂亮数组B的元素b(即两端分别选择于不同的子数组)，均不存在a + b = 2 * c的情况。这里的c是a和b之间的任意元素。通过观察可以知道，对于一个等差数组，我们将奇数位置的元素放在子数组A，偶数位置的元素放在子数组B，则可以满足题目要求。因为对于任意的满足上述...

Posted by Jeza Chen on May 26, 2024

LeetCode 1738 - 找出第K大的异或坐标值

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

前缀和思路的二维+异或版本，可以就地使用原数组维护前缀和，即matrix[i][j]为矩阵matrix中(0, 0)到(i, j)的异或和，且matrix[i][j] = matrix[i-1][j] ^ matrix[i][j-1] ^ matrix[i-1][j-1] ^ matrix[i][j](因为matrix[i - 1][j - 1]实际上都包含在matrix[i-1][j]和m...

Posted by Jeza Chen on May 26, 2024

LeetCode 954 - 二倍数对数组

LeetCode 951 - 翻转等价二叉树

LeetCode 950 - 按递增顺序显示卡牌

LeetCode 949- 给定数字能组成的最大时间

LeetCode 922 - 按奇偶排序数组 II

LeetCode 937 - 重新排列日志文件

LeetCode 2028 - 找出缺失的观测数据

LeetCode 934 - 最短的桥

LeetCode 932 - 漂亮数组

LeetCode 1738 - 找出第K大的异或坐标值

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04