type
status
date
slug
summary
tags
category
icon
password
🤔 146. LRU 缓存 - 力扣（LeetCode）
使用双向链表加哈希表（字典）进行操作。get时将删尾插头，put时检查长度，删尾插头。
729. 我的日程安排表 I
已解答
中等
相关标签
相关企业
提示
实现一个
MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。
日程可以用一对整数
start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end 。实现
MyCalendar 类：MyCalendar()初始化日历对象。
boolean book(int start, int end)如果可以将日程安排成功添加到日历中而不会导致重复预订，返回true。否则，返回false并且不要将该日程安排添加到日历中。
示例：
提示：
0 <= start < end <= 109
- 每个测试用例，调用
book方法的次数最多不超过1000次。
与排序无关！
554. 砖墙
已解答
中等
相关标签
相关企业
你的面前有一堵矩形的、由
n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
给你一个二维数组
wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。示例 1：
示例 2：
由于砖墙是一面矩形，所以对于任意一条垂线，其穿过的砖块数量加上从边缘经过的砖块数量之和是一个定值，即砖墙的高度。
因此，问题可以转换成求「垂线穿过的砖块边缘数量的最大值」，用砖墙的高度减去该最大值即为答案。
虽然垂线在每行至多只能通过一个砖块边缘，但是每行的砖块边缘也各不相同，因此我们需要用哈希表统计所有符合要求的砖块边缘的数量。
注意到题目要求垂线不能通过砖墙的两个垂直边缘，所以砖墙两侧的边缘不应当被统计。因此，我们只需要统计每行砖块中除了最右侧的砖块以外的其他砖块的右边缘即可。
具体地，我们遍历砖墙的每一行，对于当前行，我们从左到右地扫描每一块砖，使用一个累加器记录当前砖的右侧边缘到砖墙的左边缘的距离，将除了最右侧的砖块以外的其他砖块的右边缘到砖墙的左边缘的距离加入到哈希表中。最后我们遍历该哈希表，找到出现次数最多的砖块边缘，这就是垂线经过的砖块边缘，而该垂线经过的砖块数量即为砖墙的高度减去该垂线经过的砖块边缘的数量。
知识点：
C++中的
- 引用声明：
&表示我们想要引用容器中的元素，而不是复制它们。这意味着在循环体内对元素所做的任何修改都会反映到原始容器中。
- auto关键字：
auto关键字用于自动推断变量的类型。在这个例子中，它将根据cnt容器中的元素类型来推断c的类型。
- 结构化绑定：
for(auto& [_, c] : cnt)使用了C++17引入的结构化绑定（structured binding）特性。这允许我们从元组、对或pair类型的元素中解构出多个变量。
- 下划线
_：下划线_在这里用作一个占位符，表示我们不打算使用结构化绑定中的第一部分。在这个例子中，cnt可能是一个std::map或std::unordered_map，其键值对类型为pair<const KeyType, ValueType>。我们使用_来忽略键（KeyType），只绑定值（ValueType）到变量c。
- 引用绑定到const：由于使用了
auto&，如果cnt中的元素是const的，那么c也会是const的引用，这意味着你不能通过c修改元素的值。
- 在该代码中不加&也是对的
136. 只出现一次的数字
已解答
简单
相关标签
相关企业
提示
给你一个 非空 整数数组
nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
示例 2 ：
示例 3 ：
提示：
1 <= nums.length <= 3 * 104
3 * 104 <= nums[i] <= 3 * 104
- 除了某个元素只出现一次以外，其余每个元素均出现两次。
缺失的第一个正整数_牛客题霸_牛客网 (nowcoder.com)
描述
给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数
进阶： 空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
数据范围:
−231≤nums[i]≤231−1−231≤nums[i]≤231−1
0≤len(nums)≤5∗1050≤len(nums)≤5∗105
示例1
输入：
[1,0,2]复制返回值：
3
复制示例2
输入：
[-2,3,4,1,5]复制返回值：
2
复制示例3
输入：
[4,5,6,8,9]复制返回值：
1第一个只出现一次的字符_牛客题霸_牛客网 (nowcoder.com)
描述
在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
数据范围：0≤n≤100000≤n≤10000，且字符串只有字母组成。
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
示例1
输入：
"google"复制返回值：
4复制示例2
输入：
"aa"复制返回值：
-13. 无重复字符的最长子串 - 力扣（LeetCode）
给定一个字符串
s ，请你找出其中不含有重复字符的 最长子串
的长度。
示例 1:
示例 2:
示例 3:
提示：
0 <= s.length <= 5 * 104
s由英文字母、数字、符号和空格组成
滑动窗口，用散列表记录下标
128. 最长连续序列
已解答
中等
相关标签
相关企业
给定一个未排序的整数数组
nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为
O(n) 的算法解决此问题。示例 1：
示例 2：
提示：
0 <= nums.length <= 105
109 <= nums[i] <= 109
- 作者:VON
- 链接:https://baisihan.asia/article/52eed6ed-721e-4f2c-bc68-08b79763696b
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。