头像

zymTokyoTech




离线:8小时前


最近来访(7)
用户头像
itdef
用户头像
Lightning_98
用户头像
AL_98
用户头像
伏羲
用户头像
jinyc
用户头像
封禁用户
用户头像
Peter_5


zymTokyoTech
8小时前
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int>s1, smin;
    MinStack() {

    }

    void push(int x) {
        s1.push(x);
        if(smin.empty() || smin.top() >= x)
            smin.push(x);
    }

    void pop() {
        if(s1.size())
        {
            if(s1.top() == smin.top())  smin.pop();
            s1.pop(); 
        }
    }

    int top() {
        if(s1.size())
            return s1.top();
    }

    int getMin() {
        if(smin.size())
            return smin.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */



zymTokyoTech
12小时前
class Solution {
public:
    //按照右下左上的顺序遍历矩阵(方格),出界或者遍历到之前遍历过的点时更改方向
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> res;
        if(matrix.size() == 0) return res;

        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> st(m, vector<bool>(n, false));
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        int x = 0, y = 0, d = 1; //x,y起始点,d为向量数组下标,一开始向右走;

        //遍历所有方格
        for(int i = 0; i < m * n; i++)
        {   
            res.push_back(matrix[x][y]);
            st[x][y] = true;


            int a = x + dx[d], b = y + dy[d];

            //判断是否需要更改方向
            if(a < 0 || a >= m || b < 0 || b >= n || st[a][b])
            {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }

        return res;
    }
};


活动打卡代码 AcWing 39. 对称的二叉树

zymTokyoTech
13小时前
/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        return isSymmetric(root, root);
    }

    bool isSymmetric(TreeNode *root1, TreeNode *root2)
    {   
        //两个结点都是null返回true
        if(!root1 && !root2)    return true;
        //只有一个结点是null,不对称
        if(!root1 || !root2)    return false;

        if(root1->val != root2->val)    return false;

        return isSymmetric(root1->left, root2->right) && isSymmetric(root1->right, root2->left);
    }
};


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

zymTokyoTech
14小时前
/**
 * 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:
    void mirror(TreeNode* root) {
        if(!root)   return;
        if(!root->left && !root->right) return;

        TreeNode *temp = root->left;
        root->left = root->right;
        root->right = temp;

        mirror(root->left);
        mirror(root->right);
    }
};


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

zymTokyoTech
14小时前
/**
 * 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:
    bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot1 || !pRoot2) return false;
        if(isPart(pRoot1, pRoot2))  return true;
        else return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
    }

    bool isPart(TreeNode* p1, TreeNode* p2)
    {   
        //p2这棵树已经遍历到叶结点,说明所有点都匹配,是子树。
        if(!p2) return true;
        //当p2还有结点时,p1已经没有了||p1与p2的值不一样 ->不是子树
        if(!p1 || p1->val != p2->val)   return false;  

        //p1和p2相等时,递归判断p1和p2的左右子树是否相等
        return isPart(p1->left, p2->left) && isPart(p1->right, p2->right);
    }
};



zymTokyoTech
14小时前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if(!l1 || !l2)   return 0;
        ListNode *dummy = new ListNode(0);
        ListNode *curr = dummy;

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

        curr->next = (l1 ? l1 : l2);
        return dummy->next;
    }
};


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

算法1(迭代)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr;
        ListNode *curr = head;
        while(curr)
        {
            ListNode *next = curr ->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

算法2(递归)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //最小情况
        if(head == nullptr || head->next == nullptr)    return head;
        //将大问题分解成子问题
        ListNode *tail = reverseList(head->next);

        //处理子问题
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }


};



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        auto fast = head;
        auto slow = head;
        do
        {
            if(fast == nullptr || fast->next == nullptr)    return nullptr;
            fast = fast->next->next;
            slow = slow->next;
        }while(slow != fast);

        fast = head;
        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};



/**
 * 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) {
        int n = 0;
        auto p = pListHead;
        while(p)
        {
            n++;
            p = p->next;
        }
        if(k > n) return nullptr;


        for(int i = 0; i <  n - k; i ++)
            pListHead = pListHead->next;

        return pListHead;
    }
};



class Solution {
public:
    void reOrderArray(vector<int> &array) { 
        if(array.size() == 0)   return;
        int l = 0, r = array.size() -1;
        while(l < r)
        {
         while(l < r && array[l] % 2) l++;
         while(l < r && array[r] % 2 == 0) r--;

         if(l < r)  swap(array[l], array[r]);
        }
    }
};