JZX 轻语

LeetCode 984 - 不含AAA或BBB的字符串

很容易想到贪心的做法，一种可行的构造是：首先通过2-1-2-1的交错构造，尽可能快地消耗较多数量地字符，直至两个字符的数量相同，然后再1-1交错构造即可。期间会发生（数量较少的）某个字符提前用完的情况，需要进行一些特殊判断。 class Solution: def strWithout3a3b(self, a: int, b: int) -> str: ...

Posted by Jeza Chen on May 31, 2024

LeetCode 971 - 翻转二叉树以匹配先序遍历

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

树上递归有点费脑子的题目。大体思路是在这个棵树上进行先序遍历，然后尝试匹配当前子树的先序遍历序列，如果不匹配，那么就需要翻转当前子树的左右子树，然后再次进行匹配。匹配以递归的方式进行：如果当前子树的根节点和先序遍历序列的当前位置不匹配，那么就返回False，否则就递归匹配左右子树。如果左子树匹配失败，那么就尝试翻转当前子树的左右子树，然后再次递归匹配左子树；如果左子树匹配成功，那么就递归匹配...

Posted by Jeza Chen on May 31, 2024

LeetCode 970 - 强整数

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

这种要求返回所有满足条件的结果题目，一般都使用递归+回溯的方法来解决，但此题因为只涉及两个数的枚举，因此仅需使用双重循环枚举两个数的幂，将其和加入到结果直至不满足条件即可。需要注意几点：由于题目要求返回的结果不能重复，因此需要使用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 984 - 不含AAA或BBB的字符串

LeetCode 971 - 翻转二叉树以匹配先序遍历

LeetCode 970 - 强整数

LeetCode 969 - 煎饼排序

LeetCode 962 - 最大宽度坡

LeetCode 959 - 由斜杠划分区域

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

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

LeetCode 954 - 二倍数对数组

LeetCode 951 - 翻转等价二叉树

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04