8.5 位|归并|递归

lcr152

递归找m分界点，比较构造

class Solution {
    vector<int> postorder;
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        this->postorder = postorder;
        return recur(0, postorder.size() - 1);
    }

    bool recur(int left, int right)

{
        if (left >= right) return true;
        
        int root = postorder[right];
        int index = left;
        
        while (postorder[index] < root) index++;
        int m = index;
        
        while (index < right) {
            if (postorder[index] < root) return false;
            index++;
        }
        
        return recur(left, m - 1) && recur(m, right - 1);
    }
};
 

lc148.快慢+归并

if(!head || !head->next) return head;

 

 

ListNode* fast=head->next;

        while(fast && fast->next)

 

first=sortList(first); //!!!!
second=sortList(second);

merge

if(left->val < right->val)

class Solution {
    //归并
public:
    ListNode* sortList(ListNode* head) 
    {
        if(!head || !head->next) return head;

        ListNode* slow=head;
        ListNode* fast=head->next;

        while(fast && fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }

//归
        ListNode* second=slow->next;
        slow->next=nullptr;
        ListNode* first=head;

        first=sortList(first); //!!!!
        second=sortList(second);

        return merge(first,second);
    }

//并
    ListNode* merge(ListNode* left,ListNode* right)
    {
        ListNode* dummy=new ListNode(0);
        ListNode* tail=dummy;

        while(left && right)
        {
            if(left->val < right->val)
            {
                tail->next=left;
                left=left->next;
            }

            else
            {
                tail->next=right;
                right=right->next;
            }
            tail=tail->next;
        }

        //剩余部分
        if(left) tail->next=left;
        if(right) tail->next=right;

        return dummy->next;
    }
};

lc106

中序定区间长，后序找根建树

class Solution {

    //中序存hash

    unordered_map<int,int> hash;

    vector<int> postorder;

public:

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 

    {

        this->postorder=postorder;

        int n=inorder.size();

        for(int i=0;i<n;i++)

        {

            hash[inorder[i]]=i;

        }

        return dfs(n-1,0,n-1);   

    }

//i 依据后序，定root pos

//l ,r 依据中序，定区间长度，辅助找root pos 

    TreeNode* dfs(int i,int l,int r)

    {

        if(l>r) return nullptr;

        int num=postorder[i];

        TreeNode* root=new TreeNode(num);

        int idx=hash[num];

        root->right=dfs(i-1,idx+1,r);

        root->left=dfs(i-1-(r-idx),l,idx-1);//跳过 根 右，到达左子树根

        return root;

    }

};

lc2917

将合格位设为1：ret |= (1 << i);

class Solution

{
public:
    int findKOr(vector<int>& nums, int k) {
        vector<int> cnt(32, 0); 
        for (auto& n : nums) {
            int i = 0;
            while (i < 32) { 
                if (n & (1 << i)) {
                    cnt[i]++;
                }
                i++;
            }
        }
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if (cnt[i] >= k) { 
                ret |= (1 << i);
            }
        }
        return ret;
    }
};