方法：双指针+排序 具体步骤：对数组进行排序， 便于后续的查找遍历数组，得到第一个数字后，将问题转换为寻找两个数字之和为第一个数字相反数的问题其中要注意重复的数字要去除。时间复杂度：o(n2)。排序需要o(logn)，遍历需要o(n2)。空间复杂度：o(1) class Solution { public: vector<vector<int> > threeSum(vector<int>& num) { vector<vector<int> > res; int n = num.s...

方法一：原地哈希具体做法：step 1：我们可以先遍历数组将所有的负数都修改成n+1。step 2：然后再遍历数组，每当遇到一个元素绝对值不超过n时，则表示这个元素是1～n中出现的元素，我们可以将这个数值对应的下标里的元素改成负数，相当于每个出现过的正整数，我们把与它值相等的下标都指向一个负数，这就是类似哈希表的实现原理的操作。step 3：最后遍历数组的时候碰到的第一个非负数，它的下标就是没有出现的第一个正整数，因为它在之前的过程中没有被修改，说明它这个下标对应的正整数没有出现过。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: int ...

方法：异或运算根据异或运算的性质，如果一个数组只有出现一次的数字，那么数组中所有的数字通过异或运算最终的结果就是该数字。如果数组中有两个只出现一次的数字（target1、target2），我们首先就需要将targer1和target2区分开来。数组全部进行异或运算后最终的结果为target1 ^ target2，通过这个结果我们可以反推出target1和target2在哪些位上是不一致的，这样就可以将数组分为两类，分别进行异或运算得到target1和target2。时间复杂度：o(n)。需要遍历数组空间复杂度：o(1)。无额外辅助空间。 class Solution { public: ...

方法：个数统计具体做法：初始化：候选人cond = -1， 候选人的投票次数cnt = 0遍历数组，如果cnt=0， 表示没有候选人，则选取当前数为候选人，++cnt否则，如果cnt > 0, 表示有候选人，如果当前数=cond，则++cnt，否则--cnt直到数组遍历完毕，最后检查cond是否为众数时间复杂度：o(n)。遍历数组需要时间o(n)。空间复杂度：o(1)。不需要额外空间。 class Solution { public: int MoreThanHalfNum_Solution(vector<int>& numbers) { in...

方法：哈希表具体步骤：从头开始遍历数组，判断目标值减去当前遍历值是否能在哈希表中找到；如果能找到则返回哈希表中的value和当前遍历的数组序号；如果没找到，则将该键值存入哈希表，继续往下遍历数组。时间复杂度：o(n)。遍历数组需要时间o(n)，哈希表查找时间复杂度为o(1)。空间复杂度：o(n)。创建哈希表需要空间o(n)。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param numbers int整型vector * @p...

方法：双向队列双向队列就是一种特殊的队列，双向队列两边，即头部和尾部都可以进行插入元素和删除元素的操作，但是也只能插入到最尾部或者最头部，每次也只能取出头部元素或者尾部元素后才能取出里面的元素。具体做法：step 1：维护一个双向队列，用来存储数列的下标。step 2：首先检查窗口大小与数组大小。step 3：先遍历第一个窗口，如果即将进入队列的下标的值大于队列后方的值，依次将小于的值拿出来去掉，再加入，保证 队列是递增序。step 4：遍历后续窗口，每次取出队首就是最大值，如果某个下标已经过了窗口，则从队列前方将其弹出。step 5：对于之后的窗口，重复...

方法：栈+递归该题的难点在于如何处理括号和运算符的优先级。问题一，如何处理括号：当遇到括号‘（’，进行递归处理，直到括号被处理成数字；这样表达式就是数字之间的运算，而没有括号。问题二，如何处理运算符的优先级：当遇到加法运算符的时候，将后面的数字直接压入栈中； 当遇到减法运算法时，将后面的数字取相反数压入栈中； 当遇到乘法运算符时，直接进行处理，并将乘法运算后的数字压入栈中。这样栈中就只...

方法：插入排序具体步骤：1、当数组为空时，直接插入数据；当数组不为空时，遍历数组寻找合适的位置进行插入；这样得到的数组就行排序好的。 2、获取数据流的中位数。时间复杂度：o(n)。空间复杂度：o(n)。 class Solution { public: vector<int> res; void Insert(int num) { //数组为空时，直接插入数据 if (res.empty()) res.push_back(num); //数组不为空时，需要找对位置插入数据 ...

方法一：快排此题很容易想到，先将数组进行从大到小的排序，第K大的数字就是排序数组的第K个元素，可以使用快排进行排序。时间复杂度：o(nlogn)。空间复杂度：o(n)。递归深度。 class Solution { public: void quick_sort(vector<int>& a, int start, int end) { if (start >= end) return; int i = start; int j = end; //基准值设为数组第一个元...

方法一：排序将输入的数组进行排序，取前 K个值即可时间复杂度：O(nlongk)空间复杂度：O(1) class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) { vector<int> res; //特殊情况处理 if (k == 0 || k > input.size()) return res; //排序 sort...

方法：辅助栈 借助辅助栈，当遇到'(','[','{'这三种字符的时候则让对应的匹配字符入栈(分别对应')',']','}')，当出现的字符不是'(','[','{'这三种字符时，则先判断栈是否为空或者当前字符是否与栈顶元素一样，当栈空或者当前字符与栈顶字符不一样时，则括号序列不合法，直接返回；否则栈顶元素出栈。遍历字符串直到所有元素遍历完成。最后判断栈是否为空，不为空则括号序列不合法；否则为合法序列。 class Solution { private: stack<char> res; public: bool isValid(string s) {...

具体做法：1、构建两个栈，用于实现查找栈的最小值；2、栈stack1按正常压入元素；栈stack2用来实现获取栈的最小值：当stack2为空时，将元素压入栈；如果输入的元素大于stack2栈顶的元素，那么stack2就压入与栈顶相同的元素（因为此时栈中的最小元素依然是栈顶元素）；当输入元素不大于栈顶元素时，将输入元素压入栈stack2，因为此时栈的最小元素发生了变化。 class Solution { private: stack<int> stack1; stack<int> stack2; public: void push(int ...

具体做法：1、将其中一个栈stack1作为元素插入使用；2、当需要删除元素时，将stack1的元素从栈顶压入到stack2，这时stack2的栈顶元素就是队列的第一个元素；3、再将stack2的元素从栈顶压入到stack2，以便后续插入元素时使用。 class Solution { public: void push(int node) { stack1.push(node); } int pop() { while (!stack1.empty()) { stack2.push(stack1.top());...

方法：递归1、利用递归得到二叉树的前序遍历；2、将前序遍历转换为二叉树。代码中有很多细节需要处理：string和char类型之间的转换，字符与数字之间的转换。时间复杂度：o(n)空间复杂度：o(n) class Solution { public: //前序遍历 void SerializeFunction(TreeNode* root, string& str) { //空结点处理 if (root == nullptr) { str += '#'; return; }...