JZX 轻语

LeetCode 2080 - 区间内查询数字的频率

一开始想到的是前缀和的思路，但由于题目并非是针对某种小数据集的查询（比如小写字母），而是任意数字，因此前缀和会占用大量的空间。因此，我们可以使用哈希表来记录每个数字所出现的位置，然后对于每次查询，使用二分查找来计算区间内的频率：对于查询区间[left, right]，我们先找到第一个大于等于left的位置l，然后找到第一个大于right的位置r，则出现的频率为r - l。手动实现二分...

Posted by Jeza Chen on February 18, 2025

LeetCode 1706 - 球会落何处

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

比较简单的模拟题，使用一个大小为m的数组记录每个小球当前所在的列（使用-1表示球已经被卡住），遍历每一轮（其实就是遍历每一行），分情况计算每一个小球的下一轮（行）的位置：如果所在的单元格为1（形状为\），且小球处于最后一列或者右边的单元格为-1（形状为/），则卡住；如果所在的单元格为-1（形状为/），且小球处于第一列或者右边的单元格为1（形状为\），...

Posted by Jeza Chen on February 15, 2025

LeetCode 2275 - 按位与结果大于零的最长组合

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

注意这里的组合并非是连续元素。可以得知，如果组合中的按位与结果不为0，说明这些元素至少有一个比特位全为1（只有这里才能保证按位与后至少有一个比特位不为0）。因此，我们可以统计每个元素的每个比特位的1的个数，然后取最大值即可。 class Solution { public: int largestCombination(vector<int>& candid...

Posted by Jeza Chen on January 12, 2025

LeetCode 3296 & 3297 - 统计重新排列后包含另一个字符串的子字符串数目

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

典型滑动窗口题目，统计word2的字符出现频次，以及word1当前窗口的字符出现频次，如果word1当前窗口每个字符的出现频次均大于等于word2的频次，则说明可以通过重新排列word1的滑动窗口内的字串得到word2，以及固定窗口左侧，一直延伸到word1的末尾的所有子串都满足题目要求。 II属于困难题，上述的做法会超时。改进点可以使用一个变量diff记录word1当前窗口还需要多少个字...

Posted by Jeza Chen on January 10, 2025

LeetCode 1366 - 通过投票对团队排名

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

排序题，考察点在于如何实现排序规则。首先使用字典（由于队伍最多为26个，可以使用列表模拟字典）统计每个队伍的得票情况，然后根据字典转换为列表，排序规则为：按照得票情况降序排列，如果得票情况相同，则按照队伍名称的字典序升序排列。最后将排序后的队伍名称连接起来即可。 C++的实现比较复杂些，首先统计得票情况，然后使用lambda表达式实现排序规则，最后将排序后的队伍名称连接起来即可。为了方...

Posted by Jeza Chen on December 29, 2024

LeetCode 198 & 213 - 打家劫舍I、II

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

这两道题目是LeetCode上的经典动态规划题目，都是关于打家劫舍的问题。对于第一道题目，可以定义一个数组dp，其中dp[i]表示在前i个房子中能偷到的最大金额。对于第i个房子，有两种选择：偷或者不偷。如果偷第i个房子，那么第i - 1个房子就不能偷，因此最大金额为dp[i - 2] + nums[i]；如果不偷第i个房子，那么最大金额取决于前i - 1个房子的结果，即dp[i - 1]。因...

Posted by Jeza Chen on October 7, 2024

LeetCode 2306 - 公司命名

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

这种Hard难度的题目，两两比对必然会超时，所以需要找到一种更高效的方法。可以发现以下规律：对于两个首字母x和y，如果以x为首字母存在一个(不包括x的)后缀，其没有以y作为首字母的单词，那么它可以和以y为首字母，且不存在以x为首字母的单词的任一后缀配对。使用哈希表，建立首字母和去掉首字母的后缀的映射，然后统计每个首字母对应的后缀集合。最后，可以使用集合运算，两两枚举首字母（记为x和y），计算...

Posted by Jeza Chen on September 25, 2024

LeetCode 2207 - 字符串中最多数目的子序列

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

枚举左维护右 + 贪心的思路，维护两个变量first_cnt和second_cnt分别统计前面字符串中pattern[0]和pattern[1]的出现次数，然后每遇到一次pattern[1]，就累加一次子序列次数(也就是前面的pattern[0]搭配当前的pattern[1])。最后，最优的插入点会出现在最前面或最后面其一：对于最前面，就插入pattern[0]，此时会和后面所有的patte...

Posted by Jeza Chen on September 24, 2024

LeetCode 2718 - 查询后矩阵的和

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

一开始的做法是先用哈希表记录每一行/每一列最后一次被修改的值以及修改”时间”(即操作的序号)，然后遍历矩阵，对于每一个元素，判断它的最终值来源于最后一次的行修改还是列修改，然后累加即可。这个做法的时间复杂度是O(n^2)，会超时。但是，我们可以逆向思维，从最后一次操作开始，逐步向前。如果某一行/列在后面被修改了(可使用哈希表记录)，就不再处理；否则，属于该行/列的最后一次修改，其影响的元...

Posted by Jeza Chen on September 10, 2024

LeetCode 3123 - 最短路径中的边

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

单源最短路径问题的变种，需要找到所有最短路径中的所有边。可使用Dijkstra算法求解，当选择下一个节点时，顺便记录下可能的前继节点和边的索引(即，如果该节点在先前已经被选取，当距离和最优距离相同，也要记录下这个路径)。最后根据前面的中间结果，回溯到根节点，对最优路径经过的边进行标记。 class Solution { public: using DistanceInfo = ...

Posted by Jeza Chen on August 31, 2024

LeetCode 2080 - 区间内查询数字的频率

LeetCode 1706 - 球会落何处

LeetCode 2275 - 按位与结果大于零的最长组合

LeetCode 3296 & 3297 - 统计重新排列后包含另一个字符串的子字符串数目

LeetCode 1366 - 通过投票对团队排名

LeetCode 198 & 213 - 打家劫舍I、II

LeetCode 2306 - 公司命名

LeetCode 2207 - 字符串中最多数目的子序列

LeetCode 2718 - 查询后矩阵的和

LeetCode 3123 - 最短路径中的边

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04