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
    replied
    Originally posted by 13521079 View Post
    PHP Code:
    #define right 70000
     #define mid 35000
    inttwoSum(intnumsint numsSizeint target
    {
        
    intindex=(int*)calloc(sizeof(int),2);
        
    intfind=(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.

    Leave a comment:


  • 13521079
    replied
    PHP Code:
    #define right 70000
     #define mid 35000
    inttwoSum(intnumsint numsSizeint target
    {
        
    intindex=(int*)calloc(sizeof(int),2);
        
    intfind=(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;
            }
        }

    Leave a comment:


  • toannv
    replied
    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é.
    Last edited by toannv; 03-07-2015, 21:02.

    Leave a comment:


  • 14520674
    replied
    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
    PHP Code:
    #define MAX 100000
    #define MID 50000
    inttwoSum(intnumsint numsSizeint target
    {   
        
    int *res=(int*) calloc(sizeof(int),2);
        
    int p[MAX]={0},        
             
    i,j,t
        for(
    i=0i<numsSizei++)        
             
    p[nums[i]+MID] = i;
        
    target+=MID
        for(
    i=0i<numsSizei++)
       {       
           
    t=target-nums[i];       
           if(
    p[t])
          {           
               
    res[0]=i+1;            
               
    res[1]=p[t]+1;           
               return 
    res;       
           }   
        }    
        return 
    res;

    Last edited by 14520674; 03-07-2015, 17:48.

    Leave a comment:


  • 14520769
    replied
    Đâ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
    Code:
    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;
            }
        }
    }

    Leave a comment:


  • toannv
    replied
    Originally posted by 13521043 View Post
    đâ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

    PHP Code:
    inttwoSum(intnumsint numsSizeint target) {
        
        
    //Đề nó nói ko bắt đầu từ 0, nên lưu vị trí + 1
        
    for(0numsSizei++)
        {
            
    index[nums[i] + max 2] = 1;
        }
        
        for(
    0numsSizei++)
        {
            ...
            if(
    index[max 2] != && index[max 2] != 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í à.

    Leave a comment:


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

    Leave a comment:


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

    Leave a comment:


  • 13521043
    replied
    đâ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

    PHP Code:
    inttwoSum(intnumsint numsSizeint target) {
        
    intresults;
        
    int i;
        
    results = (int*)calloc(sizeof(int), 2);
        
        
    int max 100000;
        
        
    int j;
        
    intindex;
        
    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(0numsSizei++)
        {
            
    index[nums[i] + max 2] = 1;
        }
        
        for(
    0numsSizei++)
        {
            
    int 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[max 2] != && index[max 2] != 1)
            {
                
    results[0] = 1;
                
    results[1] = index[max 2];
                
                return 
    results;
            }
        }

    Leave a comment:


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

    PHP Code:
    #define MAX 1000
    inttwoSum(intnumsint numsSizeint target) {
        
    intresults;// 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=0i<5000i++) // khởi tạo số lượng = 0
        
    {
            
    temp[i]=0;
        }
        for(
    i=0i<numsSizei++)
        {
            
    temp[nums[i]+MAX]+=1//mảng lưu số lượng phần tử từng nums[i]
        
    }
        for(
    i=0i<numsSize-1i++){
            
    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]==jresults[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]==jresults[1]=k+1;
                }
                return 
    results;
            }
        }
        

    Leave a comment:


  • 13520376
    replied
    Đây là code của mình. 20ms
    PHP Code:
    inttwoSum(intnumsint numsSizeint target) {
        
    intresults;
        
    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;

    Leave a comment:


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

    Tài liệu sơ bộ buổi 1
    Attached Files
    Last edited by toannv; 02-07-2015, 10:29.

LHQC

Collapse
Working...
X