1、解题思路为了实现LRU缓存，我们需要满足以下条件：快速访问：get和set操作的时间复杂度为O(1)。记录访问顺序：需要快速找到并更新最近使用的key，同时移除最久未使用的key。数据结构选择：哈希表（Hash Map）：用于快速查找key对应的value。双向链表（Doubly Linked List）：用于维护key的访问顺序，最近使用的放在头部，最久未使用的放在尾部。2、代码实现C++ #include <list> #include <string> #include <unordered_map> #include <utility&gt...

1、解题思路直接旋转法： 创建一个新的 NxN 矩阵。遍历原矩阵，将原矩阵的第 i 行变为新矩阵的第 N-i-1 列。原地旋转法（进阶要求）： 先对矩阵进行转置（行列互换）。然后对每一行进行反转。原地旋转法满足空间复杂度 O(1) 的要求，因为不需要额外的存储空间。2、代码实现C++ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param mat int整型vector<vector<>> * @param n int...

1、解题思路初始化边界：设定矩阵的上下左右边界（top, bottom, left, right）。按层遍历 ： 从左到右遍历上层边界（top层）。从上到下遍历右层边界（right层）。从右到左遍历下层边界（bottom层）。从下到上遍历左层边界（left层）。更新边界：每完成一层遍历后，收缩相应的边界。终止条件：当所有边界相遇时，遍历完成。这种方法确保我们按照螺旋顺序访问矩阵中的所有元素。2、代码实现C++ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 *...

1、解题思路三次反转法： 将数组分成两部分：前 n-M 个元素和后 M 个元素。反转整个数组。反转前 M 个元素。反转后 n-M 个元素。这样可以得到循环右移 M 个位置后的数组。直接移动法： 逐个将元素移动到目标位置，但这种方法移动次数较多，效率较低。显然，三次反转法是最优的，因为它只需要进行三次反转操作，时间复杂度为 O(n)，空间复杂度为O(1)。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 旋转数组 * @param n int整型 数组长度 * @param m in...

1、解题思路这是一个典型的区间调度问题，可以通过贪心算法来解决。具体步骤如下：排序活动：首先将所有的活动按照结束时间进行排序。如果结束时间相同，可以按开始时间排序。贪心选择 ：使用一个优先队列（最小堆）来记录当前正在进行活动的结束时间。 遍历排序后的活动，对于每个活动，检查堆顶的结束时间是否小于等于当前活动的开始时间。如果是，则可以将该主持人用于当前活动，更新堆顶的结束时间。如果不是，则需要新增一个主持人，将当前活动的结束时间加入堆中。结果：最终堆的大小即为所需主持人的最小数量。这种方法确保我们尽可能多地复用主持人，从而最小化主持人的总数。2、代码实现C++ #include <queu...

1、解题思路这是一个典型的贪心算法问题，可以通过两次遍历数组来解决：从左到右遍历 ：确保每个孩子与其左侧相邻孩子满足糖果分配规则。 如果当前孩子的得分比左侧高，则当前孩子的糖果数至少为左侧孩子的糖果数加1。否则，当前孩子的糖果数至少为1（初始值）。从右到左遍历 ：确保每个孩子与其右侧相邻孩子满足糖果分配规则。 如果当前孩子的得分比右侧高，则当前孩子的糖果数至少为右侧孩子的糖果数加1（但不要减少当前已分配的糖果数）。否则，保持当前糖果数不变。求和：将两次遍历后的糖果数取最大值，然后求和。这种方法确保每个孩子既满足左侧规则又满足右侧规则，同时使用最少糖果。2、代码实现C++ #include &l...

1、解题思路双指针法： 使用两个指针，一个从左向右移动（left），一个从右向左移动（right）。维护两个变量，left_max和right_max，分别表示从左到右和从右到左遍历时的最大高度。每次移动高度较小的指针，因为较小的高度决定了当前能够接住的雨水量。计算当前柱子的接水量：min(left_max, right_max) - current_height。动态规划法： 预计算每个柱子左边的最大高度和右边的最大高度。对于每个柱子，接水量为min(left_max[i], right_max[i]) - height[i]。这种方法需要额外的空间存储left_max和right_max数...

1、解题思路暴力法：遍历所有可能的两根高度组合，计算每对组合的容积，并记录最大容积。时间复杂度为 O(n^2^)，对于 n=10^5^ 来说，这种方法显然不可行。双指针法：使用两个指针，一个指向数组的开始（left），一个指向数组的末尾（right）。计算当前指针所指向的两根高度形成的容积，并更新最大容积。移动指针的策略：移动高度较小的指针，因为这样可以保留较高的高度，有可能获得更大的容积。时间复杂度为O(n)，空间复杂度为O(1)。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * *...

1、解题思路滑动窗口法：使用双指针（left 和 right）表示当前窗口的左右边界。使用哈希表记录窗口中各元素的最后一次出现的位置。当遇到重复元素时，移动 left 指针到重复元素的下一个位置。更新窗口的最大长度。复杂度分析：时间复杂度：O(n)，只需要遍历数组一次。空间复杂度：O(n)，哈希表最多存储所有元素的最后一次出现的位置。2、代码实现C++ #include <unordered_map> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param arr int整型v...

1、解题思路直接反转：遍历字符串，从最后一个字符到第一个字符依次取出，构建新的反转字符串。这种方法直观且易于实现。利用语言特性：一些语言提供了直接反转字符串的方法，可以简单调用。双指针法：使用两个指针分别指向字符串的首尾，交换字符并向中间移动，直到指针相遇。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 反转字符串 * @param str string字符串 * @return string字符串 */ string solve(string str) { // write c...

1、解题思路滑动窗口法：使用双指针（left 和 right）表示当前窗口的左右边界。扩展 right 指针，直到窗口包含 t 中的所有字符。收缩 left 指针，尽可能缩小窗口，同时保持窗口包含 t 中的所有字符。记录满足条件的最短子串。哈希表辅助：使用哈希表记录 t 中每个字符的出现次数。在滑动窗口过程中，维护另一个哈希表，记录当前窗口中各字符的出现次数。判断当前窗口是否满足包含 t 中所有字符的条件。2、代码实现C++ #include <climits> #include <unordered_map> class Solution { public: /** ...

1、解题思路排序区间 ：首先将区间按照起点升序排列，这样便于后续的合并操作。合并区间 ：使用一个结果列表来存储合并后的区间。遍历排序后的区间列表，比较当前区间与结果列表中最后一个区间是否有重叠。如果有重叠，合并它们；如果没有重叠，直接将当前区间加入结果列表。2、代码实现C++ /** * struct Interval { * int start; * int end; * Interval(int s, int e) : start(start), end(e) {} * }; */ #include <vector> class Solution { public: /** *...

1、解题思路双指针法： 使用两个指针，一个从字符串的头部开始（左指针），一个从字符串的尾部开始（右指针）。比较两个指针所指的字符是否相同。如果相同，则移动两个指针向中间靠拢；如果不同，则直接返回false。当左指针超过或等于右指针时，说明所有对应的字符都相同，返回true。优化： 由于字符串仅由小写字母组成，可以直接比较字符，无需额外处理。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param str string字符串 待判断的字符串 * @return bool布尔...

1、解题思路合并两个有序数组 ：由于数组 A 和 B 都是有序的，可以利用双指针的方法，分别从数组 A 和 B 的末尾开始比较，将较大的元素放到数组 A 的末尾。处理剩余元素 ：如果数组 B 还有剩余元素，直接将其复制到数组 A 的前面。如果数组 A 还有剩余元素，由于数组 A 本身是有序的，不需要额外处理。2、代码实现C++ class Solution { public: void merge(int A[], int m, int B[], int n) { int i = m - 1; // 数组 A 的末尾指针 int j = n - 1; // 数组 B 的末尾指针 int k =...