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

[toannv]

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.

[13520280]

#define MAX 60000
#define MID 30000

int singleNumber(int* nums, int numsSize) {
    int* hash = (int*)calloc(sizeof(int),MAX);
    for(int i=0; i<numsSize;i++)
    {
        hash[nums[i]+MID]+=1;
    }
    for(int i=0; i<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

[13521005]

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

int singleNumber(int* nums, int numsSize) {
    int result =  nums[0];
    for(int i = 1; i < numsSize ; i++)
    {
        result ^= nums[i];
    }
    return result;
} 

[14520052]

int singleNumber(int* nums, int numsSize) {
    int x=nums[0],i;
    for (i=1;i<numsSize;i++)
        x = x^nums[i];
    return x;
} 

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

[13520280]

int singleNumber(int* nums, int numsSize) {
    int x=nums[0],i;
    for (i=1;i<numsSize;i++)
        x = x^nums[i];
    return x;
} 

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

Ừa ha. Hay thiệt! XOR :kiss:

[14520874]

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

#define _MAX 50000

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

:embarrassed:

[13520280]

- C++ using STL
- 20ms

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

[14520979]

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???

[14520674]

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 )

[14520979]

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

[14520769]

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?

[toannv]

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.

[14520674]

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

[toannv]

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:

[13521005]

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

int singleNumber(int* nums, int numsSize) {
    int result =  nums[0];
    for(int i = 1; i < numsSize ; i++)
    {
        result ^= nums[i];
    }
    return result;
} 

int singleNumber(int* nums, int numsSize) {
    return (numsSize == -1) ? 0 : (singleNumber(nums, numsSize-1)) ^ nums[numsSize-1];
} 

:happy: