Originally posted by 13521079
View Post
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
-
PHP Code:#define right 70000
#define mid 35000
int* twoSum(int* nums, int numsSize, int target)
{
int* index=(int*)calloc(sizeof(int),2);
int* find=(int*)calloc(sizeof(int),right);
for(int i=0;i<numsSize;i++)
{
find[nums[i]+mid]=i;
}
target=target+mid;
for(int i=0;i<numsSize;i++)
{
int t=target-nums[i];
if(find[t]>i)
{
index[0]=i+1;
index[1]=find[t]+1;
return index;
}
}
}
Leave a comment:
-
thấy mn post code mình cũng post code :3 mà hình như cũng giống mấy cái trên
rumtime: 4ms
PHP Code:#define MAX 100000
#define MID 50000
int* twoSum(int* nums, int numsSize, int target)
{
int *res=(int*) calloc(sizeof(int),2);
int p[MAX]={0},
i,j,t;
for(i=0; i<numsSize; i++)
p[nums[i]+MID] = i;
target+=MID;
for(i=0; i<numsSize; i++)
{
t=target-nums[i];
if(p[t])
{
res[0]=i+1;
res[1]=p[t]+1;
return res;
}
}
return res;
}
Last edited by 14520674; 03-07-2015, 17:48.
Leave a comment:
-
Đây là code của mình dựa trên ý tưởng của anh Vinh ở trên, chỉ có điều là gộp 2 vòng for lại cho "nhìn" có vẻ gọn hơn
Code:int* twoSum(int* nums, int numsSize, int target) { int i, t, max = 32004, mid = 16002; int *pos, *results; pos = (int *)calloc(sizeof(int), max); results = (int *)calloc(sizeof(int), 2); for (i = 0; i < numsSize; i++) { t = target - nums[i]; if (pos[t + mid]) { results[0] = pos[t + mid]; results[1] = i + 1; return results; } else { pos[nums[i] + mid] = i + 1; } } }
Leave a comment:
-
Originally posted by 13521043 View Postđây là code của mình, ý tưởng cơ bản là lưu vị trí của pt trong để vô 1 mảng, pt không có trong đề sẽ không có giá trị (mình lấy giá trị 0), vậy chổ nào khác 0 mình mới xét.
code chạy 4ms
PHP Code:int* twoSum(int* nums, int numsSize, int target) {
//Đề nó nói ko bắt đầu từ 0, nên lưu vị trí + 1
for(i = 0; i < numsSize; i++)
{
index[nums[i] + max / 2] = i + 1;
}
for(i = 0; i < numsSize; i++)
{
...
if(index[t + max / 2] != 0 && index[t + max / 2] != i + 1)
...
}
}
Leave a comment:
-
Các bạn có thể coi thêm một bài về mảng.Attached Files
Leave a comment:
-
đây là code của mình, ý tưởng cơ bản là lưu vị trí của pt trong để vô 1 mảng, pt không có trong đề sẽ không có giá trị (mình lấy giá trị 0), vậy chổ nào khác 0 mình mới xét.
code chạy 4ms
PHP Code:int* twoSum(int* nums, int numsSize, int target) {
int* results;
int i;
results = (int*)calloc(sizeof(int), 2);
int max = 100000;
int j;
int* index;
index = (int*)calloc(sizeof(int), max); //khởi tạo mảng lưu vị trí
//Ban đầu mình khởi tạo cho giá trị = 0
//Nhưng search trên mạng thấy, mình sử dụng calloc thì nó tự động khởi tạo 0
//Nếu khởi tạo code mình chạy 12ms, bỏ đi còn 4ms
/*
for(i = 0; i < max; i++)
{
index[i] = 0;
}
*/
//Đề nó nói ko bắt đầu từ 0, nên lưu vị trí + 1
for(i = 0; i < numsSize; i++)
{
index[nums[i] + max / 2] = i + 1;
}
for(i = 0; i < numsSize; i++)
{
int t;
t = target - nums[i];
//Kiểm tra xem số t có giá trị trong index không, và khác i hiện tại
if(index[t + max / 2] != 0 && index[t + max / 2] != i + 1)
{
results[0] = i + 1;
results[1] = index[t + max / 2];
return results;
}
}
}
Leave a comment:
-
Code tham khảo bài tập buổi 1
PHP Code:#define MAX 1000
int* twoSum(int* nums, int numsSize, int target) {
int* results;// mảng lưu kết quả
int i,j;
int temp[50000]; // mảng lưu số lượng
results= (int*)calloc(sizeof(int),2);
for(i=0; i<5000; i++) // khởi tạo số lượng = 0
{
temp[i]=0;
}
for(i=0; i<numsSize; i++)
{
temp[nums[i]+MAX]+=1; //mảng lưu số lượng phần tử từng nums[i]
}
for(i=0; i<numsSize-1; i++){
j=target-nums[i];
if(temp[j+MAX]==1&& nums[i]!=j) // tồn tại số hạng 2 và không trùng số hạng 1
{
results[0]=i+1;
for(int k=i+1;k<numsSize;k++)
{
if(nums[k]==j) results[1]=k+1;
}
return results;
}
else
if(temp[j+MAX]>1) // tồn tại nhiều số hạng 2 thì chọn số đầu tiên
{
results[0]=i+1;
for(int k=i+1;k<numsSize;k++)
{
if(nums[k]==j) results[1]=k+1;
}
return results;
}
}
}
Leave a comment:
-
Đây là code của mình. 20ms
PHP Code:int* twoSum(int* nums, int numsSize, int target) {
int* results;
int binArr[40000];
results = (int*)calloc(sizeof(int),2);
int i,j,t;
target+=2000;
for (i=0;i<numsSize;i++)
{
nums[i]+=1000;
binArr[nums[i]]=1;
}
for (i=0;i<numsSize-1;i++)
{
t=target-nums[i];
if (binArr[t]==1)
{
results[0]=i+1;
for (j=i+1;j<numsSize;j++)
{
if (nums[j]==t)
{
results[1]=j+1;
return results;
}
}
}
}
return results;
}
Leave a comment:
-
[Lớp thuật toán hè 2015] Tài liệu và trao đổi buổi 1
Tài liệu sơ bộ buổi 1Attached FilesLast edited by toannv; 02-07-2015, 10:29.Tags: None
Leave a comment: