堆疊的壓入與彈堆疊序列

題目描述：

回顧堆疊的基本結構：

堆疊的結構是先進后出，后進先出


入堆疊序列:[1,2,3,4,5] 出堆疊序列[4,5,3,2,1]，否屬于同一個堆疊出入序列?
提示 ：入堆疊中可能有元素可能會堆疊

思路:

• 用一個堆疊模擬實作入堆疊，且在入堆疊時和出堆疊序列比較是否該元素提前出堆疊

代碼：

    bool IsPopOrder(vector<int> pushV,vector<int> popV)
    {
        if(pushV.size()==0&&popV.size()==0)//特殊情況
        {
            return false;
        }
        int push_index=0,pop_index=0;
        while(push_index<pushV.size())//當入堆疊序列沒有還有元素那么就該出結果了，因為模擬堆疊和出堆疊序列如果對不上就說明為假
        {
            st.push(pushV[push_index++]);
            while(!st.empty()&&st.top()==popV[pop_index])//注意，一直相等出堆疊可能stack空導致越界訪問
            {
                st.pop();
                pop_index++;
            }
        }
        return st.empty();//空代表完全符合
    }
    
private:
    stack<int>st;
};

鏈表的合并

題目描述：

思路：

• 歸并比較大小插入法

新開辟一個鏈表當作容器，在依次比較較小的值插入鏈表中

代碼：

  ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        
        
         //特殊情況
        if(pHead1==nullptr)
        {
            return pHead2;
        }
        if(pHead2==nullptr)
        {
            return pHead1;
        }

        //開辟一個新的鏈表當作容器，帶頭鏈表（哨兵位置）
        ListNode* ret=new ListNode(0);
        ListNode* NewHead=ret;
        
        while(pHead1&&pHead2)//比較大小需要倆個鏈表有值才可以
        {
        
            if(pHead1->val<pHead2->val)//鏈表1小于鏈表2
               {
                   ret->next=pHead1;
                   pHead1=pHead1->next;
                   ret=ret->next;
               }
            else//鏈表2小于鏈表1
            {
                   ret->next=pHead2;
                   pHead2=pHead2->next;
                   ret=ret->next;
            }            
        }
 
        //特殊情況      
        if(pHead1)//當鏈表2全部節點插入容器時鏈表1還有元素
        {
            ret->next=pHead1;
        }
        if(pHead2)//反之
        {
            ret->next=pHead2;
       }
       
        return NewHead->next;//回傳鏈表
    }

• 遞回比較法

哨兵位，帶頭鏈表的補充說明與解釋

這個一個節點不算這個鏈表中得元素，他的作用就是方便刪一個節點的元素,你就可以看作老鷹捉小雞這個游戲中的老母雞

二叉搜索樹的后序遍歷序列

題目描述：

知識補給：

二叉搜索樹
左子樹永遠大于根節點，右子樹永遠都大于根節點
如圖所示：



后續遍歷:
左子樹 右子樹 根 上述圖中的二叉搜索樹的后續遍歷為：
1->3->2->6->9->7->5

思路：

在知識補給中可以看到二叉搜索樹的特點就是左子樹比根節點大，右子樹比根節點大，那么我們只需要找到根在去判斷左子樹是不是比根節點小，右子樹是不是比根節點大

那么現在就有一個問題就是如何找根呢？

依舊是知識補給中，后續遍歷是先遍歷左子樹，在是右子樹，然后是根，那么后續遍歷最后一個節點就是這棵樹的根(如果疑惑前看知識補給或這篇二叉樹基礎)

代碼實作：

主邏輯

    bool VerifySquenceOfBST(vector<int> sequence) 
    {
        
        if(sequence.empty())//特殊處理，小心有詐
        {
            return false;
        }        
        
         return VerifySquenceOfBSTHelp(sequence,0,sequence.size()-1);//遞回開始判斷
    }

判斷部分

    bool VerifySquenceOfBSTHelp(vector<int>& sq,int start,int end)
    {
        if(start>=end)//當你只有一個與元素的時候就說明了沒有元素需要在比判斷了
        {
            return true;
        }
        
        int root=sq[end];//序列最后一個元素為根
        
        //劃磁區間
        int i; 
        for(i =start; i<end;i++)//end為根所以少比一次
        {
            if(sq[i]>root)//如果比根大就說明了i這個位置已經是右子樹了
            {
                break;
            }
        }
        
        for(int j =i;j<end;j++)//右子樹
        {
            if(sq[j]<root)//如果在右子樹區間中有一個節點小于根那么就不是一個二叉搜索樹樹
            {
                return false;   
            }
        }
        
        
        //遞回
        return  VerifySquenceOfBSTHelp(sq, , )&&VerifySquenceOfBSTHelp(sq, , )    
    }

區間分析

第一次遍歷：

左子樹 start

從第一次遍歷中可以看出左子樹的start還是這個序列的起始位置也就是當前節點的start

左子樹end

從第一次遍歷中可以發現左子樹的end就是在i的前一個位置，那么左子樹end 就是 i-1

右子樹start

從第一次遍歷中可以發現右子樹的start 其實就是 i 當下的位置 所以 左子樹的start 為 i

右子樹end

第一次遍歷之后那么當前的根節點對我們來說已經沒有用了，所以右子樹的end就是當前end-1

return  VerifySquenceOfBSTHelp(sq,start ,i-1 )&&VerifySquenceOfBSTHelp(sq,i ,end-1 );

題目鏈接

第一題
第二題
第三題

嘮嘮家常

最近天氣有點冷呀，大家注意保暖，今天剛好是2022年1月1日，祝大家新年快樂，新年新氣象，改掉上能的壞習慣，保留上年的好習慣