tonngw

分类

题解(12)

/ 注册

全部文章（共12篇）

题解 | #打家劫舍(二)#

动态规划相同的代码跑两遍，和（一）思路一样 f[i] 表示偷第 i 个房间，g[i] 表示不偷第 i 个房间这里分两种情况：不选起点，答案就是 res = max(f[n], g[n]) 最大值选起点，那么就不能选终点，所以答案就是 res = max(res, g[n]) cl...

C++ 动态规划

2022-03-08

0 358

题解 | #主持人调度#

优先队列（小根堆）：用于存储每个主持人主持的最后一场活动的结束时间，堆中元素个数就是主持人的个数将所有区间先按照开始时间从小到大排序，对于开始时间相等的按照结束时间排序遍历所有区间每次判断当前区间的开始时间是否大于堆顶的结束时间，如果大于等于，那么这场活动可以和堆顶这场活动使用同一个...

C++ 堆(优先队列)

2022-03-07

0 380

题解 | #最小覆盖子串#

滑动窗口算法 / 双指针算法定义两个哈希表，一个 hs 用于存储窗口 [i, j] 中字符出现的次数，一个 ht 用于存储字符串 t 中每个字符出现的次数。定义一个变量 cnt 用于记录窗口中包含字符串 t 的有效字符个数（多的不算）。先将 t 中每个字符和出现次数存入哈希表，然后遍历字符串 ...

C++ 双指针滑动窗口

2022-03-06

2 487

题解 | #N皇后问题#

回溯从第一行开始枚举皇后放在哪一列递归函数：dfs(int x) 如果当前行 x 等于 n 表示所有行的皇后都已经放完了，则方案数 + 1，将当前棋盘加入到答案中。枚举皇后应该放在 x 行的哪一列 y，y 从 0 枚举到 n - 1 判断：如果当前列 col[y]、当前对角线 dg...

C++ 回溯

2022-03-06

0 388

题解 | #环形数组的连续子数组最大和#

(动态规划) O(n)O(n)O(n) 这道题目是 NC19 连续子数组的最大和的升级版，增加了环形情况。分两种情况考虑问题：无环情况下：求出连续子数组的最大值 res 有环情况下：先求出无环情况下连续子数组的最小值 res2，然后用数组和 sum 减去最小值 res2 即为环形情况...

C++ 动态规划

2022-03-05

2 641

题解 | #缺失的第一个正整数#

解题思路 (数组,哈希表,原地交换) O(1)O(1)O(1) 如果没有空间限制的话，可以使用哈希表来解，先把所有元素放入哈希表 set 中，然后从 1 开始在哈希表中查询第一个未出现的正整数。要求使用常数空间的话想到在原数组原地交换，而我们关心的是正数，所以如果 nums[i] 是正数 >...

C++ 数组

2022-03-03

0 303

题解 | #二叉搜索树与双向链表#

因为二叉搜索树的中序遍历是有序的，所以选择中序遍历二叉树，在遍历的过程中将二叉搜索树转换为双向链表。使用一个指针 pre 指向当前遍历节点的前一个节点。关键的三步操作前一个节点 pre 的 right 指向当前节点（注意 pre 不能为空）pre->right = cur 当前节点...

C++ 双向链表二叉树二叉搜索树

2022-03-02

0 306

题解 | #滑动窗口的最大值#

窗口滑动的过程中需要队尾进队和队头出队，所以定义一个双端队列 deque 比较方便 for (i) 判断窗口的合法性更新队列中滑动窗口的最大值，如果当前元素大于队尾元素，那么在当前窗口内的最大值就是当前元素，所以弹出队尾，直到遇到队列为空或者条件不成立为止将当前下标入队如果达到...

C++ 滑动窗口单调队列队列

2022-03-02

0 325

题解 | #数组中的逆序对#

递归排序求逆序对 mergeSort() 函数有两个作用：归并排序：拆分 -> 通过临时数组 tmp 排序 -> 将排序后的结果 tmp 放回原数组(tmp 从 0 开始将其放到原数组 data 从 l 开始到 r) 返回值就是区间内 [l, r] 逆序对的数量什么时候形成逆序对...

C++ 归并排序

2022-03-01

0 302

题解 | #删除有序链表中重复的元素-II#

和删除有序链表中重复的元素-I 的思路是类似的，这道题目是将重复出现元素全部删掉（包括自己），那么就需要存储第一个重复节点前一个位置指针 p 用于删除。用 a 指针遍历链表，b = a->next 只要 a 和 a->next 不为空则进行循环，b = a->next 如果 ...

C++ 链表

2022-02-28

0 278