1、解题思路回溯法： 使用回溯法生成所有可能的排列。通过交换元素的位置来生成不同的排列。使用标记数组 visited 来记录哪些元素已经被使用过，避免重复使用。时间复杂度：O(n!)，空间复杂度：O(n!)（存储结果的空间）。递归法： 递归地生成所有可能的排列。每次选择一个未被使用的元素，将其加入当前排列，然后继续递归。使用标记数组 visited 来记录哪些元素已经被使用过。时间复杂度：O(n!)，空间复杂度：O(n!)（存储结果的空间）。库函数法： 使用语言内置的库函数（如 Python 的 itertools.permutations）直接生成所有排列。简单但不符合面试要求。2、代码实现...

1、解题思路排序法： 首先将数组排序，这样可以方便地跳过重复元素。固定一个元素 nums[i]，然后在剩下的数组中使用双指针法寻找 nums[left] 和 nums[right]，使得 nums[i] + nums[left] + nums[right] = 0。为了避免重复，当发现相同的元素时，跳过它们。时间复杂度：O(n^2)，空间复杂度：O(1)（不考虑结果存储空间）。哈希表法： 使用哈希表来存储所有可能的二元组，然后遍历数组寻找第三个元素。这种方法需要额外的空间来存储中间结果，且时间复杂度较高。时间复杂度：O(n^2)，空间复杂度：O(n)。不符合题目对空间复杂度的要求。暴力法： 三...

1、解题思路哈希表法（不符合空间要求）：使用哈希表记录所有出现的数字。从1开始逐个检查，直到找到第一个不在哈希表中的正整数。时间复杂度：O(n)，空间复杂度：O(n)。原地哈希法：利用数组本身作为哈希表，将数字 x 放到索引 x-1 的位置。遍历数组，将每个数字放到正确的位置。再次遍历数组，找到第一个 nums[i] != i+1 的位置，返回 i+1。如果所有位置都正确，返回 n+1。时间复杂度：O(n)，空间复杂度：O(1)。标记法：首先将所有非正数和大于 n 的数标记为无效（例如设为 n+1）。遍历数组，将数字 x 对应的索引 x-1 的位置标记为负数。再次遍历数组，找到第一个正数的位置...

1、解题思路异或法：将所有数字进行异或，最终得到的结果是两个只出现一次的数字的异或结果。找到异或结果中的任意一个为1的位，该位可以将数组分成两部分，每部分各包含一个只出现一次的数字。对这两部分分别进行异或，得到两个只出现一次的数字。时间复杂度：O(n)，空间复杂度：O(1)。哈希表法：使用哈希表统计每个数字的出现次数。遍历哈希表，找到出现次数为1的数字。时间复杂度：O(n)，空间复杂度：O(n)。不符合题目对空间复杂度 O(1) 的要求。排序法：将数组排序，然后遍历数组找到只出现一次的数字。时间复杂度：O(nlogn)，空间复杂度：O(1)。不符合题目对时间复杂度 O(n) 的要求。2、代码实...

1、解题思路摩尔投票法：假设第一个数字为候选数字，计数器初始化为1。遍历数组，如果当前数字与候选数字相同，计数器加1；否则计数器减1。如果计数器减到0，更换候选数字为当前数字，并将计数器重置为1。最后剩下的候选数字即为所求。时间复杂度：O(n)，空间复杂度：O(1)。哈希表法：使用哈希表统计每个数字的出现次数。遍历哈希表，找到出现次数超过数组长度一半的数字。时间复杂度：O(n)，空间复杂度：O(n)。不符合题目对空间复杂度 O(1) 的要求。排序法：将数组排序，中间位置即为所求。时间复杂度：O(nlogn)，空间复杂度：O(1)（如果使用原地排序）。不符合题目对时间复杂度 O(n) 的要求。分...

1、解题思路哈希表法：使用哈希表存储每个数字及其对应的下标。遍历数组，对于每个数字 num，检查 target - num 是否存在于哈希表中。如果存在，返回这两个数的下标。时间复杂度：O(n)，空间复杂度：O(n)。排序与双指针法：先将数组排序，然后使用双指针从两端向中间遍历。如果两数之和等于 target，返回它们的下标。如果两数之和小于 target，移动左指针。如果两数之和大于 target，移动右指针。时间复杂度：O(nlogn)（排序），空间复杂度：O(n)（存储原始下标）。暴力法：双重循环遍历所有可能的数对，检查其和是否等于 target。时间复杂度：O(n^2)，空间复杂度：O...

1、解题思路栈的应用： 使用两个栈：nums 栈存储数字，ops 栈存储运算符和括号。遵循以下规则： 遇到数字时，提取完整的数字并压入 nums 栈。遇到左括号时，压入 ops 栈。遇到右括号时，弹出 ops 栈直到遇到左括号，计算括号内的表达式。遇到运算符时，根据优先级决定是否先计算栈中的部分表达式。运算符优先级： 乘法优先级高于加减法。遇到高优先级的运算符时，先计算栈中的部分表达式。计算顺序： 从左到右依次处理字符。遇到高优先级运算符时，先计算高优先级的部分。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直...

1、解题思路直接排序法： 每次调用 Insert() 方法时，将数值插入数组并保持数组有序。调用 GetMedian() 时，根据数组长度直接计算中位数。时间复杂度： 插入时间复杂度：O(n)（因为插入排序需要移动元素）。获取中位数时间复杂度：O(1)。空间复杂度：O(n)。堆（优先队列）优化： 使用两个堆： 一个大根堆（maxHeap）存储较小的半部分数值。一个小根堆（minHeap）存储较大的半部分数值。维护两个堆的大小关系： 如果两个堆的大小相等，中位数是两个堆顶的平均值。如果两个堆的大小相差1，中位数是较大堆的堆顶。时间复杂度： 插入时间复杂度：O(logn)（堆的插入操作）。获取中位...

1、解题思路排序法：直接对整个数组进行排序，然后取第 (n - k) 个元素（假设数组是升序排序）。时间复杂度为 O(nlogn)，空间复杂度为 O(1)（如果使用的是原地排序算法，如堆排序或快速排序）。快速选择（Quickselect）：类似于快速排序的分区思想，可以在平均 O(n) 时间内找到第 k 大的元素。由于题目要求时间复杂度为 O(nlogn)，且空间复杂度为 O(1)，因此使用排序法更为稳妥。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param a in...

1、解题思路排序法：直接对整个数组排序，然后取前 k 个元素。时间复杂度为 O(nlogn)，不满足题目要求的 O(nlogk)。堆（优先队列）：使用一个大根堆来维护当前最小的 k 个元素。遍历数组，将每个元素与堆顶（当前堆中的最大值）比较： 如果堆的大小小于 k，直接加入堆。如果当前元素小于堆顶，弹出堆顶并加入当前元素。最终堆中的元素即为最小的 k 个数。时间复杂度为 O(nlogk)，空间复杂度为 O(k)。快速选择（Quickselect）：类似于快速排序的分区思想，可以在平均 O(n) 时间内找到第 k 小的元素，然后输出前 k 个元素。最坏情况下时间复杂度为 O(n^2)，但题目要求...

1、解题思路暴力法：对于每个窗口，遍历窗口内的所有元素找出最大值。时间复杂度为 O(n*k)，其中 n 是数组长度，k 是窗口大小。这会超出时间限制。双端队列优化 ：使用一个双端队列（deque）来存储当前窗口中的可能成为最大值的元素索引。维护队列的单调性：队列中的元素索引对应数组中的值从大到小排列。遍历数组时：移除队列中不在当前窗口范围内的索引。移除队列中比当前元素小的索引（因为它们不可能成为后续窗口的最大值）。将当前元素索引加入队列。记录当前窗口的最大值（队列首元素对应的值）。2、代码实现C++ #include <deque> #include <vector> ...

1、解题思路栈的应用： 遍历字符串，遇到左括号 '(', '{', '[' 时，压入栈。遇到右括号 ')' , '}' , ']' 时，检查栈顶是否为对应的左括号： 如果是，弹出栈顶。如果不是，返回 false。遍历结束后，如果栈为空，返回 true；否则返回 false。边界条件： 空字符串视为合法。字符串长度为奇数时可直接返回 false。2、代码实现C++ #include <stack> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 *...

1、解题思路普通栈：直接使用一个栈来存储所有元素，但 min 操作需要遍历所有元素，时间复杂度为 O(n)，不符合题目要求。辅助栈：使用一个辅助栈来同步存储当前栈中的最小值。每次 push 操作时，辅助栈压入当前最小值；每次 pop 操作时，辅助栈同步弹出。这样 min 操作只需返回辅助栈的栈顶元素即可。2、代码实现C++ #include <stack> class Solution { public: void push(int value) { dataStack.push(value); // 压入主栈 // 压入辅助栈: 如果辅助栈为空或者新值 <= 当前最小值, ...

1、解题思路栈的特性：后进先出（LIFO）。队列的特性：先进先出（FIFO）。双栈实现队列 ：Push 操作：直接压入 stack1。Pop 操作 ：如果 stack2 为空，则将 stack1 中的所有元素依次弹出并压入 stack2，此时 stack2 的栈顶元素即为队列的头部元素。如果 stack2 不为空，则直接弹出 stack2 的栈顶元素。2、代码实现C++ class Solution { public: void push(int node) { stack1.push(node); } int pop() { if (stack2.empty()) { while (!sta...