头像

tgs


访客:256

离线:4天前


活动打卡代码 AcWing 38. 二叉树的镜像

tgs
6天前
void mirror(TreeNode* root) {
    if (!root) return;
    TreeNode *right = root->right; 
    mirror(right);
    TreeNode* left = root->left; 
    mirror(left);
    root->left = right;
    root->right = left;
    return;
}


活动打卡代码 AcWing 37. 树的子结构

tgs
6天前
bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (!pRoot1 || !pRoot2) return false;
        if (isSame(pRoot1, pRoot2)) return true;
        return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
    }

    bool isSame(TreeNode* pRoot1, TreeNode* pRoot2) {
        if (!pRoot2) return true;
        if (!pRoot1 || pRoot1->val != pRoot2->val) return false;
        return isSame(pRoot1->left, pRoot2->left) && isSame(pRoot1->right, pRoot2->right);
    }
};



tgs
6天前
class Solution {
public:
    bool isPopOrder(vector<int> &pushed, vector<int> &popped)
    {

        int sz = pushed.size();
        int sz2 = popped.size();
        if (sz != sz2) return false;
        stack<int> s;

        int j = 0;
        for (int x : pushed)
        {
            s.push(x);
            while (!s.empty() && j < sz && s.top() == popped[j])
            {
                s.pop();
                j++;
            }
        }

        return j == sz;
    }
};



tgs
6天前
  • Two Stacks
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        s.push(x);
        if (min_s.empty() || x <= min_s.top())
            min_s.push(x);
    }

    void pop() {
        if (s.top() == min_s.top()) 
            min_s.pop();
        s.pop();
    }

    int top() {
        return s.top();    
    }

    int getMin() {
        return min_s.top();    
    }

private:
    stack<int> s;
    stack<int> min_s;
};
  • One stack
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        min = INT_MAX;
    }

    void push(int x) {
        if (x <= min) {
            s.push(min);
            min = x;
        } 
        s.push(x);
    }

    void pop() {
        int t = s.top();
        s.pop();
        if (t == min) { 
            min = s.top();
            s.pop();
        }
    }

    int top() {
        return s.top();     
    }

    int getMin() {
        return min;  
    }

private:
    stack<int> s;
    int min;
};



tgs
6天前
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int size;
    vector<int> res;

    if ((size = matrix.size()) == 0)
        return res;

    int r1 = 0, r2 = size - 1;
    int c1 = 0, c2 = matrix[0].size() - 1;

    while (r1 <= r2 && c1 <= c2)
    {
        for (int c = c1; c <= c2; c++)
            res.push_back(matrix[r1][c]);
        for (int r = r1 + 1; r <= r2; r++)
            res.push_back(matrix[r][c2]);

        if (r1 < r2 && c1 < c2)
        {
            for (int c = c2 - 1; c > c1; c--)
                res.push_back(matrix[r2][c]);
            for (int r = r2; r > r1; r--)
                res.push_back(matrix[r][c1]);
        }
        r1++;
        r2--;
        c1++;
        c2--;
    }

    return res;
    }



tgs
7天前
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) {}
};

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
    ListNode *r = new ListNode();
    ListNode *s = r;

    while (l1 && l2)
    {
        if (l1->val <= l2->val)
        {
            s->next = l1;
            l1 = l1->next;
        }
        else
        {
            s->next = l2;
            l2 = l2->next;
        }
        s = s->next;
    }
    if (l1)
        s->next = l1;
    else
        s->next = l2;

    return r->next;
}



活动打卡代码 AcWing 35. 反转链表

tgs
7天前
ListNode *reverseListIteratively(ListNode *head)
{
    ListNode *current = head;
    ListNode *prev = NULL;  // first node of new list 
    ListNode *next = NULL;  

    while (current != NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}
ListNode *reverseListRecursively(ListNode *head)
{
    if (!head || !head->next)
        return head;
    ListNode *newhead = reverseListRecursively(head->next);
    head->next->next = head;
    head->next = NULL;
    return newhead;
}




tgs
17天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        ListNode* p = pListHead, * q = pListHead;
        int i = 1;
        while (q && q->next && i < k) {
            q = q->next;
            i++;
        }
        if (i < k) return NULL;
        while (q->next) {
            p = p->next;
            q = q->next;
        }
        return p;
    }
};



tgs
17天前
  • 维护有序性
class Solution {
public:
    void reOrderArray(vector<int> &array) {
    int i, j, n = array.size();
    for (i = 0; i < n - 1; i++) 
        for (j = i + 1; j > 0; j--) 
            if (array[j] % 2 == 1 && array[j - 1] % 2 == 0) 
                swap(array[j], array[j - 1]);
    }
};
  • 不维护有序性
class Solution {
public:
    void reOrderArray(vector<int> &array) {
         int l = 0, r = array.size() - 1;
         while (l < r) {
             while (l < r && array[l] % 2 == 1) l ++ ;
             while (l < r && array[r] % 2 == 0) r -- ;
             if (l < r) swap(array[l], array[r]);
         }
    }
};





tgs
17天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* p = dummy;
        while (p->next) {
            ListNode* q = p->next;
            while (q->next && q->val == q->next->val) 
                q = q->next;
            if (p->next == q) p = p->next;
            else p->next = q->next;
        }
        return dummy->next;
    }
};