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

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

    Comment


    • #17
      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

      Comment


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

        Comment


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

          Comment


          • #20
            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

            Comment


            • #21
              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.
              :sunglasses:Practice Makes Perfect:sunglasses:

              Comment


              • #22
                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

                Comment


                • #23
                  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

                  Comment


                  • #24
                    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]

                    Comment


                    • #25
                      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

                      Comment


                      • #26
                        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:

                        Comment


                        • #27
                          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

                          Comment

                          LHQC

                          Collapse
                          Working...
                          X