JZX 轻语

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

典型滑动窗口题目，统计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 3122 - 使矩阵满足条件的最少操作次数

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

动态规划题目，使用dp[i][j]表示将第i列都改为数字j后，前i列满足条件的最少操作次数。那么状态转移方程为：dp[i][j] = min(dp[i-1][k] + m - cnt[i][j])，其中k枚举前一列可能的数字(且需要k != i)，m表示矩阵的行数，cnt[i][j]表示第i列数字j的个数。为了节省空间，我们可以使用滚动数组优化空间复杂度。 class Solution...

Posted by Jeza Chen on August 31, 2024

LeetCode 3120&3121 - 统计特殊字母的数量

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

第一题比较简单，使用两个布尔数组分别记录小写字母和大写字母是否出现过。然后统计大小写都出现过的字母的数量即可。第二题稍微复杂一点，需要用两个整型数组记录每个字母最后一个小写出现的位置和第一个大写出现的位置。然后遍历字母，如果某个字母的第一次大写出现位置在最后一次小写出现位置之后，那么这个字母就是特殊字母。第一题做法： class Solution { public: i...

Posted by Jeza Chen on August 31, 2024

LeetCode 3153 - 所有数对中数位差之和

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

枚举右维护左的做法(有点像前缀和)，使用digits数组维护当前位置左边所有数字各个位中的数字出现次数，具体而言，digits[i][j]表示左侧所有数字中，第i位数字为j的个数。遍历数组nums，对于每个数字，遍历每一位，统计左侧所有数字中，不同于当前数字该位的数字出现次数，累加到答案中。 C++的做法： class Solution { public: using ll ...

Posted by Jeza Chen on August 30, 2024

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

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

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

LeetCode 2306 - 公司命名

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

LeetCode 2718 - 查询后矩阵的和

LeetCode 3123 - 最短路径中的边

LeetCode 3122 - 使矩阵满足条件的最少操作次数

LeetCode 3120&3121 - 统计特殊字母的数量

LeetCode 3153 - 所有数对中数位差之和

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04