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

[13521005]

https://leetcode.com/problems/reverse-bits/ có vẻ đúng :3

Mình làm thế này. Phức tạp hơn một tí, tốc độ cũng không cải thiện gì ps:

uint32_t reverseBits(uint32_t n) {
    int a;
    char bef, aft;//before - after
    int j, x;
    for(int i = 0; i < 16; i++)
    {
        j = 31 - i;
        bef = (n >> i) & 1;
        aft = (n >> j) & 1;
        x = bef ^ aft;
        a = (x << i) | (x << j);
        n ^= a;

    }
    return n;
} 

[14520423]

uint32_t reverseBits(uint32_t n) {
    uint32_t temp=0;
    for(int i=0;i<32;i++)
    {   
        
        temp=temp<<1;
        if(n&1)
            temp=temp+1;
        n=n>>1;
    }
    return temp;
} 

https://leetcode.com/problems/reverse-bits/ có vẻ đúng :3

[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:

[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:

[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]

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.

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

[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

[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]

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

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

[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]

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:

[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.

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