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

  • [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
    Khi tất cả những cái khác đã mất đi thì tương lai vẫn còn

    Bové

  • #2
    [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
    Last edited by toannv; 14-07-2015, 10:24.

    Comment


    • #3
      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

      Comment


      • #4
        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;

        Comment


        • #5
          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!

          Comment


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

            Comment


            • #7
              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);

              Last edited by 14520674; 15-07-2015, 12:35.
              PHP Code:
              Full nameThai Viet Phong
              Facebook
              www.facebook.com/ThaiVietPhong.ITM
              Email
              thaivietphong.net@gmail.com 
              Tìm trước khi hỏi bạn sẽ giỏi hơn mỗi khi tìm

              Comment


              • #8
                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

                Comment


                • #9
                  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;
                      }
                  };

                  Comment


                  • #10
                    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;
                        }
                    }; 

                    Comment


                    • #11
                      [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;
                          }
                      }; 

                      Comment

                      LHQC

                      Collapse
                      Working...
                      X