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

[13520280]

[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

[toannv]

[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

[toannv]

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

[13520376]

void convertTreeToArr(struct TreeNode* root, int 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 TreeNode* root) {
    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;
} 

[14520052]

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root)
        {
            if (!root->left&&!root->right)
                return 1;
            stack<struct TreeNode*> S;
            struct TreeNode* p,* 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);
                }
                
                p = S.top(); S.pop();
                
                if (temp&&p)
                    if (temp->val>=p->val)
                        return 0;
                temp = p;
          }while (!S.empty()||temp->right);
      }
      return 1;
    }
}; 

Done!

[toannv]

Done!

Lâu lắm mới thấy bạn Bảo post bài

[14520674]

runtime: 12ms!:sweat:

int max(int a, int b){
    if (a>b)
        return a;
    return b;
}
int min(int a, int b){
    if (a>b)
        return b;
    return a;
}
int Max(struct TreeNode* root){
    if(root){
        int mx=root->val;
        if(root->left)
            mx= max(mx, Max(root->left));
        if(root->right)
            mx= max(mx, Max(root->right));
        return mx;
    }
}
int Min(struct TreeNode* root){
    if(root){
        int mn=root->val;
        if(root->left)
            mn= min(mn, Min(root->left));
        if(root->right)
            mn= min(mn, Min(root->right));
        return mn;
    }
    return 0;
}
bool isValidBST(struct TreeNode* root) {
    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);
} 

[13521005]

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

int getLeft(struct TreeNode* root);
int getRight(struct TreeNode* root);
bool isValidBST(struct TreeNode* root) {
    
    if (root == NULL)
        return true;
    int left, right;
    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 TreeNode* root)
{
    root = root->left;
    while (root->right != NULL)
    {
        root = root->right;
    }
    return root->val;
}

int getRight(struct TreeNode* root)
{
    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

[14520922]

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

giúp em sửa bài này thầy ơi

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

[14520922]

bài Happy number

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

[14520769]

[MENTION=12238]toannv[/MENTION]: thầy xem giúp em

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