155. Min Stack

155. Min Stack

思路:

用另一个栈保存另一个栈的各个元素插入,删除后的最小值。

他利用这么一个现象:后插入的大元素不会影响这个栈的最小值,反之小元素会改变。那么只要把此时小元素插入到最小栈即可,同理删除元素的时候也按值删除。

Read more

739. Daily Temperatures

739. Daily Temperatures

思路:

  1. 单调栈;用单调栈维护从后往前遍历当前元素的最大值,便可以轻松获取当前元素之后的最大值下标,即可以更新下一个更大元素的时间差。

  2. KMP失败匹配算法;从后往前遍历,当前元素的更大值要么是当前元素的下一个元素,要么是下一个元素的更大值,要么是下一个元素的更大值的更大值……如此“递归”查找可得下一个最大值。如果查找不到,就不存在最大值。

Read more

347. Top K Frequent Elements

思路:

map记录出现初次,

堆维护前K大

代码:


class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        map<int, int> counter;
        map<int, int>::iterator iter;
        priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int,int> > >  pq;
        for(auto i : nums)
            counter[i]++;
        
        iter = counter.begin();
        pair<int, int> tp;
        int s1, s2, e1, e2;
        // cout << counter.size() << endl;
        while(iter != counter.end()){
            s1 = iter->first;
            s2 = iter->second;
            if(pq.size() == k){
                tp = pq.top();
                e2 = tp.first;
                e1 = tp.second;
                if(e2 < s2){
                    pq.pop();
                    pq.push(make_pair(s2, s1));
                }
            }else pq.push(make_pair(s2, s1));            
            iter++;
        }

        vector<int> ans;        
        while(pq.size() > 0){                                    
            ans.push_back(pq.top().second);            
            pq.pop();
        }
        return ans;
    }
};

1609. Even Odd Tree

思路:

层序遍历。记录边界即可。

代码:


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    bool isEvenOddTree(TreeNode* root) {
        if(root == nullptr ) return false;
        queue<TreeNode *> que;
        vector<int> a;
        int level = 0, num = 1, nextn = 0;;
        que.push(root);
        while(!que.empty()){
            TreeNode *t = que.front();
            que.pop();
            a.push_back(t->val);
            num--;
            if(t->left){
                que.push(t->left);
                nextn++;
            }
            if(t->right){
                que.push(t->right);
                nextn++;            
            }            
            if(num == 0){
                num = nextn;
                nextn = 0;
                int flag = 1;
                if(a.size() < 1) continue;

                if(level & 1){
                    for(int i = 1; i < a.size(); i++){
                        if(a[i] >= a[i - 1] || a[i]%2 == 1 )
                            flag = 0;
                    }
                    if(a[0]%2 == 1) flag = 0;
                }
                else{
                    for(int i = 1; i < a.size(); i++){
                        if(a[i] <= a[i - 1] || a[i]%2 == 0)
                            flag = 0;
                    }                
                    if(a[0]%2 == 0) flag = 0;

                }
           
                a.clear();
                level ++;
                if(!flag) return false;
            }   
        }
        return true;
    }
};

654. 最大二叉树

一个基础的递归建树就可以解决。

以递归的思想处理每一个新数组,先找出最大值所在并以此值一分数组为2个数组,同时递归建树即可。

Note:注意边界错误,如right到底没有没值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return constructBT(nums, 0, nums.size() - 1);
        
    }
    TreeNode* constructBT(vector<int>& nums, int left, int right){
        if(left > right)
            return NULL;
        
        int index = left, nmax = nums[left];
        for(int i = left + 1; i <= right; i++){
            if(nmax < nums[i]){
                nmax = nums[i];
                index = i;
            }
        }
        TreeNode* root = new TreeNode(nmax);
        root->left = constructBT(nums, left, index - 1);
        root->right  = constructBT(nums, index + 1, right);
        return root;
    }
    
    

};

面试题 链表相关

所有关于链表的题目都会总结在这里。假设这些题目的链表的头结点都是带有效值的

定义链表

struct ListNode{
    int Value;
    ListNode* pNext;
};

尾插入节点

注意第一个参数是指针的指针,因为有可能需要修改第一个链表节点。

void AddToTail(ListNode **pHead, int value){
    if(pHead == null) return;
	ListNode *pNew = new ListNode();
    pNew->Value = value;
    pNew->pNext = nullptr;
    if(*pHead == null){
        *pHead = pNew;
    }else{
        ListNode* pNode = *pHead;
        while(pNode->pNext != null){
            pNode = pNode->pNext;
        }
        *pNode->pNext = pNew;        
    }
}

删除第一个对应值的链表

viod RemoveNode(ListNode** pHead, int value){
    if(pHead == nullptr || *pHead == nullptr) return;
    ListNode *pToDeleted = nullptr;
    if((*pHead)->value == value){
        pToDeleted = *pHead;
        *pHead = (*pHead)->pNext;
    }else{
        ListNode *pNode = *pHead;
        //pNode指向检查节点的前一个节点
        while((*pNode)->pNext != null && (*pNode)->pNext->value != value){
            pNode = pNode->pNext;
        }
        if((*pNode)->pNext != null && (*pNode)->pNext->value == value){
			pToDeleted = (*pNode)->pNext;
        }
    }
	if(pToDeleted != nullptr){
        delte pToDelted;
        pToDelted = nullptr; //释放内存后,即使是不需要使用的指针,也要做好清除工作,不然不容易维护            
    }
	
}

pToDeleted = *pNode->pNext;上面遍历链表中代码不应该用pToDeleted来记录链表值,否然容易出现代码指针值意义混乱,造成不该删的指针却删掉了。

面试题6 从尾到头打印链表

假如对空间复杂度在O(N)O(N)之上,那么可以使用栈或者递归。

栈代码如下

void PrintListReversingly_Iteratively(ListNode* pHead){
    //使用指针类型的STACK更省内存?
    std::stack<ListNode*> nodes;
    ListNode* pNode = pHead;
    while(pNode != nullptr){
        nodes.push(pNode);
        pNode = pNode->pNext;
    }
    while(!nodes.empty()){
        pNode = nodes.top();
        printf("%d\n", pNode->value);
        nodes.pop();
    }   
}

归代码

void PrintListReversingly_Recursively(ListNode* pHead){
    if(pHead == nullptr) return;
    PrintListReversingly_Recursively(pHead->pNext);
    printf("%d\n", pHead->pNext);
    
}

面试18:删除一个链表节点

题面:

给定一个单向链表的头结点指针和一个指向待删除的节点的指针,要求用O(N)O(N)时间删除节点。

思路:

教科书上的链表删除都是遍历得到上一个待删除的节点的指针,时间复杂度O(N)O(N)。显然不行,也可以直接把待删除的节点K的下一个节点J的内容复制到K上,再删除J,就可以快速删除。考虑边界上,如果没有下一个节点则需要从头遍历;如果只有一个头结点且删除的是头结点,那么只能把头结点置nullptr

其时间复杂度为(n−1)∗O(1)+O(N)(n−1)∗O(1)+O(N)。

代码:

void DeleteNode(ListNode **pHead, ListNode *pToBeDeleted){
    if(pHead == nullptr || (*phead) == nullptr || (*pToBeDeleted) == nullptr ) return;
    ListNode *pFree = nullptr;
    
    if(pToBeDeleted->pNext){
        pFree = ToBeDeleted->pNext;
        pToBeDeleted->value = pToBeDeleted->pNext->value;   
        pToBeDeleted->pNext = pToBeDeleted->pNext->pNext;   
        
    }
    //删除节点无后继节点,且是头结点
    else if( *pHead == pToBeDeleted){
		pFree = *pHead;
        *pHead = nullptr;
    }
    // 链表中多个节点,且删除节点在末尾
    else{
		ListNode *pCur = *pHead
        for(; pCur->pNext->pNext != nullptr; pCur = pCur->pNext);
        pFree = pCur->pNext;
        pCur->pNext = nullptr;
    }
    Delete pFree;
}

错误点:

  • the properiry of “*” > the properity of “==”
  • 链表插入和删除后没有设置指针

注意点:

这个函数假设了待删除的节点一定在链表中;

头结点可能删除掉,所以设置了头结点为指针的指针。

面18(题目二):删除重复值的链表节点

题面:

删除一条已排序的链表中的所有的其值重复出现的节点。

思路:

在上面学习的基础上,连续删除就行,应该是比较简单的。

代码:

void DeleteDuplication(ListNode **pHead){
    if(pHead == nullptr || *pHead == nullptr) return;
    
    ListNode *pCur = *pHead, *pPre = nullptr, *pFree = nullptr;
    //定义一个头结点,避免不同情况的删除
    ListNode *pKid = new ListNode();
    pKid->pNext = *pHead;
    pPre = pKid;
    
    while(pCur != nullptr){
		int value = pCur->value,  isDuplication = 0;
        //删除后面的重复节点
        while(pCur->pNext && pCur->pNext->value == value){
            pFree = pCur->pNext;
            pCur->pNext = pFree->pNext;
            delete pFree;
            isDuplication = 1;
        }
        
        //若重复,则删除第一个重复节点
		if(isDuplication){
			pFree = pCur;			
			pCur = pCur->pNext;			
			pPre->pNext = pCur;
            delete pFree;
			// if(pFree) printf("@");
        }
        //不重复则下移
        else{
            pPre = pPre->pNext;
            pCur = pCur->pNext;
        }
    }
	*pHead = pKid->pNext;
    delete pKid;
}

测试

参见

面22:倒数第K个节点

题面:

给出一个链表,返回倒数第K个节点。

思路:

最直观的思路是遍历到终点,反向遍历K-1次,但是对单链表无可奈何,而且效率不高。

第二种思路可以遍历一次求链表的长度L,第二次遍历L - K + 1个节点。但是需要遍历两次链表。

三种思路更秒,采用双指针,第一个指针先遍历K个节点,随后两个节点一起遍历,直到第一个指针为空,第二个指针就指向了倒数第K个节点。

代码:

ListNode *FindKthToTail(ListNode *pHead, unsigned int K){
    if(pHead == nullptr) return nullptr;
    ListNode *p1 = pHead, *p2 = pHead;
    
    for(int i = 0; i < K; i++){
        if(p1 == nullptr) return nullptr;
        p1 = p1->pNext;
    }
    while(p1!=nullptr){
        p1 = p1->pNext;
        p2 = p2->pNext;
    }
    return p2;
}

这代码写的比剑指offer代码写的优美多了

相关扩展:

相关题目有找出链表的中间节点;判断一个链表是否有环;更难一点判断链表的环的入口节点!

其思路宗旨都是使用两个进度不一样的指针指向不同的节点来解决问题!

面23:链表中的环的入口节点

题面:

给出一个链表,求出其成环的入口节点。

思路:

首先得判断有环,可以使用一个快一慢的两只指针(移动速度分别为2和1)指向链表头。如果链表有环,则快慢指针就一定会相遇。

那么对于有环的链表如何确定其入口节点呢?假设环的中节点有K个,快指针从头先遍历K次之后,快慢指针同时开始遍历,正好两个指针会在入口节点上汇合!

如何确定环中节点呢?这个!可以直接在确定有环后,记录下该节点的位置,再继续遍历直到重新到该节点同时统计经过的节点数量即可。

amazing啊

代码:

ListNode *FindCycleNode(ListNode* pHead){
	if(pHead == nullptr) return nullptr;
    ListNode *pSlow, *pQuick, *pRecord = nullptr ;
    //判断有没有环
    pSlow = pQuick = pHead;
    while(pQuick != nullptr){
	    pQuick = pQuick->pNext;
        if(pQuick) pQuick = pQuick->pNext;
        if(pSlow) pSlow = pSlow->pNext;        
        if(pSlow == pQuick) break;
    }
    if(pQuick == nullptr) return nullptr;
    //确定环内数量
    pRecord = pSlow;
    int numberOfCycle = 0;
    while(pRecord != pSlow){
        numberOfCycle++;
        pSlow = pSlow->pNext;
    }
    //确定环的入口节点
    pSlow = pQuick = pHead;
    for(int i = 0; i < numberOfCycle; i++){
        pQuick = pQuick->pNext;
    }
    while(pSlow != pQuick){
        pQuick = pQuick->pNext;
        pSlow = pSlow->pNext;                
    }
    return pSlow;
}

面24:反转链表

题面:

输入一个链表的头结点,反转该链表并输出反转后的链表的头结点。

思路:

在反转过程中,假设有三个顺序排列的待反转的链表ijk,其中j是待反转的链表。初始化,i为空指针,j为头节点,k为头结点的下一个指针指向的内容(可能为空),并把i的指针指空。在链表反转过程如下:j的指针指向i,然后把ijk分别按次序向后移动。重复执行上述步骤直到j为空。

代码:

ListNode *ReverseList(ListNode *pHead){
    if(pHead == nullptr) return nullptr;
    ListNode *p1 = nullptr, *p2 = pHead, *p3 = pHead->pNext;
    while(p2 != nullptr){
        p2->pNext = p1;
        p1 = p2;
        p2 = p3;
        if(p3) p3 = p3->next;        
    }
    return p2;    
}

面25:合并链表

题面:

将两个链表增序合并成一条链表。

思路:

用两个指针指向两条链表的头结点,用合并数组的思路合并即可。注意一条链表为空后,另一条不为空的链表可以直接连上去。

代码:

ListNode *Merge(ListNode *pHead1, ListNode *pHead2){
    if( pHead1 == nullptr && pHead2 == nullptr){
        return nullptr;
    }else if(pHead1 == nullptr) return pHead2;
    else if(pHead2 == nullpr) return pHead1;
    
    ListNode *p1 = pHead1, *p2 = pHead2, *pHead3 = new ListNode(), *p3 = pHead3;
    
    while(p1 && p2){
        if(p1->value <= p2->value){
            p3->pNext = p1;
            p3 = p1;            
            p1 = p1->pNext;

        }else{
            p3->pNext = p2;
            p3 = p2;
            p2 = p2->pNext;
        }                 
    }
    p3->pNext = nullptr;       
    if(p1){
        p3->pNext = p1;
    }else if(p2){
        p3->pNext = p2;
    }
    ListNode *pFree = pHead3;
    pHead3 = pHead->pNext;
    delete pFree;
	return pHead3;        
}

测试

参见

面35:复杂链表的分解

题面:

给出一个有两个指针的链表数据结构,一个指针1指向下一个节点,另一个指针2可指向任意一个节点,或者为空。将给出的链表复制并返回头结点。

思路:

这题目还是挺不错的!属于比较复杂的题目,而且有思考空间。

将复制的过程分解为两个部分,第一步先不管指针2,复制整个链表;第二步再设置指针2。第一步需要的复杂度为O(N)O(N)。第二步再复制的过程中需要确定复制链表中指针2指向的节点的的位置。

第一种确定位置的思路:就是从原链表遍历寻找原指针指向的节点位置,同样的在复制链表上一起遍历。复杂度为O(N2)O(N2)。

第二种确定位置的思路:直接用hash表记录下原链表中节点和复制链表中对应节点的映射关系。复杂度为O(N)O(N)。是用了空间换时间的思路。

害怕碰撞。

脱离上面的方案的限制,更巧妙的方法来了。链表的顺序遍历远远比随机遍历方便很多,而且指针指向的节点的位置不随链表节点而变化。可以考虑把复制节点直接插入到被复制节点的后面。全部复制完成后,由于原节点的指针2指向的节点的后一个节点就是复制节点的指针2指向的节点,所以可以直接指向。复杂度为O(N)O(N),空间复杂度为O(1)O(1)。

代码:

struct ComplexListNode{
    int value;
    ComplexListNode *pNext;
    ComplexListNode *pSibling;    
}

void CopyNode(ComplexListNode *pHead){
    if(pHead == nullptr) return null;
    ComplexListNode *pNode = pHead;
    while(pNode){
        ComplexListNode *pNew = new ComplexListNode();
        pNew->value = pNode->value;
        pNew->pNext = pNode->pNext;
        pNew->pSibling = nullptr;
        
        pNode->pNext = pNew;
    	pNode = pNew->pNext;
    }    
}

void SetSiblingLink(ComplexListNode * pHead){
    if(pHead == nullptr )return nullptr;
    ComplexListNode *pNode  = pHead;
    while(pNode){
		ComplexListNode *pNext = pNode->pNext;
        pNext->pSibling = pNode->pSibliing->pNext;
        pNode = pNext->pNext;
    }    
}

ComplexListNode *GetComplexList(ComplexListNode *pHead){
    if(pHead == nullptr) return nullptr;
	ComplexListNode *pNode = pHead;
    ComplexListNode *pClonedHead = pNode->pNext;
    ComplexListNode *pClonedNode = pNode->pNext;
    pNode->next = pClonedNode->next;
    pNode = pClneNode->next;
    while(pNode){
        pClonedNode->pNext = pNode->pNext;        
        pNode->pNext = pNode->pNext->pNext;
        pClonedNode = pNode->pNext;
        pNode = pClonedNode->pNext;   
        /*
        //we can write in this way.
        pClonedNode->pNext = pNode->pNext;        
        pClonedNode = pClonedNode->pNext;
		pNode->pNext = pClonedNode->pNext;
        pNode = pNode->pNext;                  
        */
    }
    return pClonedHead;      
}
ComplexListNode *Clone(ComplexListNode* pHead){
    CopyNode(pHead);
    SetSiblingLink(pHead);
    return GetComplexList(pHead);
}

面36:把二叉搜索树转化为双向链表

题面:

如题,要求不创建任何新节点,只能调整树中节点的指向。输出调整后的排序链表。

思路:

可以从递归的角度入手。对于一个节点A,中序遍历到A,则A的左子树已经转化为了链表,连接好AA的左子树的最大节点(前一个指针)的指针则连接完成。

那对于A的右子树的最小节点BA之间的连接,也可以看成B与前一个节点的指针相互链接。那么我们只需要在中序遍历的过程中改变前一个指针的内容即可。

注意一下整棵树的最大的右指针和最小节点的左指针,发现都应该是空,无需额外修改。

对于一个节点A的左右指针,分别指向按顺序排列的旁边两个节点。可以用中序遍历来获取该节点的前一个节点B的指针,并设置好B的右指针和A的左指针。如此就可以在中序遍历的后设置除了最后一个节点的右指针,但是右指针本来就应该是NULL,所以无需修改。

代码:

void AdjustLinkCore(BinaryTreeNode* pRoot, BinaryTreeNode *&preNode, BinaryTreeNode *&pHead){
    if(pRoot == nullptr) return;
  	AdjustLinkCore(pRoot->pLeft, preNode, pHead);

    if(pHead == nullptr) pHead = pRoot;
    pRoot->pLeft = preNode;
    if(preNode) preNode->pRight = pRoot;
    preNode = pRoot;
    
    AdjustLinkCore(pRoot->pRight, preNode, pHead);
}
BinaryTreeNode* AdjustLink(BinaryTreeNode* pRoot){
    BinaryTreeNode *preNode = nullptr;
    BinaryTreeNode *pHead = nullptr;
    AdjustLinkCore(pRoot, preNode, pHead);
    return pHead;
}

面52:两个链表的第一个公共节点

题面:

如题。

思路:

明显地,可以用栈来存储两个链表遍历过程。空间复杂度和时间复杂度都是O(N)O(N)。

换一种想法,能不能直接遍历就使两个链表同时遍历到第一个公共节点。定义两个指针来遍历两条链表。只要让一个指向长链表的节点的指针多走多出的节点,就可以让两个节点同时同序的遍历到公共节点。时间复杂度为O(N+M)O(N+M),空间复杂度O(1)O(1)。

代码:

int GetLenOfList(ListNode *pHead){
    int len = 0;
    ListNode *pNode = pHead;
    while(pNode){
        pNode = pNode->pNext;
        len++;
    }
    return len;
}
ListNode *FindFirstCommonNode(ListNode *pHead1, ListNode *pHead2){
    if(pHead1 == nullptr || pHead2 == nullptr) return nullptr;
    int len1 = GetLenOfList(pHead1);
    int len2 = GetLenOfList(pHead2);
    if(len1 < len2){
        swap(pHead1, pHead2);
        swap(len1, len2);
    }
    int step = len1 - len2;
	ListNode *pNode1 = pHead1;
    ListNode *pNode2 = pHead2;
    while(step){
        pNode1 = pNode->pNext;
        step--;
    }
    while(pNode1 != pNode2){
        pNode1 = pNode1->pNext;
        pNode2 = pNode1->pNext;
    }
    //two pNodes maybe refer to null or the first common node.
    return pNode1;
}

更简单的解法:

双指针遍历两条链表,遍历到结尾则跳到另一条链表上。路径长度的相等一定会有两个指针相遇。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1 = headA,  *p2 = headB;
        while(p1 != p2){
            p1 = p1 == nullptr ? headB : p1->next;
            p2 = p2 == nullptr ? headA : p2->next;
        }
        return p1;
    }
};

链表回文判断

234. Palindrome Linked List

O(n)时间,O(1)空间

思路:

朴素的思路:先用快慢指针找到链表中间节点,之后翻转后半部分链表。判断两个链表是否相同。

其中奇数个节点链表需要考虑一下。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow ,*quick;
        slow = quick = head;
        while(quick && quick->next){
            slow = slow->next;
            quick = quick->next->next;
        }
        ListNode *p2 = reverseList(slow), *p1 = head;
        while(p1 && p2){
            if(p1->val != p2->val) return false;
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
        
    }

    ListNode *reverseList(ListNode* head){
        if(head == nullptr) return head;
        ListNode *per = nullptr, *cur = head, *next = head->next;
        while(cur){
            cur->next = per;
            per = cur;
            cur = next;
            if(next) next = next->next;
        }
        return per;
    }
};

奇偶链表节点分解

非常容易写复杂的题目。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!(head && head->next)) return head;
        // ListNode *p1 = head, *p2 = new ListNode(), *evenHead = p2, *pre = nullptr;
        // while(p1 && p1->next){
        //     p2->next = p1->next;
        //     p2 = p2->next;
        //     p1->next = p2->next;
        //     pre = p1;
        //     p1 = p2->next;
        // }
        // p2->next = nullptr;    
        // p1 = p1 ? p1 : pre;
        // p1->next = evenHead->next;
        // delete evenHead;
        // return head;
        ListNode *evenHead = head->next, *odd = head, *even = head->next;
        while(even && even->next){
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

删除倒数第N个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode node, *pre = &node;
        pre->next = head;
        ListNode *quick, *slow;
        quick = slow = pre;
        for(int i = 0; i < n; ++i) quick = quick->next;
        while(quick->next){
            quick = quick->next;
            slow = slow->next;
        }
        ListNode *fordel = slow->next;
        slow->next = fordel->next;
        if(fordel == head){ //删除节点 务必小心:1.删了头结点,需要重置头结点 2.考虑后续节点
            head = fordel->next;
        }
        delete fordel;            
        return head; 

    }
};

PAT 1043 二叉树重建

搜索二叉树的前序列推出整个二叉树或者推出后序列

思想:利用二叉树的子树的性质,分隔开两个子树,递归的遍历根节点;

难点:利用双针思想保持并判断两个区间的内容,同时确定无子树的错误和递归边界;

PAT 1043

其实有点意思
柳神的代码比我的构思好多了
vector<int>pre,post;
bool isMirror;
void checkPre(int root,int tail)//【root,tail】
{
    if(root>tail) return;//! 空节点退出
    int i=root+1,j=tail;
    if(!isMirror)
    {
        //!while退出之时 就是到了另一个子树序列的开头与结尾
        while(i<=tail&&pre[root]>pre[i]) i++;
        while(j>root&&pre[root]<=pre[j]) j--;//!若该序列是二叉搜索树则必有i==j+1
    }
    else
    {
        while(i<=tail&&pre[root]<=pre[i]) i++;
        while(j>root&&pre[root]>pre[j]) j--;
    }
    if(i-j!=1) return;//!由于树可能不存在 需要处理异常情况
    checkPre(root+1,j);
    checkPre(i,tail);
    post.push_back(pre[root]);//!前序遍历压入当前根节点;
}
int main()
{
    int n, flag = 1;
    scanf("%d",&n);
    pre.resize(n+1);
    for(int i=0; i<n; i++) scanf("%d",&pre[i]);
    checkPre(0,n-1);
    if(post.size()!=n)//! 不为二、        printf("YES\n");
        for(int i=0; i<n; i++)
        {
            printf("%d",post[i]);
            printf("%c",i!=n-1?' ':'\n');
        }
    }
    else printf("NO\n");

}

PAT风格二叉树总结

总结一下PAT出现的所有树的套路

前序中序转后序

int post[40], n, pos = 0;
vector<int> pre, in;
stack<int>s;
void dfs(int l1, int h1, int l2, int h2){
    if(l1 > h1) return;
    int k = l2;
    for(;in[k]!=pre[l1];k++);
    dfs(l1 + 1, l1 + k - l2, l2 , k - 1);
    dfs(l1 + k - l2 + 1, h1, k + 1, h2);
    post[pos++] = pre[l1];
}
int main(){
    int t;
    cin >> n;
    for(int i =0 ;i < 2 * n; i++){
        string a;
        cin >> a;
        if(a[1] == 'u'){
            cin >> t;
            s.push(t);
            pre.push_back(t);
        }else{
            in.push_back(s.top());
            s.pop();
        }
    }
    dfs(0, n - 1, 0, n - 1);
    for(int i = 0;i < n; i++){
        if(i == n - 1) cout << post[i];
        else cout << post[i] << ' ' ;
    }
}

BST + CMT 转层序

int cbst[2000], n, pos = 1, in[2000];
int dfs(int u){
    if(u > n ) return 0;
    dfs(u * 2);
    cbst[u] = in[pos++];
    dfs(u * 2 + 1);
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> in[i];
    }
    sort(in + 1, in + n + 1);
    dfs(1);
    for(int i = 1;i <= n; i++){
        if(i == n ) printf("%d", cbst[i]);
        else printf("%d ", cbst[i]);
    }
}

前序中序转后序

vector<int> in, post, pre;
int n, flag  = 1;
void dfs(int l1, int h1, int l2, int h2){
    if(l1 >= h1){
        if(l1 == h1) in.push_back(pre[l1]); // l1 > h1时 才能压入 否则是错误的
        return;
    }
    int k = l1 + 1;
    while(k <= h1 && pre[k] != post[h2 - 1]) k++;
    if(k == l1 + 1)
        flag = 0;
    dfs(l1 + 1, k - 1, l2, l2 + k - l1 - 2  );
    in.push_back(pre[l1]);
    dfs(k, h1, l2 + k - l1 - 1, h2 - 1 );
}
int main(){
    cin >> n;
    post.resize(n);
    pre.resize(n);
    for(int i = 0; i < n; i++) cin >> pre[i];
    for(int i = 0; i < n; i++) cin >> post[i];
    dfs(0, n - 1, 0 , n - 1);
    if(flag) cout << "Yes\n";
    else cout << "No\n";
    for(int i = 0; i < n; i++)
        if(i == n - 1) printf("%d\n", in[i]);
        else printf("%d ", in[i]);
}

层序中序转前序后序

这个问题也非常的巧妙,本来是一个层次遍历划分出一个父节点,但是下一步左右子树划分却成了问题,这个算法有一次刷新了我的世界观。使用中序遍历的思想,在层次遍历中查询每一个节点的归属父节点的左子树还是右子树

const ll mod = 1000000007;
int tree[40][2], val[40], n;
int  in[40];
vector<int> pre, post, lay;

int build(vector<int> lay, int l, int r){
    if(l > r) return 0;
    int k = 1;
    while(lay[0] != in[k]) k++;
    vector<int> llay, rlay;
    for(int i = 1;i < lay.size(); i++){
        int isl = 0;
        for(int j = l; j< k; j++)
        if(lay[i] == in[j]){
            isl = 1;
            break;
        }
        if(isl) llay.push_back(lay[i]);
        else rlay.push_back(lay[i]);
    }
    pre.push_back(in[k]);
    tree[k][0] =  build(llay, l, k - 1);
    tree[k][1] =  build(rlay, k + 1, r);
    post.push_back(in[k]);
    return k;
}
int main(){
    cin >> n;
    lay.resize(n);
    int root = 0;
    for(int i = 0;i < n; i++) cin >> lay[i];
    for(int i = 0;i < n; i++) cin >> in[i + 1];
    root = build(lay, 1, n);
    for(int i = 0;i < n;i++)
        if(i == n - 1) printf("%d\n", pre[i]);
        else printf("%d ", pre[i]);
    for(int i = 0;i < n;i++)
        if(i == n - 1) printf("%d\n", post[i]);
        else printf("%d ", post[i]);
}

判断完全二叉树

int tree[200][2], n, ingree[200], root, lastnood, flag = 1;
int bfs(int u){
    int tn = 1;
    queue<int> que;
    que.push(u);
    while(que.size()){
        int v = que.front(); que.pop();
        lastnood = v;
        if(tree[v][0] == -1){
            if(tn != n)
                flag = 0;
        }else{
            que.push(tree[v][0]);
            tn++;
        }
        if(tree[v][1] == -1){
            if(tn != n)
                flag = 0;
        }else{
            que.push(tree[v][1]);
            tn++;
        }
    }
}

int main(){
    fill(tree[0], tree[0] + 200 * 2 , - 1 );
    cin >> n;
    for(int i = 0;i < n; i++) {
        string a, b;
        cin >> a >> b;
        if(a != "-"){
            int v = atoi(a.c_str());
            tree[i][0] = v;
            ingree[v] ++;
        }
        if(b != "-") {
            int v = atoi(b.c_str());
            tree[i][1] = v;
            ingree[v] ++;
        }
    }
    for(int i = 0; i < n ;i++) if(ingree[i] == 0) root = i;
    bfs(root);
    if(flag) cout << "YES " << lastnood;
    else cout << "NO " << root;

}

静态链表建树

int tree[2000][3], lay[2000], n, depest, ct = 0;
int insert(int u, int val, int dep){
    depest = max(depest,dep);
//    cout << u << endl;
    if(u == 0){
        lay[dep] ++;
        tree[++ct][2] = val;
        return ct;
    }else if(val <= tree[u][2]){
        tree[u][0] = insert(tree[u][0], val, dep + 1);
    }else if(val > tree[u][2]){
        tree[u][1] = insert(tree[u][1], val, dep + 1);
    }
    return u;
 }
 int main()
 {
     int root = 0, tmp;
     cin >> n;
     for(int i = 0;i < n;i++){
        cin >> tmp;
        root = insert(root, tmp, 1);
     }
     cout << lay[depest ] << " + " <<  lay[depest - 1] << " = " <<  lay[depest] + lay[depest - 1] << endl;
 }

判断树

晴神的一道题1016

int tree[100][3], val[40], n,  ingree[20];
int navln, layer[23], isct = 1, switime;
stack<int> s;
//avl
int ctavl(int root){
    if(root == 0) return 0;
    int h1 = ctavl(tree[root][0]);
    int h2 =  ctavl(tree[root][1]);
    if( abs(h1 - h2) > 1) navln ++;
    return max(h1, h2) + 1;
}
//层序遍历同时存储 逆层序遍历的顺序以便调整堆!
void isctree(int root){
    int nt = 1;
    queue<int> que, lay;
    que.push(root);
    lay.push(1);
    while(que.size()){
        int u = que.front(); que.pop();
        int ll = lay.front(); lay.pop();
        s.push(u);
        layer[ll] ++;
//        cout << u << endl;
        if( tree[u][0] ){
            que.push(tree[u][0]);
            lay.push(ll + 1);
            nt ++;
        }else if(nt != n) isct = 0;
        if( tree[u][1] ){
            que.push(tree[u][1]);
            lay.push(ll + 1);
            nt ++;
        }else if(nt != n) isct = 0;
    }
}
// 向下调整 大顶堆
void downAdjust(int root){
    for(int p = tree[root][0];p !=0; p = tree[root][0]){
        int pp = tree[root][1];
        if(val[pp] > val[p]) p = pp;
        if(val[p] < val[root]) break;
        swap( val[root], val[p]);
        switime ++;
        root = p;
    }
}
int main(){
    string s1, s2;
    cin >> n;
    for(int i = 0;i < n; i++){
        cin >> val[i];
    }
    for(int i = 1;i <= n; i++){
        cin >>  s1 >> s2;
        if(s1 != "-"){
            tree[i][0] = atoi(s1.c_str());
            ingree[atoi(s1.c_str())]++;
        }
        if(s2 != "-"){
            tree[i][1] = atoi(s2.c_str());
            ingree[atoi(s2.c_str())]++;
        }
    }
    int rt = -1;
    for(int i = 0;i < n; i++)
        if( ingree[i] == 0) rt = i;
//    cout << rt ;
    ctavl(rt);
    if(navln != 0) cout << "NOT AVL TREE!!!\n" <<  navln << endl;
    else{
        isctree(rt);
        int p = 1, noden = 1;
        while(noden == layer[p]){
            noden *= 2;
            p++;
        }
        if(!isct) cout << "NOT COMPLETE TREE!!!\n" << p - 1 << endl;
        else{
            while(s.size()){
                int u = s.top(); s.pop();
                downAdjust(u);
            }
            cout << "OHHHHH HEAP!!!\n" << switime << endl;
        }
    }
}