哈希表+滑动窗口，用哈希表保存不重复的元素，滑动窗口在遍历的时候，如果哈希表中存在重复元素，则分别调整哈希表和滑动窗口。 class Solution { public: /** * * @param arr int整型vector the array * @return int整型 */ int maxLength(vector<int>& arr) { int result=0; unordered_set<int> hash_set{}; int le...

贪心算法，当局部和sum大于0时，继续向前增加，并且与结果result比较；当局部和小于0时，让sum=0并且重新开始累加。 class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { int result=INT_MIN; int sum=0; for(int i=0;i<array.size();i++){ sum+=array[i]; if(sum>result) res...

首先需要一个反转链表的子函数，能够反转[left,right)并且返回反转之后的头结点。在以每k个节点反转链表的函数中，采用递归调用，每次都用head->next来接住递归返回的反转后的头结点。 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 *...

动态规划，在空间上并不需要保存全部的n个元素，只需要保存第i-1和第i-2个元素即可，每次累加原地更新。 class Solution { public: int jumpFloor(int number) { if(number==1) return 1; vector<int> dp(2,0); dp[0]=1; dp[1]=2; for(int i=2;i<number;++i){ int temp=dp[0]+dp[1]; dp[0]...

设置两个栈，一个用来入队，一个用来出队，再push的时候直接将元素压入stack1，再pop的时候如果stack2不为空，则直接pop，否则先将stack1中的元素全部弹出并压入stack2，然后从stack2弹出栈顶元素。 class Solution { public: void push(int node) { stack1.push(node); } int pop() { int result{-1}; if(stack2.empty()){ while(!stack1.empty())...

与合并有序数组的思路时一样的，先遍历两个链表共同的部分，再遍历其中某一个链表剩余的部分。 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* i=pHead1; ListNode* j=pHead2; Li...

一次遍历数组，遍历过程中，维持一个哈希表，用来保存值和下标，然后判断哈希表中是否有target-num[i]。 class Solution { public: /** * * @param numbers int整型vector * @param target int整型 * @return int整型vector */ vector<int> twoSum(vector<int>& numbers, int target) { vector<int> resu...

第K大数，用小顶堆实现，堆中的其他元素都大于堆顶元素。 class Solution { public: int findKth(vector<int> a, int n, int K) { priority_queue<int,vector<int>,greater<int>> min_heap{}; for(int i=0;i<K;i++) min_heap.push(a[i]); for(int i=K;i<n;i++){ if(a[i]>mi...

用队列实现，每一层的节点的个数就是que的元素的个数，没保存一个节点的值，同时将相应节点的左右子结点保存进去。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型vector<vector<>> */ vector<v...

topK问题，用一个大小为K的堆实现。 class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> result{}; if(k==0) return result; priority_queue<int,vector<int>,less<int>> max_heap{}; for(int i...

前、中、后序遍历 递归法。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 the root of binary tree * @return int整型vector<vector<>> */ void pre_order(TreeNode* root,...

双向链表+哈希表，哈希表的目的是为了实现O(1)的时间复杂度。另外要注意的就是在set和get过程中要同时维护双向链表和哈希表。 class Solution { public: /** * lru design * @param operators int整型vector<vector<>> the ops * @param k int整型 the k * @return int整型vector */ void set(int key,int value){ auto iter=k_it...

思路2：前后指针x和y，x向后，y向前，不符合顺序则交换。这样的代码比较简短。在递归左右部分的时候与partition版本不同。 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型vector 待排序的数组 ...

pivot是基准元素，按照基准元素将数组分为两部分（大于和小于），pos就是分割后正确的基准元素位置，在寻找pos位置的过程中进行交换。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型vector 待排序的数组 * @return int整型vector */ int partition(vector<int>& arr,int left,int right){ ...