JZX 轻语

LeetCode 937 - 重新排列日志文件

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

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 901 - 股票价格跨度

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

本质问题就是对于每个元素，求解左边第一个比其大的元素下标，此时两个下标的跨度即所需结果。此类问题(1. 对于每个子问题(数组的每个元素)，求解元素单侧比它大/小的第一个元素; 2. 如果维护子问题的结果)，均可以使用单调栈来求解。 class StockSpanner: def __init__(self): self._stack = [] # typin...

Posted by Jeza Chen on May 22, 2024

LeetCode 2225 - 找出输掉零场或一场比赛的玩家

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

使用哈希表记录每个玩家的负场次数即可，然后再有序遍历(避免结果数组需要排序)哈希表的键输出即可。由于有些玩家从来没输过，如果哈希表仅保存负者的数据是不够的，因为不清楚到底有几个玩家，所以遍历比赛数据时，如果赢家没有在哈希表时，则显式将其初始化为0。 class Solution: def findWinners(self, matches: List[List[int]])...

Posted by Jeza Chen on May 22, 2024

LeetCode 893 - 子数组按位或操作

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

对于这种子数组的特征问题，一般来说可以考虑前缀和思路。但由于or操作并不满足差分性质，所以需要使用一个集合ans来维护所有的非重复结果，以及一个数据结构last来存储以上一个元素结尾的所有子数组的按位或结果，然后再将last中所有的结果和当前的元素再异或一次，放进ans中，并更新last(还需要往后追加当前元素，作为长度为1的子数组)。一开始使用的是列表，但随着数组的变大，循环的量会逐渐变多...

Posted by Jeza Chen on May 21, 2024

LeetCode 937 - 重新排列日志文件

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

LeetCode 934 - 最短的桥

LeetCode 932 - 漂亮数组

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

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

LeetCode 904 - 水果成篮

LeetCode 901 - 股票价格跨度

LeetCode 2225 - 找出输掉零场或一场比赛的玩家

LeetCode 893 - 子数组按位或操作

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04