JZX 轻语

LeetCode 986 - 区间列表的交集

双指针典型题目。使用两个指针i和j分别指向A和B的区间，然后根据两个区间的交集(两个区间的最大左端点和最小右端点)来更新答案。指针的移动规则是：如果A区间的右端点小于等于B区间的右端点(A区间位于B左侧，说明A的下一个区间可能和B当前区间还是会有交集)，那么A区间的指针i向右移动；否则B区间的指针j向右移动。 class Solution: def intervalInters...

Posted by Jeza Chen on May 31, 2024

LeetCode 985 - 查询后的偶数和

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

挺简单的数组题目，首先累加一下数组中的偶数和，然后对每个查询进行偶数和的更新即可：如果查询前的数为偶数，那么需要减去原数值，如果查询后的数为偶数，那么需要加上新数值。 class Solution: def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]: ...

Posted by Jeza Chen on May 31, 2024

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

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

很容易想到贪心的做法，一种可行的构造是：首先通过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 986 - 区间列表的交集

LeetCode 985 - 查询后的偶数和

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

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

LeetCode 970 - 强整数

LeetCode 969 - 煎饼排序

LeetCode 962 - 最大宽度坡

LeetCode 959 - 由斜杠划分区域

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

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

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04