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.
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
-
PHP Code:#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;
}
}
- Bài chưa tối ưu do nếu bộ test cực lớn. Cần tối ưu hơn.
- 8msLast 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é
-
-
Ý 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(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;
}
}
"Programs must be written for people to read, and only incidentally for machines to execute"
- Harold Abelson
Comment
-
- 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;
}
};
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
-
Originally posted by 14520979 View Posttạ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???) nên nó ra kết quả thôi
)
PHP Code:Full name: Thai 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
-
-
Originally posted by 14520769 View Postnế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?
Đọc kỹ hướng dẫn sử dụng trước khi dùng.Last edited by toannv; 08-07-2015, 10:29.
Comment
-
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(int* nums, int numsSize) {
int result = nums[0];
for(int i = 1; i < numsSize ; i++)
{
result ^= nums[i];
}
return result;
}
PHP Code:int singleNumber(int* nums, int numsSize) {
return (numsSize == -1) ? 0 : (singleNumber(nums, numsSize-1)) ^ nums[numsSize-1];
}
Comment
Comment