Announcement

Collapse
No announcement yet.

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

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 2

    Ngày mai, phòng máy sẽ mở cửa lúc 9:30 và 10:00 là bắt đầu học nhé các bạn.
    Attached Files
    toannv
    Trưởng phòng CôngTác SinhViên
    Last edited by toannv; 07-07-2015, 11:35.

  • #2
    PHP Code:
    #define MAX 60000
    #define MID 30000

    int singleNumber(intnumsint numsSize) {
        
    inthash = (int*)calloc(sizeof(int),MAX);
        for(
    int i=0i<numsSize;i++)
        {
            
    hash[nums[i]+MID]+=1;
        }
        for(
    int i=0i<MAX;i++)
        {
            if(
    hash[i]==1)
            return 
    i-MID;
        }

    - Tại vì lúc chạy ban đầu bị lỗi do có số âm. Nên chia hash ra: [0,30000): hash số âm. Còn lại hash số không âm.
    - Bài chưa tối ưu do nếu bộ test cực lớn. Cần tối ưu hơn.
    - 8ms
    toannv
    Trưởng phòng CôngTác SinhViên
    Last edited by toannv; 07-07-2015, 11:23.
    Khi tất cả những cái khác đã mất đi thì tương lai vẫn còn

    Bové

    Comment


    • #3
      XOR tất cả phần tử với nhau sẽ ra kết quả
      vì 2 số giống nhau XOR lại sẽ = 0

      PHP Code:
      int singleNumber(intnumsint numsSize) {
          
      int result =  nums[0];
          for(
      int i 1numsSize i++)
          {
              
      result ^= nums[i];
          }
          return 
      result;

      Comment


      • #4
        PHP Code:
        int singleNumber(intnumsint numsSize) {
            
        int x=nums[0],i;
            for (
        i=1;i<numsSize;i++)
                
        x^nums[i];
            return 
        x;

        Ý tưởng by Thiên Phúc.

        Comment


        • #5
          Originally posted by 14520052 View Post
          PHP Code:
          int singleNumber(intnumsint numsSize) {
              
          int x=nums[0],i;
              for (
          i=1;i<numsSize;i++)
                  
          x^nums[i];
              return 
          x;

          Ý tưởng by Thiên Phúc.
          Ừa ha. Hay thiệt! XOR :kiss:
          Khi tất cả những cái khác đã mất đi thì tương lai vẫn còn

          Bové

          Comment


          • #6
            Ý tưởng: Chia làm 2 mảng, mảng chứa số âm, mảng chứa số dương...

            PHP Code:
            #define _MAX 50000

            int singleNumber(intnumsint numsSize) {
                
            inthash = (int*)calloc(_MAX,sizeof(int));
                
            inthash2 = (int*)calloc(_MAX,sizeof(int));
                for (
            int i 0i<numsSizei++) {
                    if (
            nums[i]<0hash[nums[i]*(-1)]++;
                    else 
            hash2[nums[i]]++;
                }
                for (
            int i 0i<_MAXi++) {
                    if (
            hash[i] == 1) return i*(-1);   
                    if (
            hash2[i] == 1) return i;   
                }

            :embarrassed:
            "Programs must be written for people to read, and only incidentally for machines to execute"
            - Harold Abelson

            Comment


            • #7
              - C++ using STL
              - 20ms
              PHP Code:
              class Solution {
              public:
                  
              int singleNumber(vector<int>& nums
                  {
                      
              int result nums[0];
                   
                      for(
              std::vector<int>::iterator it nums.begin()+1;it!=nums.end();it++)
                      {
                          
              result ^=*it;
                      }
                      return 
              result;
                  }
              }; 
              13520280
              Đinh Quang Hình
              Last edited by 13520280; 07-07-2015, 13:48.
              Khi tất cả những cái khác đã mất đi thì tương lai vẫn còn

              Bové

              Comment


              • #8
                tại sao xor lần lượt như thế lại ra được kết quả đề bài yêu cầu. mấy anh giải thích giúp em với???
                :sunglasses:Practice Makes Perfect:sunglasses:

                Comment


                • #9
                  Originally posted by 14520979 View Post
                  tại sao xor lần lượt như thế lại ra được kết quả đề bài yêu cầu. mấy anh giải thích giúp em với???
                  mỗi lần xor thì nếu có 2 số giống nhau nó sẽ ra 0 nên sau khi xor hết dãy số thì những số giống nhau sẽ bị triệt tiêu chỉ còn lại số lặp 1 lần ) nên nó ra kết quả thôi )
                  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
                    Originally posted by 14520674 View Post
                    mỗi lần xor thì nếu có 2 số giống nhau nó sẽ ra 0 nên sau khi xor hết dãy số thì những số giống nhau sẽ bị triệt tiêu chỉ còn lại số lặp 1 lần ) nên nó ra kết quả thôi )
                    cảm ơn bạn, giờ thì hiểu rồi
                    :sunglasses:Practice Makes Perfect:sunglasses:

                    Comment


                    • #11
                      nếu như vậy thì nếu mảng có 2 phần tử duy nhất sẽ ra sai kết quả? VD đối với mảng {1, 2, 3, 1} thì kết quả sẽ là 2^3 = 0010 ^ 0011 = 0001 = 1?

                      Comment


                      • #12
                        Originally posted by 14520769 View Post
                        nếu như vậy thì nếu mảng có 2 phần tử duy nhất sẽ ra sai kết quả? VD đối với mảng {1, 2, 3, 1} thì kết quả sẽ là 2^3 = 0010 ^ 0011 = 0001 = 1?
                        Đề bài giới hạn chuyện này rồi mà em: every element appears twice except for one . Yên tâm.
                        Đọc kỹ hướng dẫn sử dụng trước khi dùng.
                        toannv
                        Trưởng phòng CôngTác SinhViên
                        Last edited by toannv; 08-07-2015, 10:29.

                        Comment


                        • #13
                          thầy ơi có tài liệu chi tiết ko ạ e ở nhà học cuối tháng này mới vào SG
                          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


                          • #14
                            Originally posted by 14520674 View Post
                            thầy ơi có tài liệu chi tiết ko ạ e ở nhà học cuối tháng này mới vào SG
                            Chứ em muốn chi tiết cỡ nào nữa? :funny:

                            Comment


                            • #15
                              cải tiến đoạn code của mình bằng phương pháp đệ quy thì ta chỉ cần một dòng

                              Originally posted by 13521005 View Post

                              PHP Code:
                              int singleNumber(intnumsint numsSize) {
                                  
                              int result =  nums[0];
                                  for(
                              int i 1numsSize i++)
                                  {
                                      
                              result ^= nums[i];
                                  }
                                  return 
                              result;

                              PHP Code:
                              int singleNumber(intnumsint numsSize) {
                                  return (
                              numsSize == -1) ? : (singleNumber(numsnumsSize-1)) ^ nums[numsSize-1];

                              :happy:

                              Comment

                              LHQC

                              Collapse
                              Working...
                              X