Announcement

Collapse
No announcement yet.

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

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts
    toannv
    Trưởng phòng CôngTác SinhViên

  • toannv
    replied
    Originally posted by 14520007 View Post
    Bài 189: Rotate an array of n elements to the right by k steps.

    For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

    Note:
    Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

    Code:
    void rotate(int* nums, int numsSize, int k) {
        if( k==0 || k==numsSize)
            return;
        int i=0;
        int count=0;
        int prev = nums[0];
        while (count < numsSize)
        {
            int j = ( i + k ) % numsSize;
            
            int temp = nums[j];
            nums[j] = prev;
            prev = temp;
            
            i = j;
            count ++;
        }
    }
    HELP: làm sao để mình sữa lỗi nhập bên dưới::unhappy: Thầy và các bạ giúp em!!!
    Input:
    [1,2,3,4,5,6], 2
    Output:
    [3,2,1,4,1,6]
    Expected:
    [5,6,1,2,3,4]

    Em hiểu sai đề rồi. Bài này Tôi có nói phương pháp "xoay gương" rồi

    Leave a comment:

  • 13521005
    Hồ Hoàng Tùng

  • 13521005
    replied
    Originally posted by 14520769 View Post
    khi j chạy tới 1 (tức nums[j] = -3) anh đảo lộn lại trật tự result (result[0] = index) thì nó mới ra được kết quả. Em nghĩ vậy không biết đúng không
    đúng rồi. còn phải đảo trật tự lại nữa.
    vậy là ăn may rồi :sweat:

    Leave a comment:

  • 14520769
    Lã Hoàng Thái Sơn

  • 14520769
    replied
    Originally posted by 13521005 View Post
    PHP Code:
    if (index <= 0)
    continue;
    if (
    j+== index)
    continue; 
    cái này em thấy không thỏa đáng, vì index của anh đâu có bao giờ lưu giá trị âm đâu mà continue, j cũng z, nếu như j chạy tuyến tính từ 0 -> n-2 thì gặp 1 cái chắc là nó cũng ra rồi cũng không cần kiểm tra điều kiện nữa

    cái vd của em sai thiệt (tại không để ý kĩ cái code ), nhưng mà vd của anh thì có vẻ như nó sẽ không ra đáp án được cho bài này, vì với vòng for dùng để nhập hash con vị trí của con -3 đã bị chèn bởi vị trí con 3 rồi nên không có cách nào tìm lại được, trừ khi là ở vòng
    PHP Code:
    for (int j 0numsSize 1j++)
        {
            
    target nums[j];

            if (
    >= 0)
                
    index hashtable[t];
            else
                
    index =  - hashtable[-t];
            if ((
    1) >= index)
                continue;
            
    result[0] = 1;
            
    result[1] = index;
                
            return 
    result;
        } 
    khi j chạy tới 1 (tức nums[j] = -3) anh đảo lộn lại trật tự result (result[0] = index) thì nó mới ra được kết quả. Em nghĩ vậy không biết đúng không

    Leave a comment:

  • 14520007
    Ngô Duy Ân

  • 14520007
    replied
    Bài 189: Rotate an array of n elements to the right by k steps.

    For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

    Note:
    Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

    Code:
    void rotate(int* nums, int numsSize, int k) {
        if( k==0 || k==numsSize)
            return;
        int i=0;
        int count=0;
        int prev = nums[0];
        while (count < numsSize)
        {
            int j = ( i + k ) % numsSize;
            
            int temp = nums[j];
            nums[j] = prev;
            prev = temp;
            
            i = j;
            count ++;
        }
    }
    HELP: làm sao để mình sữa lỗi nhập bên dưới::unhappy: Thầy và các bạ giúp em!!!
    Input:
    [1,2,3,4,5,6], 2
    Output:
    [3,2,1,4,1,6]
    Expected:
    [5,6,1,2,3,4]

    Leave a comment:

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

  • toannv
    replied
    Originally posted by 14520979 View Post
    phòng nào vậy thầy? em không thấy đề cập đến địa điểm.
    Phòng của ... buổi 1,2 đó em: http://forum.uit.edu.vn/threads/55625

    Leave a comment:

  • 14520052
    Lâm Minh Bảo

  • 14520052
    replied
    PHP Code:
    using namespace std;
    class 
    Solution {
    public:
        
    vector<inttwoSum(vector<int>& numsint target) {
            
    map<int,intA;
            
    int i,n,x;
            for (
    i=0n=nums.size(); i<n;i++)
                
    A[nums[i]] = i;
            for (
    i=0;;i++)
            {
                
    target nums[i];
                if (
    A.find(x)!=A.end()&&A.find(x)->second!=i)
                    break;
            }
            
    vector<intresult;
            
    result.push_back(i+1);
            
    result.push_back(A.find(x)->second+1);
            return 
    result;
        }
    }; 
    Code C++ dùng STL

    Leave a comment:

  • 14520979
    Trần Khánh Toàn

  • 14520979
    replied
    Originally posted by toannv View Post
    Mai học lúc 10:00 nhé các bạn!
    Phòng máy sẽ mở cửa lức 9:30
    phòng nào vậy thầy? em không thấy đề cập đến địa điểm.

    Leave a comment:

  • truonganpn
    Campus staff

  • truonganpn
    replied
    Test bài này có vẻ cho số nhỏ nên hầu hết đều dùng mảng đánh dấu để hash nhỉ. Có ai nghĩ thử trường hợp trong mảng input có số nào đó xêm xêm... 1 tỷ xem

    Leave a comment:

  • 13521005
    Hồ Hoàng Tùng

  • 13521005
    replied
    Originally posted by 14520769 View Post
    cái này em thấy k được anh ơi, lỡ mảng {-3, 3, 5} target = 2 thì sao
    cảm ơn bạn đã quan tâm bài của mình
    bạn nhận định đúng vấn đề nhưng ví dụ của bạn chưa chính xác
    ở ví dụ của bạn nếu j = 0
    thì t = 5 => hash[5] = 3 => return (j+1 và hash[5]) tức (1; 3) vẫn thoả
    bạn thử kiểm tra lại với bộ {5;-3;3} target = 2 xem
    sau đó hãy kiểm tra hộ mình nếu mình sửa đoạn
    PHP Code:
    if (j+> = index)
    continue; 
    thành
    PHP Code:
    if (index <= 0)
    continue;
    if (
    j+== index)
    continue; 
    cảm ơn bạn :happy:

    mẹo ở đây là nếu trong mảng ban đầu có 2 số ngịch đảo nhau, thì mảng hash chỉ lưu được số ở sau.
    nhưng ta vẫn có thể kiểm tra số còn lại với vai trò là số thứ nhất (nums[j])
    13521005
    Hồ Hoàng Tùng
    Last edited by 13521005; 06-07-2015, 19:10.

    Leave a comment:

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

  • toannv
    replied
    Mai học lúc 10:00 nhé các bạn!
    Phòng máy sẽ mở cửa lức 9:30

    Leave a comment:

  • 14520769
    Lã Hoàng Thái Sơn

  • 14520769
    replied
    Originally posted by 13521005 View Post
    ở đây mình giải quyết trường hợp số âm khác với mọi người
    ở mảng hash mình lưu chỉ số của các giá trị trong bảng nums
    nếu là trị là âm thì giá trị trong bảng hash cũng là âm.
    ví dụ mảng nums là 4 -3 6
    thì mảng hash là
    hash[4] = 1
    hash[3] = -2
    hash[6] = 3
    những phần tử khác của hash bằng 0

    Mình cảm thấy code này khá ngắn gọn và rất dễ đọc
    PHP Code:
    inttwoSum(intnumsint numsSizeint target) {
        
        
    inthashtable = (int*) calloc (sizeof(int),50000);
        
    intresult = (int*) calloc (sizeof(int), 2);
        
    int  tindex;
        
        for (
    int i 0numsSize i++)
        {
            if (
    nums[i] >= 0)
                
    hashtable[nums[i]] = 1;
            else
                
    hashtable[-nums[i]] = - (1);
        }

        for (
    int j 0numsSize 1j++)
        {
            
    target nums[j];

            if (
    >= 0)
                
    index hashtable[t];
            else
                
    index =  - hashtable[-t];
            if ((
    1) >= index)
                continue;
            
    result[0] = 1;
            
    result[1] = index;
                
            return 
    result;
        }

    cái này em thấy k được anh ơi, lỡ mảng {-3, 3, 5} target = 2 thì sao

    Leave a comment:

  • 14520979
    Trần Khánh Toàn

  • 14520979
    replied
    PHP Code:
    class Solution {
    public:
       
    vector<inttwoSum(vector<int>& aint tong
        {
            
    vector<intc;
            
    int *b=new int[66000];
            for(
    long i=0;i<a.size();i++) b[a[i]+33000]=i+1;
            for(
    long i=0;i<a.size();i++)
            if( 
    b[tong-a[i]+33000]>=&& b[tong-a[i]+33000]!=i+1)
            {
                
    c.push_back(i+1);
                
    c.push_back(b[tong-a[i]+33000]);
                return 
    c;
            }
        }
    }; 

    Leave a comment:

  • 13521005
    Hồ Hoàng Tùng

  • 13521005
    replied
    ở đây mình giải quyết trường hợp số âm khác với mọi người
    ở mảng hash mình lưu chỉ số của các giá trị trong bảng nums
    nếu là trị là âm thì giá trị trong bảng hash cũng là âm.
    ví dụ mảng nums là 4 -3 6
    thì mảng hash là
    hash[4] = 1
    hash[3] = -2
    hash[6] = 3
    những phần tử khác của hash bằng 0

    Mình cảm thấy code này khá ngắn gọn và rất dễ đọc
    PHP Code:
    inttwoSum(intnumsint numsSizeint target) {
        
        
    inthashtable = (int*) calloc (sizeof(int),50000);
        
    intresult = (int*) calloc (sizeof(int), 2);
        
    int  tindex;
        
        for (
    int i 0numsSize i++)
        {
            if (
    nums[i] >= 0)
                
    hashtable[nums[i]] = 1;
            else
                
    hashtable[-nums[i]] = - (1);
        }

        for (
    int j 0numsSize 1j++)
        {
            
    target nums[j];

            if (
    >= 0)
                
    index hashtable[t];
            else
                
    index =  - hashtable[-t];
            
    /*if ((j + 1) >= index)
                continue;*/
            
    if (index <=0)
                continue;
            if (
    index == 1)
                continue;
            
    result[0] = 1;
            
    result[1] = index;
                
            return 
    result;
        }

    13521005
    Hồ Hoàng Tùng
    Last edited by 13521005; 06-07-2015, 19:03.

    Leave a comment:

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

  • toannv
    replied
    Originally posted by 14520979 View Post
    8ms, con số 66000 hình như là có thể cải tiến nhưng e chịu??
    PHP Code:
    class Solution {
    public:
       
    vector<inttwoSum(vector<int>& aint tong
    {
        
    long i,t;
        
    int *b=new int[66000];
        for(
    i=0;i<a.size();i++)
        {
            if(
    a[i]>=0b[a[i]]=i+1;
            else 
    b[a[i]+66000]=i+1;
        }
        for(
    i=0;i<a.size();i++)
        {
            
    t=tong-a[i];
            if((
    t>=&& b[t]>=&& b[t]!=i+1)||(t<&& b[t+66000]>=&& b[t+66000]!=i+1))
            {
                
    vector<intc;
                
    c.push_back(i+1);
                if(
    t>=0c.push_back(b[t]);
                else 
    c.push_back(b[t+66000]);
                return 
    c;
            }
        }
    }
    }; 
    Đã dùng STL thì em dùng khai báo động luôn đi.

    Leave a comment:

  • 14520979
    Trần Khánh Toàn

  • 14520979
    replied
    8ms, con số 66000 hình như là có thể cải tiến nhưng e chịu??
    PHP Code:
    class Solution {
    public:
       
    vector<inttwoSum(vector<int>& aint tong
    {
        
    long i,t;
        
    int *b=new int[66000];
        for(
    i=0;i<a.size();i++)
        {
            if(
    a[i]>=0b[a[i]]=i+1;
            else 
    b[a[i]+66000]=i+1;
        }
        for(
    i=0;i<a.size();i++)
        {
            
    t=tong-a[i];
            if((
    t>=&& b[t]>=&& b[t]!=i+1)||(t<&& b[t+66000]>=&& b[t+66000]!=i+1))
            {
                
    vector<intc;
                
    c.push_back(i+1);
                if(
    t>=0c.push_back(b[t]);
                else 
    c.push_back(b[t+66000]);
                return 
    c;
            }
        }
    }
    }; 

    Leave a comment:

LHQC

Collapse
Working...
X