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;
}
};