JZX 轻语

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

该题目正向构造比较困难，可以考虑逆向思考，模拟分析结果数组中按照题目要求的那样弹出的下标顺序(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 1673 - 找出最具竞争力的子序列

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

由题目得知，如果子序列前面的值越小，则越具竞争力，即尽可能找到较小的值放在前面。本质就是找到一个子数组，其中第一个元素为nums[0..n-k]中的最小值，第二个元素为nums[第一个元素位置+1..min(n-1, n-k+1)]中的最小值，第三个元素及后面亦然(注意区间的右侧，我们不能直接取最小值，否则即便追加后面所有的元素都无法构成长度为k的结果)。朴素的想法可以使用一个堆，先维护nu...

Posted by Jeza Chen on May 24, 2024

LeetCode 904 - 水果成篮

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

滑动窗口题目，其中窗口里面所涵盖的水果满足成篮要求。窗口右侧首先移向至当前满足要求的最大下标，当无法延展右侧时，左侧则滑动至窗口(刚好)只有一种水果的最小下标，再延展右侧，直至右侧移动到数组最右端。结果则来源于上述过程窗口的最大尺寸。在实现的过程中，我将传入的数组fruits充当为栈，并从右到左开始遍历数组，且没有显式地使用滑动窗口相关指针。使用一个集合curr_set记录当前窗口的...

Posted by Jeza Chen on May 22, 2024

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

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

LeetCode 922 - 按奇偶排序数组 II

LeetCode 937 - 重新排列日志文件

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

LeetCode 934 - 最短的桥

LeetCode 932 - 漂亮数组

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

LeetCode 1673 - 找出最具竞争力的子序列

LeetCode 904 - 水果成篮

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04