JZX 轻语

LeetCode 1357 - 每隔 n 个顾客打折

很简单的哈希表应用题，使用一个哈希表记录商品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 1441 - 用栈操作构建数组

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

根据栈后进先出的特点，不难得知栈内的元素必定为递增序列，且对于栈中两个相邻的元素a和b，如果b - a > 1，那么a和b之间的元素（已经被弹出了）必定是在bPush前，发生了b - a - 1次Push和Pop操作（即这些中间的元素进栈后又出栈了，然后b入栈前，栈顶元素为a）。因此，我们可以使用prev记录上一个元素(初始值可为0)，然后遍历target数组，对于每个元素num，如果...

Posted by Jeza Chen on August 22, 2024

LeetCode 3152 - 特殊数组 II

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

一开始的想法是：先从左到右遍历数组，将不满足nums[i] % 2 != nums[i + 1] % 2的下标存入invalid_inx_vec；然后对于每个查询，使用二分法找到from和to之间的第一个不满足条件的下标，如果存在则返回false，否则返回true。这种做法的时间复杂度为O(nlogn)。后面参考了官方题解，发现可以使用动态规划的方法，时间复杂度为O(n)：使用dp[i]...

Posted by Jeza Chen on August 14, 2024

LeetCode 3192 - 使二进制数组全部等于 1 的最少操作次数 II

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

有两种做法：第一种则是动态规划，记dp[i][j](其中j = 0, 1)为数组后i个元素构成的子数组(只考虑这i个元素，不考虑前面的翻转影响)翻转为j的最少次数，则如果nums[i] == j，则dp[i][j] = dp[i - 1][j]；否则dp[i][j] = dp[i - 1][1 - j] + 1。最后返回min(dp[n][0], dp[n][1])。第二种做法，则是基于...

Posted by Jeza Chen on August 13, 2024

LeetCode 1357 - 每隔 n 个顾客打折

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

LeetCode 690 - 员工的重要性

LeetCode 1444 - 切披萨的方案数

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

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

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

LeetCode 1441 - 用栈操作构建数组

LeetCode 3152 - 特殊数组 II

LeetCode 3192 - 使二进制数组全部等于 1 的最少操作次数 II

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04