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

[toannv]

Tài liệu sơ bộ buổi 1

[13520376]

Đây là code của mình. 20ms

int* twoSum(int* nums, int numsSize, int target) {
    int* results;
    int binArr[40000];
    results = (int*)calloc(sizeof(int),2);
    int i,j,t;
    target+=2000;
    for (i=0;i<numsSize;i++)
    {
        nums[i]+=1000;
        binArr[nums[i]]=1;
    }
    for (i=0;i<numsSize-1;i++)
    {
        t=target-nums[i];
        if (binArr[t]==1)
        {
            results[0]=i+1;
            for (j=i+1;j<numsSize;j++)
            {
                if (nums[j]==t)
                {
                    results[1]=j+1;
                    return results;
                }
            }
        }
    }
    return results;
} 

[13520045]

Code tham khảo bài tập buổi 1

#define MAX 1000
int* twoSum(int* nums, int numsSize, int target) {
    int* results;// mảng lưu kết quả
    int i,j;
    int temp[50000]; // mảng lưu số lượng
    results= (int*)calloc(sizeof(int),2);
    for(i=0; i<5000; i++) // khởi tạo số lượng = 0
    {
        temp[i]=0;
    }
    for(i=0; i<numsSize; i++)
    {
        temp[nums[i]+MAX]+=1; //mảng lưu số lượng phần tử từng nums[i]
    }
    for(i=0; i<numsSize-1; i++){
        j=target-nums[i]; 
        if(temp[j+MAX]==1&& nums[i]!=j)  // tồn tại số hạng 2 và không trùng số hạng 1
        {
            results[0]=i+1;
            
            for(int k=i+1;k<numsSize;k++)
            {
                if(nums[k]==j) results[1]=k+1;
            }
            
            return results;
        }
        else 
        if(temp[j+MAX]>1) // tồn tại nhiều số hạng 2 thì chọn số đầu tiên
        {
            results[0]=i+1;
            for(int k=i+1;k<numsSize;k++)
            {
                if(nums[k]==j) results[1]=k+1;
            }
            return results;
        }
    }
    
} 

[13521043]

đây là code của mình, ý tưởng cơ bản là lưu vị trí của pt trong để vô 1 mảng, pt không có trong đề sẽ không có giá trị (mình lấy giá trị 0), vậy chổ nào khác 0 mình mới xét.

code chạy 4ms

int* twoSum(int* nums, int numsSize, int target) {
    int* results;
    int i;
    results = (int*)calloc(sizeof(int), 2);
    
    int max = 100000;
    
    int j;
    int* index;
    index = (int*)calloc(sizeof(int), max); //khởi tạo mảng lưu vị trí
    
    //Ban đầu mình khởi tạo cho giá trị = 0
    //Nhưng search trên mạng thấy, mình sử dụng calloc thì nó tự động khởi tạo 0
    //Nếu khởi tạo code mình chạy 12ms, bỏ đi còn 4ms
    /*
    for(i = 0; i < max; i++)
    {
        index[i] = 0;
    }
    */
    
    //Đề nó nói ko bắt đầu từ 0, nên lưu vị trí + 1
    for(i = 0; i < numsSize; i++)
    {
        index[nums[i] + max / 2] = i + 1;
    }
    
    for(i = 0; i < numsSize; i++)
    {
        int t;
        t = target - nums[i];
        //Kiểm tra xem số t có giá trị trong index không, và khác i hiện tại
        if(index[t + max / 2] != 0 && index[t + max / 2] != i + 1)
        {
            results[0] = i + 1;
            results[1] = index[t + max / 2];
            
            return results;
        }
    }
} 

[toannv]

Các bạn có thể coi thêm một bài về mảng.

[toannv]

Các bạn làm bài bị lỗi mà sửa không được cũng post lên đây nhé.

[toannv]

đây là code của mình, ý tưởng cơ bản là lưu vị trí của pt trong để vô 1 mảng, pt không có trong đề sẽ không có giá trị (mình lấy giá trị 0), vậy chổ nào khác 0 mình mới xét.

code chạy 4ms

int* twoSum(int* nums, int numsSize, int target) {
    
    //Đề nó nói ko bắt đầu từ 0, nên lưu vị trí + 1
    for(i = 0; i < numsSize; i++)
    {
        index[nums[i] + max / 2] = i + 1;
    }
    
    for(i = 0; i < numsSize; i++)
    {
        ...
        if(index[t + max / 2] != 0 && index[t + max / 2] != i + 1)
        ...
    }
} 

Em chú ý, nên đặt biến phụ để lưu giá trị max/2 chứ mỗi lần chạy mà chia lại kiểu này thì ... phí à.

[14520769]

Đây là code của mình dựa trên ý tưởng của anh Vinh ở trên, chỉ có điều là gộp 2 vòng for lại cho "nhìn" có vẻ gọn hơn

int* twoSum(int* nums, int numsSize, int target) 
{
    int i, t, max = 32004, mid = 16002;
    int *pos, *results;
    pos = (int *)calloc(sizeof(int), max);
    results  = (int *)calloc(sizeof(int), 2);
    for (i = 0; i < numsSize; i++)
    {
        t = target - nums[i];
        if (pos[t + mid])
        {
            results[0] = pos[t + mid];
            results[1] = i + 1;
            return results;
        }
        else 
        {
            pos[nums[i] + mid] = i + 1;
        }
    }
}

[14520674]

thấy mn post code mình cũng post code :3 mà hình như cũng giống mấy cái trên
rumtime: 4ms

#define MAX 100000
#define MID 50000
int* twoSum(int* nums, int numsSize, int target) 
{   
    int *res=(int*) calloc(sizeof(int),2);
    int p[MAX]={0},        
         i,j,t; 
    for(i=0; i<numsSize; i++)        
         p[nums[i]+MID] = i;
    target+=MID; 
    for(i=0; i<numsSize; i++)
   {       
       t=target-nums[i];       
       if(p[t])
      {           
           res[0]=i+1;            
           res[1]=p[t]+1;           
           return res;       
       }   
    }    
    return res;
} 

[toannv]

Các bạn chụp hình màn hình mình đc Accepted bài Sum nhưng dùng STL nhé. Còn ko thì up code lên nhé.

[13521079]

#define right 70000
 #define mid 35000
int* twoSum(int* nums, int numsSize, int target) 
{
    int* index=(int*)calloc(sizeof(int),2);
    int* find=(int*)calloc(sizeof(int),right);
    for(int i=0;i<numsSize;i++)
    {
        find[nums[i]+mid]=i;
    }
    target=target+mid;
    for(int i=0;i<numsSize;i++)
    {
        int t=target-nums[i];
        if(find[t]>i)
        {
            index[0]=i+1;
            index[1]=find[t]+1;
            return index;
        }
    }
} 

[toannv]

#define right 70000
 #define mid 35000
int* twoSum(int* nums, int numsSize, int target) 
{
    int* index=(int*)calloc(sizeof(int),2);
    int* find=(int*)calloc(sizeof(int),right);
    for(int i=0;i<numsSize;i++)
    {
        find[nums[i]+mid]=i;
    }
    target=target+mid;
    for(int i=0;i<numsSize;i++)
    {
        int t=target-nums[i];
        if(find[t]>i)
        {
            index[0]=i+1;
            index[1]=find[t]+1;
            return index;
        }
    }
} 

Nếu chạy tốt thì chuyển qua dùng STL đi em ơ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;
        }
    }
}
}; 

[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.

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