JZX 轻语

LeetCode 970 - 强整数

这种要求返回所有满足条件的结果题目，一般都使用递归+回溯的方法来解决，但此题因为只涉及两个数的枚举，因此仅需使用双重循环枚举两个数的幂，将其和加入到结果直至不满足条件即可。需要注意几点：由于题目要求返回的结果不能重复，因此需要使用set来存储结果，最后再转换为list返回。注意x和y的大小关系，通过swap保证外层循环遍历的x是较大的数，这样...

Posted by Jeza Chen on May 31, 2024

LeetCode 969 - 煎饼排序

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

挺好玩的排序，通过分析可知，其类似于冒泡or选择排序，一种可行的从大到小、从后往前排好数组做法是：当处理第i大的元素时，先将其翻转到首位(若其现在处在第j个位置，则翻转前j个元素)，然后再翻转到第i位即可。这样可以保证不会破坏已经排好且放置在数组最后的元素。由于在翻转的过程中，每个元素的位置会发生多次变动，我们不必完全模拟翻转的全过程，可以利用前面的翻转结果来计算当前处理元素的现位置...

Posted by Jeza Chen on May 31, 2024

LeetCode 962 - 最大宽度坡

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

朴素的做法是对于每一个元素，在其左侧的子数组中从左往右检查第一个小于等于它的元素，并更新上述最长的距离。这种双重循环会超时，需要想办法复用前面已遍历元素的大小数据。这种综合大小+索引情况可以考虑单调栈。对于此问题，可以利用单调栈维护已遍历数组以arr[0]开头的最长递减序列，在此单调栈中，每个元素在索引上递增，而在大小关系递减，最长递减序列意味着栈中每个元素的右侧元素是原数组中其右侧第一个比...

Posted by Jeza Chen on May 29, 2024

LeetCode 959 - 由斜杠划分区域

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

这种二维空间融合/扩展+求解划分数量的问题，可以考虑使用并查集的方式~我们可以将第i行第j列的格子编号为n * i + j，然后将每个格子等分为”左右”两部分，其中第i行第j列左右两部分编号为2 * (n * i + j)及2 * (n * i + j) + 1。这样，我们可以根据每个格子的划分形式，将左右两部分与其相邻格子的左右两部分进行合并，最终得到的连通分量即为答案。划分的规则...

Posted by Jeza Chen on May 29, 2024

LeetCode 958 - 二叉树的完全性检验

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

不难得知，当对完全二叉树进行层次遍历时，其结果构造为连续的非空节点+连续的空节点。使用队列对二叉树进行层次遍历，直到遇到第一个空节点。随后检查队列里面剩余的节点，如果全是是空节点则为True，否则返回False。 from collections import deque class Solution: def isCompleteTree(self, root: Opti...

Posted by Jeza Chen on May 29, 2024

LeetCode 2981 - 找出出现至少三次的最长特殊子字符串 I

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

朴素的做法是使用双重循环，枚举并计数所有的的特殊子字符串(即所有字符相同，当遇到不一样的字符时终止内层循环)，但这样会超时。我们可以通过滑动窗口的方式节省遍历连续重复字符的时间，维护当前字符last_ch及其连续重复次数recessive_cnt，并使用二维数组ch_recessive_counts[i][j]维护第i个小写字母连续组成j次的子串计数。然后在每次循环最后，更新计数信息ch_r...

Posted by Jeza Chen on May 29, 2024

LeetCode 954 - 二倍数对数组

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

类似于题目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 970 - 强整数

LeetCode 969 - 煎饼排序

LeetCode 962 - 最大宽度坡

LeetCode 959 - 由斜杠划分区域

LeetCode 958 - 二叉树的完全性检验

LeetCode 2981 - 找出出现至少三次的最长特殊子字符串 I

LeetCode 954 - 二倍数对数组

LeetCode 951 - 翻转等价二叉树

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

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

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04