//典型的双指针题。由力扣上的*********************************************题变种而来。力扣那题只是要移除特定值的元素，这题的“特定值”则是一直在变化的。 //思路上，每当快指针指向的元素是重复的时候，就让慢指针停止一次步进，让快指针跳过这个元素，使得不会再把这个重复的元素向左移动，反而是用这个重复元素右侧的元素去覆盖它。 //可以将快慢两个指针想象成是在两个数组里的。快指针在旧数组里，慢指针在新数组里。然后将这个过程看作是一个把旧数组中的元素有选择地拷贝到新数组中的过程。 class Solution { public: int reArr...

//抄的题解的。注意区分单调队列与优先队列。一个升序的单调队列会自动把比它小的全部出队掉，保证自己进队后还能维持有序性（不是进队时找个正确的位置插入，而是直接就在队尾进队，前面有比自己小的就全部出队滚蛋）。而优先队列则是用了大顶堆的思想，把最大值调整到堆顶（也就是队头）。 //如果只是要实现单调队列本身，使用deque就行。每个元素入队时不断查询队尾（查询队尾只有双端队列才能做到）的元素是否比自己大，比自己小的就出队（pop_back），然后再继续查询队尾，直到比自己大为止。 //本题的滑动窗口，不仅要维护队列中的一个最大值，还需要保证窗口的有效性，因此在前面已经离开了窗口左端的过期的值是需要...

//好久没自己实现过一个栈了。topindex用来指向栈顶的下一个元素。细节处理要稍微注意一下。 //对于最小元素的记录，在入栈时可以随时更新，但出栈时不太好搞。 //有两种方案，一个是维护一个“历史记录”，记录此前min的历史值，出栈时回退历史值即可。这个需要额外的O(N)空间复杂度，但时间上是O(1)的。 //另一个方案就是我写的这种，出栈时重新遍历整个栈来找到min。无需额外空间，但需要O(n)的时间。 #include <climits> class Solution { public: void push(int value) { if (valu...

//这题比较容易就能想到利用栈的先进后出的特性，来在入队时放进栈1，出队时弹到栈2里，将“后出”通过栈的先进后出的特性给逆序成“先出”。 //唯一的问题在于什么时候弹。这个我自己想的时候没考虑好。看了题解说“栈2里还有东西时就pop栈2，没东西时才把栈1里的挨个弹到栈2里”。而且分析下来，每个元素最多进栈2出栈2一次，所以看起来是每个元素出队时都需要遍历栈1中其他元素，好像是O(n)的时间复杂度，而实际上平均下来只有O(1)。 #include <climits> class Solution { public: void push(int node) { ...

//如果是未排序的链表，用桶来记录。但这题是已排序的，所以空间复杂度只要O1就够了。我们记录当前的节点，判断它与下一个节点是否相同即可。 //整体思路是简单的，但是一些细节处理比较麻烦。比如这题要求把所有重复的节点都删掉，比如1233445要求删除成125而不是12345，这要求我们把Previous也删掉，所以需要一个Entry来记录重复的入口节点。以便删除完一整串重复的数字后能将入口的next指向“对岸” //再比如，有可能链表的开头就发生重复了，这样的话我们返回的链表的位置也必须从pHead往后挪。有可能还不止得挪一次。 //还比如，把整个链表删干净了的情况。 //落到实处时，还要考虑删...

//这题我有两个思路吧。如果Label能保证是不重复的话，嗯遍历就行了，只要靠Label就能找到Random指向的节点是谁。这题也确实是这样的。 //但如果不能通过Label来确定的话，就需要维护一个映射了，在构建基础链表的过程就要建立起从源链表到新链表的映射，然后回过头来遍历源链表时，就知道源链表里指的Random对应到新链表里是哪个节点了。如果不这么干的话，时间复杂度会高很多。 /* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int ...

//参考了剑指offer中记载的快慢指针法。快指针提前走k-1步。快指针抵达终点时慢指针就能到倒数第k个节点处了。例：1->2。求倒数第1个节点。提前走0步。快慢指针一起到最后一个节点。 class Solution { public: ListNode* FindKthToTail(ListNode* pHead, int k) { if(pHead==nullptr || k<=0) return nullptr; int times=k-1; ListNode* fast=pHead; ...

//参考了剑指offer上讲解的快慢指针法。核心思路分3步： //1.先确定有无环：快指针一次走2步，慢指针走1步，发生重逢说明有环。 //2.确定环的长度：重逢一定是在环中发生的，从重逢的位置开始，用个temp一直往前推进，直到回到这个位置，记录这个过程中走了多少步，这就是环的长度。 //3.移动到环开始的位置：让快指针从head开始走n步（n为环长度），相当于让慢指针落后n步，这样当快指针绕环走完一圈回来后正好能赶上慢指针刚抵达环的开头。 class Solution { public: ListNode* HasLoop(ListNode* p) { if...

class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode*p1=pHead1; ListNode *p2=pHead2; //这种做法的时间复杂度是O(n^2) // while (p1!=p2) { // p1=p1? p1->next:pHead1; // p2=p2? p2->next:pHead2; // } //参考了题解https://blog.nowcoder.net/n/faa...

#include <tuple> class Solution { public: //官方题解里的利用一个全局变量+二叉搜索树的中序遍历本身就是有序的 这个的思路挺妙的。 //思路：由于在二叉搜索树中，每一个节点的整棵左子树一定都小于这个节点。因此这个节点的prev就应该是左子树中最大的节点。同理，这个节点的Next应该是右子树中的最小的节点。我们将这两个节点设置为LeftMax，RightMin。作为递归函数的返回值。 //而这个节点本身，它既可能是某个父节点的左孩子，也可能是某个父节点的右孩子。当它作为左孩子时，父节点会希望它返回自己这棵树中的最大的节点（对父节...

//思路具体看题解。我是参考题解思路写的。 class Solution { public: void solve(TreeNode* root,int sum,int &count) { if(root==nullptr) return; if(root->val==sum) { count++; } solve(root->left, sum-root->val, count); solve(root->r...

//这题由于限制了空间复杂度为O1，因此最简单粗暴的办法，把两个链表遍历一边，所有值拿出来，存进数组，排序，建一个新链表，这种思路是不行的。我们只能在原地构建一个新链表——其实就是把几个指针大家挪来挪去，你指我指你。 //思路上借鉴了之前的反转链表的题解，想象成我们建了一个新的链表，然后把旧链表上的节点一个个“拆”下来，放到新链表上去。 class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* p1=pHead1; ListNode* p2=pHe...

//要用到3根指针来保证不丢。挺麻烦。题解中的双链表法，每次从原链表里摘下来的下一个节点都挂到新链表的头部，以此实现反转，这个想法很妙。 class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead->next==nullptr || pHead==nullptr) return pHead;//说明只有一个节点。 ListNode*previous=pHead; ListNode*current=pHead->next;//从第二个节点开始。 ListNode*n...

#include <algorithm> #include <iterator> #include <vector> class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int>temp; if(head==nullptr) return {}; ListNode* current=head; int length=0...