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

[toannv]

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.

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

[13521005]

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:

[14520769]

if (index <= 0)
continue;
if (j+1 == 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

for (int j = 0; j < numsSize - 1; j++)
    {
        t = target - nums[j];

        if (t >= 0)
            index = hashtable[t];
        else
            index =  - hashtable[-t];
        if ((j + 1) >= index)
            continue;
        result[0] = j + 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

[14520007]

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.

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]

[toannv]

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

[14520052]

using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> A;
        int i,n,x;
        for (i=0, n=nums.size(); i<n;i++)
            A[nums[i]] = i;
        for (i=0;;i++)
        {
            x = target - nums[i];
            if (A.find(x)!=A.end()&&A.find(x)->second!=i)
                break;
        }
        vector<int> result;
        result.push_back(i+1);
        result.push_back(A.find(x)->second+1);
        return result;
    }
}; 

Code C++ dùng STL

[14520979]

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.

[truonganpn]

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

[13521005]

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

if (j+1 > = index)
continue; 

thành

if (index <= 0)
continue;
if (j+1 == 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])

[toannv]

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

[14520769]

ở đâ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

int* twoSum(int* nums, int numsSize, int target) {
    
    int* hashtable = (int*) calloc (sizeof(int),50000);
    int* result = (int*) calloc (sizeof(int), 2);
    int  t, index;
    
    for (int i = 0; i < numsSize ; i++)
    {
        if (nums[i] >= 0)
            hashtable[nums[i]] = i + 1;
        else
            hashtable[-nums[i]] = - (i + 1);
    }

    for (int j = 0; j < numsSize - 1; j++)
    {
        t = target - nums[j];

        if (t >= 0)
            index = hashtable[t];
        else
            index =  - hashtable[-t];
        if ((j + 1) >= index)
            continue;
        result[0] = j + 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

[14520979]

class Solution {
public:
   vector<int> twoSum(vector<int>& a, int tong) 
    {
        vector<int> c;
        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]>=1 && b[tong-a[i]+33000]!=i+1)
        {
            c.push_back(i+1);
            c.push_back(b[tong-a[i]+33000]);
            return c;
        }
    }
}; 

[13521005]

ở đâ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

int* twoSum(int* nums, int numsSize, int target) {
    
    int* hashtable = (int*) calloc (sizeof(int),50000);
    int* result = (int*) calloc (sizeof(int), 2);
    int  t, index;
    
    for (int i = 0; i < numsSize ; i++)
    {
        if (nums[i] >= 0)
            hashtable[nums[i]] = i + 1;
        else
            hashtable[-nums[i]] = - (i + 1);
    }

    for (int j = 0; j < numsSize - 1; j++)
    {
        t = target - nums[j];

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

[toannv]

8ms, con số 66000 hình như là có thể cải tiến nhưng e chịu??

class Solution {
public:
   vector<int> twoSum(vector<int>& a, int tong) 
{
    long i,t;
    int *b=new int[66000];
    for(i=0;i<a.size();i++)
    {
        if(a[i]>=0) b[a[i]]=i+1;
        else b[a[i]+66000]=i+1;
    }
    for(i=0;i<a.size();i++)
    {
        t=tong-a[i];
        if((t>=0 && b[t]>=1 && b[t]!=i+1)||(t<0 && b[t+66000]>=1 && b[t+66000]!=i+1))
        {
            vector<int> c;
            c.push_back(i+1);
            if(t>=0) c.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.

[14520979]

8ms, con số 66000 hình như là có thể cải tiến nhưng e chịu??

class Solution {
public:
   vector<int> twoSum(vector<int>& a, int tong) 
{
    long i,t;
    int *b=new int[66000];
    for(i=0;i<a.size();i++)
    {
        if(a[i]>=0) b[a[i]]=i+1;
        else b[a[i]+66000]=i+1;
    }
    for(i=0;i<a.size();i++)
    {
        t=tong-a[i];
        if((t>=0 && b[t]>=1 && b[t]!=i+1)||(t<0 && b[t+66000]>=1 && b[t+66000]!=i+1))
        {
            vector<int> c;
            c.push_back(i+1);
            if(t>=0) c.push_back(b[t]);
            else c.push_back(b[t+66000]);
            return c;
        }
    }
}
};