JZX 轻语

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

动态规划题目，使用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 1357 - 每隔 n 个顾客打折

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

很简单的哈希表应用题，使用一个哈希表记录商品id和价格的映射关系，然后每次调用getBill计算账单时，累加商品价格，如果当前是第n个顾客，那么就打折。 C++的做法： class Cashier { public: Cashier(int n, int discount, vector<int>& products, vector<int>&...

Posted by Jeza Chen on August 30, 2024

LeetCode 1353 - 最多可以参加的会议数目

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

会议安排问题往往都能尝试使用贪心解决。考虑以下策略：首先按开始时间排序，然后每天选择有效的会议中结束时间最早的那个会议参加。所谓的有效会议是指开始时间小于等于当前时间的会议。为了实现这个策略，我们可以使用一个小顶堆，每次将已经开始的有效会议加入堆中，然后从堆中取出结束时间最早的会议参加。如果实现时间的推进呢？我们可以使用一个cur_time变量记录当前时间，初始值为第一个会议的开始时...

Posted by Jeza Chen on August 30, 2024

LeetCode 690 - 员工的重要性

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

挺简单的一个问题，首先使用一个哈希表记录员工的id和Employee对象的映射关系，然后使用BFS遍历员工的下属，累加重要性即可。 C++的做法： /* // Definition for Employee. class Employee { public: int id; int importance; vector<int> subordina...

Posted by Jeza Chen on August 26, 2024

LeetCode 1444 - 切披萨的方案数

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

一开始想复杂了，以为切后的两片都能再切，其实只能继续切右边/下边的那块(这意味着不用记录剩下的长宽，只要记录下一切的起始点就行，因为能继续切的部分处于原披萨的右下角)，另一块则需要保证有苹果。因此可以使用递归+记忆化搜索解决：记dp(r, c, remain)为从(r, c)开始，剩余remain次切割的方案数：如果remain == 0，则只需判断剩下的那块有没有苹果即...

Posted by Jeza Chen on August 24, 2024

LeetCode 3133 - 数组最后一个元素的最小值

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

一个想起来挺复杂，但想出来后实现挺简单的题目。由于要求数组内所有元素按位AND之后的值为x，这意味着，x每个为1的位，数组中每个元素的对应位也都要为1。因此，我们可以按照以下方式构造一个递增数组：第一个元素除了x中为1的位之外，其他位都为0，第二个元素其他位中后两位为10，第三个元素其他位中后两位为11，第四个元素其他位中后三位为100，以此类推。这样构造的数组，其最后一个元素的值就是返回值...

Posted by Jeza Chen on August 22, 2024

LeetCode 1443 - 收集树上所有苹果的最少时间

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

不难得知，如果一个子树中没有苹果可摘，那么就没必要经过；否则，进去和出来都要花费2个单位时间(指的是进去和离开这个子树的用时，不包括内部的采摘时间)。因此，我们可以使用DFS进行后序遍历，递归计算每个子树所需的采摘时间。如果子树中至少一个子树有苹果可摘(即返回值不为0)，或者当前子树的根节点有苹果，则消耗时间为2 + 所有子树的采摘时间；否则，消耗时间为0。最后，返回从根节点出发的总采摘时间...

Posted by Jeza Chen on August 22, 2024

LeetCode 1442 - 形成两个异或相等数组的三元组数目

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

不难得知，对于满足条件的三元组(i,j,k)，由于arr[i..j-1]的异或结果a等于arr[j..k]的异或结果a，那么a和b的异或结果为0，换句话说，子数组arr[i..k]所有的元素异或结果为0。反过来思考，如果某个长度为l的子数组中，所有元素异或的结果为0，那么该子数组中可以构造l - 1个满足条件的三元组。因此，题目转化为寻找所有元素异或结果为0的子数组，并计算其长度l，然后累加...

Posted by Jeza Chen on August 22, 2024

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

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

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

LeetCode 1357 - 每隔 n 个顾客打折

LeetCode 1353 - 最多可以参加的会议数目

LeetCode 690 - 员工的重要性

LeetCode 1444 - 切披萨的方案数

LeetCode 3133 - 数组最后一个元素的最小值

LeetCode 1443 - 收集树上所有苹果的最少时间

LeetCode 1442 - 形成两个异或相等数组的三元组数目

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04