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

  • [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
    toannv
    Phòng CôngTác SinhViên
    Last edited by toannv; 02-07-2015, 10:29.

  • #2
    Đâ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;

    Comment


    • #3
      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;
              }
          }
          

      Comment


      • #4
        đâ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;
                }
            }

        Email: luuthevinh7@gmail.com
        Blog: luuthevinh.com - luuthevinh.me - 14gamez.com
        Facebook: /eric14

        Comment


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

          Comment


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

            Comment


            • #7
              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í à.

              Comment


              • #8
                Đâ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;
                        }
                    }
                }

                Comment


                • #9
                  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;

                  14520674
                  Thái Viết Phong
                  Last edited by 14520674; 03-07-2015, 17:48.
                  PHP Code:
                  Full nameThai Viet Phong
                  Facebook
                  www.facebook.com/ThaiVietPhong.ITM
                  Email
                  thaivietphong.net@gmail.com 
                  Tìm trước khi hỏi bạn sẽ giỏi hơn mỗi khi tìm

                  Comment


                  • #10
                    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é.
                    toannv
                    Phòng CôngTác SinhViên
                    Last edited by toannv; 03-07-2015, 21:02.

                    Comment


                    • #11
                      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;
                              }
                          }

                      Comment


                      • #12
                        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.

                        Comment


                        • #13
                          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;
                                  }
                              }
                          }
                          }; 
                          :sunglasses:Practice Makes Perfect:sunglasses:

                          Comment


                          • #14
                            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.

                            Comment


                            • #15
                              ở đâ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.

                              Comment

                              LHQC

                              Collapse
                              Working...
                              X