Announcement

Collapse
No announcement yet.

[Lớp thuật toán hè 2015] Tài liệu và trao đổi buổi 4

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts
    14520769
    Lã Hoàng Thái Sơn

  • 14520769
    replied
    [MENTION=12238]toannv[/MENTION]: thầy xem giúp em
    PHP Code:
    class Solution {
    public:
        
    bool isValidBST(TreeNode *root
        {
            
    TreeNode *bridge, *cur, *prev;
            
    cur root;
            while (
    cur)
            {
                if (
    cur->left)
                {
                    
    bridge cur->left;
                    while (
    bridge->right && bridge->right != cur)
                    {
                        
    bridge bridge->right;
                    }
                    if (!
    bridge->right)
                    {
                        
    bridge->right cur;
                        
    cur cur->left;
                    }
                    else
                    {
                        
    bridge->right NULL;
                        if (!
    cur->right)
                            return 
    true;
                        
    prev cur;
                        
    cur cur->right;
                        if (
    prev->val >= cur->val)
                            return 
    false;
                    }
                }
                else
                {
                    if (!
    cur->right)
                        return 
    true;
                    
    prev cur;
                    
    cur cur->right;
                    if (
    prev->val >= cur->val)
                        return 
    false;
                }
            }
            return 
    true;
        }
    }; 

    Leave a comment:

  • 14520922
    Trần Lê Trọng Thức

  • 14520922
    replied
    bài Happy number

    PHP Code:
    class Solution {
    public:
        
    bool isHappy(int n) {
            
    int result n;
            while (
    result != 1)
            {
                
    result sumOfDigits(result);
                if (
    result <= && result >= && result != 1)
                return 
    false;
            }
            if (
    result == 1)
                    return 
    true;
        }
        
        
    int sumOfDigits(int n)
        {
            
    vector <intdigit;
            
    int sum 0;
            while (
    0)
            {
                
    digit.push_back(10);
                
    /=10;
            }
            for (
    int i 0digit.size();i++)
            {
                
    sum += digit[i]*digit[i];
            }
            return 
    sum;
        }
    }; 

    Leave a comment:

  • 14520922
    Trần Lê Trọng Thức

  • 14520922
    replied
    bài https://leetcode.com/problems/4sum/

    giúp em sửa bài này thầy ơi
    Code:
    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>> result;
            sort(nums.begin(), nums.end());
            
            for(int i = 0; i < nums.size() - 4;i++)
            {
                int sum = nums[i];
                vector <int> temp;
                temp.push_back(nums[i]);
                int counter =1;
                for (int j = i+1; j <= nums.size() - 4;j++)
                {
                    counter ++;
                    sum += nums[j];
                    temp.push_back(nums[i+j]);
                    if (sum == target && counter == 4)
                    {
                        result.push_back(temp);
                    }
                }
            }
            return result;
        }
    };

    Leave a comment:

  • 13521005
    Hồ Hoàng Tùng

  • 13521005
    replied
    bài Validate Binary Search Tree
    có thê làm theo kiểu đệ quy thông thường, thời gian 8ms
    sai lầm thường gặp là hiểu sai định nghĩa của BST
    - Tất cả phần tử bên trái phải nhỏ hơn nút gốc
    thông thường các bạn chỉ kiểm tra phần từ left của nút gốc rồi đệ quy, đúng ra phải kiểm tra phần tử cực phải của phần tử trái của nút gốc mới đúng

    PHP Code:
    int getLeft(struct TreeNoderoot);
    int getRight(struct TreeNoderoot);
    bool isValidBST(struct TreeNoderoot) {
        
        if (
    root == NULL)
            return 
    true;
        
    int leftright;
        if (
    root->left != NULL)
        {
            
    left getLeft(root);
            if (
    left >= root->val)
                return 
    false;
        }
        if (
    root->right != NULL)
        {
            
    right getRight(root);
            if (
    right <= root->val)
                return 
    false;
        }

        
    bool isValid_left isValidBST(root->left);
        
    bool isValid_right isValidBST(root->right);
        return (
    isValid_left isValid_right);
    }


    int getLeft(struct TreeNoderoot)
    {
        
    root root->left;
        while (
    root->right != NULL)
        {
            
    root root->right;
        }
        return 
    root->val;
    }

    int getRight(struct TreeNoderoot)
    {
        
    root root->right;
        while (
    root->left != NULL)
        {
            
    root root->left;
        }
        return 
    root->val;

    đặt tên biến hơi khó hiểu mọi người thông cảm

    Leave a comment:

  • 14520674
    Thái Viết Phong

  • 14520674
    replied
    runtime: 12ms!:sweat:
    PHP Code:
    int max(int aint b){
        if (
    a>b)
            return 
    a;
        return 
    b;
    }
    int min(int aint b){
        if (
    a>b)
            return 
    b;
        return 
    a;
    }
    int Max(struct TreeNoderoot){
        if(
    root){
            
    int mx=root->val;
            if(
    root->left)
                
    mxmax(mxMax(root->left));
            if(
    root->right)
                
    mxmax(mxMax(root->right));
            return 
    mx;
        }
    }
    int Min(struct TreeNoderoot){
        if(
    root){
            
    int mn=root->val;
            if(
    root->left)
                
    mnmin(mnMin(root->left));
            if(
    root->right)
                
    mnmin(mnMin(root->right));
            return 
    mn;
        }
        return 
    0;
    }
    bool isValidBST(struct TreeNoderoot) {
        if(
    root==NULL)
             return 
    true;
            
    bool res=true;
        if(
    root->left)
             
    res Max(root->left) < root->val;
        if(
    root->right)
             
    res res && Min(root->right) > root->val;
         return 
    res && isValidBST(root->left)
            && 
    isValidBST(root->right);

    14520674
    Thái Viết Phong
    Last edited by 14520674; 15-07-2015, 12:35.

    Leave a comment:

  • toannv
    Trưởng phòng CôngTác SinhViên

  • toannv
    replied
    Originally posted by 14520052 View Post
    Done!
    Lâu lắm mới thấy bạn Bảo post bài

    Leave a comment:

  • 14520052
    Lâm Minh Bảo

  • 14520052
    replied
    PHP Code:
    class Solution {
    public:
        
    bool isValidBST(TreeNoderoot) {
            if (
    root)
            {
                if (!
    root->left&&!root->right)
                    return 
    1;
                
    stack<struct TreeNode*> S;
                
    struct TreeNodep,* temp;
        
                
    S.push(root);
                while (
    S.top()->left)
                    
    S.push(S.top()->left);
                
    temp S.top(); S.pop();
                do
                {
                    if (
    temp->right)
                    {
                        
    S.push(temp->right);
                        while (
    S.top()->left)
                            
    S.push(S.top()->left);
                    }
                    
                    
    S.top(); S.pop();
                    
                    if (
    temp&&p)
                        if (
    temp->val>=p->val)
                            return 
    0;
                    
    temp p;
              }while (!
    S.empty()||temp->right);
          }
          return 
    1;
        }
    }; 
    Done!

    Leave a comment:

  • 13520376
    Hoàng Văn Kế

  • 13520376
    replied
    PHP Code:
    void convertTreeToArr(struct TreeNoderootint temps[100000], int index)
    {
        if (
    root==NULL) return;
        
    convertTreeToArr(root->left,temps,index);
        
    temps[*index]=root->val; (*index)++;
        
    convertTreeToArr(root->right,temps,index);
    }

    bool isValidBST(struct TreeNoderoot) {
        
    int i,index=0,temps[100000];
        
    convertTreeToArr(root,temps,&index);
        for(
    i=1;i<index;i++)
        {
            if (
    temps[i]<=temps[i-1]) return false;
        }
        return 
    true;

    Leave a comment:

  • toannv
    Trưởng phòng CôngTác SinhViên

  • toannv
    replied
    Lần đầu tiên trong giờ học, chưa có bạn nào làm ra được bài 1 :shot:. Lý do:
    - Các bạn chưa rõ bản chất và cơ chế của đệ qui
    ....
    Cố gắng làm và post lên nghe các bạn

    Leave a comment:

  • toannv
    Trưởng phòng CôngTác SinhViên

  • toannv
    replied
    [Lớp thuật toán hè 2015] Tài liệu và trao đổi buổi 4

    Hôm nay phòng máy sẽ mở cửa lúc 9:30 và học chính thức lúc 10:00 nhé các bạn.

    Thông tin thêm về cơ hội đi Hà Nội ngay sau thi giữa học kỳ 1 năm đến http://www.olp.vn/tin-tuc/olympic-ac...micpchanoi2015
    Attached Files
    toannv
    Trưởng phòng CôngTác SinhViên
    Last edited by toannv; 14-07-2015, 10:24.

    Leave a comment:

  • 13520280
    Đinh Quang Hình

  • [Lớp thuật toán hè 2015] Tài liệu và trao đổi buổi 4

    [STL Part 2]
    Gửi các bạn tài liệu tham khảo phần STL và slide trình bày ngày mai:
    [1] Tài liệu tham khảo: https://goo.gl/SDqbie
    [2] Slide trình bày:
    - .exe and .tar https://goo.gl/RY8QPY
    - .pdf: https://goo.gl/YjGYem

LHQC

Collapse
Working...
X