聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1746|回复: 2
收起左侧

[其他] 求助帖,求问stanford公开课Algorithms: Design and Analysis, Part I (Week 1)的问题

[复制链接] |试试Instant~ |关注本帖
yangze0930 发表于 2015-7-8 18:26:05 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
题目:
Question 1
Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.
Because of the large size of this array, you should implement the fast divide-and-conquer algorithm covered in the video lectures. The numeric answer for the given input file should be typed in the space below.

. from: 1point3acres

求问第一周编程题,第一次使用vector写代码。为什么算出来的结果和用动态数组写的代码算出来的不一样 使用vector写的程序代码,算出来是2584786980.
  • #include<iostream>
  • #include<vector>
  • #include<fstream>
  • using namespace std;
  • long long countInversion(vector<int> & vec)
  • {
  •         int n = vec.size();
  •         if (n != 1)
  •         {
  •                 vector<int> b, c;
  •                 for (int i = 0; i < n / 2; i++)
  •                 {
  •                         b.push_back(vec);
  •                 }
  •                 for (int i = 0; i < n - n / 2; i++)
  •                 {
  •                         c.push_back(vec[n / 2 + i]);
  •                 }
  •                 long long num1 = countInversion(b);
  •                 long long num2 = countInversion(c);
  •                 long long num3 = 0;
  •                 vec.clear();
  •                 int i = 0, j = 0;
  •                 for (int k = 0; k < n; k++)
  •                 {
  •                         if (i < n / 2 && j<n - n / 2)
  •                         {
  •                                 if (b <= c[j])
  •                                 {
  •                                         vec.push_back(b);
  •                                         i++;
  •                                 }
  •                                 else if (b>c[j])
  •                                 {
  •                                         vec.push_back(c);
  •                                         num3 = num3 + n / 2 - i;
  •                                         j++;
  •                                 }
  •                         }
  •                         else if (i >= n / 2)
  •                         {
  •                                 vec.push_back(c[j]);
  •                                 j++;
  •                         }
  •                         else if (j >= n - n / 2)
  •                         {
  •                                 vec.push_back(b);
  •                                 i++;
  •                         }
  •                 }
  •                 long long ans = num1 + num2 + num3;
  •                 return ans;
  •         }
  •         else if (n == 1)
  •                 return 0;
  • }
  • int main(void)
  • {
  •         vector<int> a;
  •         int temp;
  •         ifstream fin("D:\\IntegerArray.txt");
  •         if (!fin)
  •         {
  •                 cout << "can't open file";
  •                 return 1;
  •         }
  •         for (int i = 0; i < 100000; i++)
  •         {
  •                 fin >> temp;
  •                 a.push_back(temp);
  •         }
  •         long long ans = countInversion(a);
  •         cout << a.size()<<'\t'<<ans;
  •         getchar();
  •         getchar();
  •         return 0;
  • }

[color=rgb(73, 123, 137) !important]复制代码

使用动态数组算出来的结果是2407905288
  • #include<iostream>
  • #include<fstream>
  • using namespace std;
  • long long inven(int a[],int n)
  • {
  •         if (n != 1)
  •         {
  •                 int *b=new int[n/2];
  •                 int *c=new int[n-n/2];
  •                 for (int i = 0; i < n / 2; i++)
  •                 {
  •                         b = a;
  •                 }
  •                 for (int i = 0; i < n - n / 2; i++)
  •                 {
  •                         c = a[n / 2 + i];
  •                 }
  •                 long long num1 = inven(b,n/2);
  •                 long long num2 = inven(c,n-n/2);
  •                 long long num3 = 0;
  •                 int i = 0, j = 0;
  •                 for (int k = 0; k < n; k++)
  •                 {
  •                         if (i < n / 2 && j<n-n/2)
  •                         {
  •                                 if (b <= c[j])
  •                                 {
  •                                         a[k] = b;
  •                                         i++;
  •                                 }
  •                                 else if (b>c[j])
  •                                 {
  •                                         a[k] = c[j];
  •                                         num3 = num3 + n / 2 - i;
  •                                         j++;
  •                                 }
  •                         }
  •                         else if (i >= n / 2)
  •                         {
  •                                 a[k] = c[j];
  •                                 j++;
  •                         }
  •                         else if (j >= n - n / 2)
  •                         {
  •                                 a[k] = b;
  •                                 i++;
  •                         }
  •                 }
  •                 delete b;
  •                 delete c;
  •                 long long ans = num1 + num2 + num3;
  •                 return ans;
  •         }
  •         else if (n == 1)
  •                 return 0;
  • }
  • int main(void)
  • {
  •         ifstream fin("D:\\IntegerArray.txt");
  •         if (!fin)
  •         {
  •                 cout << "can't open file";
  •                 return 1;
  •         }
  •         int a[100000];
  •         for (int i = 0; i < 100000; i++)
  •         {
  •                 fin >> a;
  •         }
  •         long long ans = inven(a,100000);
  •         cout << ans;
  •         getchar();
  •         getchar();
  •         return 0;
  • }

-google 1point3acres[color=rgb(73, 123, 137) !important]复制代码

蟹蟹各位啦


CS, EE, IS
 楼主| yangze0930 发表于 2015-7-8 18:29:47 | 显示全部楼层
重新贴一下代码
vector数据结构写的:
  1. #include<iostream>
  2. #include<vector>
  3. #include<fstream>
  4. . Waral 博客有更多文章,
  5. using namespace std; 来源一亩.三分地论坛.

  6. long long countInversion(vector<int> & vec)
  7. {
  8.         int n = vec.size();
  9.         if (n != 1)
  10.         {
  11.                 vector<int> b, c;
  12.                 for (int i = 0; i < n / 2; i++)
  13.                 {
  14.                         b.push_back(vec[i]);
  15.                 }
  16.                 for (int i = 0; i < n - n / 2; i++)
  17.                 {
  18.                         c.push_back(vec[n / 2 + i]);. Waral 博客有更多文章,
  19.                 }. 牛人云集,一亩三分地
  20.                 long long num1 = countInversion(b);
  21.                 long long num2 = countInversion(c);
  22.                 long long num3 = 0;
  23.                 vec.clear();
  24.                 int i = 0, j = 0;. from: 1point3acres
  25.                 for (int k = 0; k < n; k++)
  26.                 {
  27.                         if (i < n / 2 && j<n - n / 2)
  28.                         {. 牛人云集,一亩三分地
  29.                                 if (b[i] <= c[j])
  30.                                 {
  31.                                         vec.push_back(b[i]);
  32.                                         i++;
  33.                                 }
  34.                                 else if (b[i]>c[j])
  35.                                 {
  36.                                         vec.push_back(c[i]);
  37.                                         num3 = num3 + n / 2 - i;
  38.                                         j++;
  39.                                 }
  40.                         }
  41.                         else if (i >= n / 2).留学论坛-一亩-三分地
  42.                         {
  43.                                 vec.push_back(c[j]);
  44.                                 j++;
  45.                         }
  46.                         else if (j >= n - n / 2). more info on 1point3acres
  47.                         {
  48.                                 vec.push_back(b[i]);
  49.                                 i++;. more info on 1point3acres
  50.                         }
  51.                 }. 一亩-三分-地,独家发布
  52.                 long long ans = num1 + num2 + num3;
  53.                 return ans;
  54.         }
  55.         else if (n == 1)
  56.                 return 0;
  57. }


  58. int main(void)
  59. {.1point3acres网
  60.         vector<int> a;
  61.         int temp;. 牛人云集,一亩三分地
  62.         ifstream fin("D:\\IntegerArray.txt");
  63.         if (!fin)
  64.         {
  65.                 cout << "can't open file";. 围观我们@1point 3 acres
  66.                 return 1;
  67.         }
  68.         for (int i = 0; i < 100000; i++)
  69.         {
  70.                 fin >> temp;
  71.                 a.push_back(temp);
  72.         } 来源一亩.三分地论坛.
  73.         long long ans = countInversion(a);
  74.         cout << a.size()<<'\t'<<ans;. 牛人云集,一亩三分地
  75.         getchar();. more info on 1point3acres
  76.         getchar();
  77.         return 0;
  78. }
复制代码
动态数组写的代码:
  1. #include<iostream>. 留学申请论坛-一亩三分地
  2. #include<fstream>
  3. using namespace std;. 一亩-三分-地,独家发布

  4. long long inven(int a[],int n)
  5. {. more info on 1point3acres
  6.         if (n != 1)
  7.         {
  8.                 int *b=new int[n/2];
  9.                 int *c=new int[n-n/2];
  10.                 for (int i = 0; i < n / 2; i++)
  11.                 {
  12.                         b[i] = a[i];. 1point 3acres 论坛
  13.                 }
  14.                 for (int i = 0; i < n - n / 2; i++)
  15.                 {
  16.                         c[i] = a[n / 2 + i];
  17.                 }. 1point3acres
  18.                 long long num1 = inven(b,n/2);
  19.                 long long num2 = inven(c,n-n/2);
  20.                 long long num3 = 0;
  21.                 int i = 0, j = 0;
  22.                 for (int k = 0; k < n; k++)
  23.                 {. 留学申请论坛-一亩三分地
  24.                         if (i < n / 2 && j<n-n/2)
  25.                         {
  26.                                 if (b[i] <= c[j])
  27.                                 {
  28.                                         a[k] = b[i];. from: 1point3acres
  29.                                         i++;
  30.                                 }
  31.                                 else if (b[i]>c[j])
  32.                                 {
  33.                                         a[k] = c[j];
  34.                                         num3 = num3 + n / 2 - i;
  35.                                         j++;
  36.                                 }
  37.                         }
  38.                         else if (i >= n / 2)
  39.                         {
  40.                                 a[k] = c[j];
  41.                                 j++;. more info on 1point3acres
  42.                         }
  43.                         else if (j >= n - n / 2)
  44.                         {
  45.                                 a[k] = b[i];. 围观我们@1point 3 acres
  46.                                 i++;
  47.                         }
  48.                 }
  49.                 delete b;
  50.                 delete c;
  51.                 long long ans = num1 + num2 + num3;
  52.                 return ans;
  53.         }
  54.         else if (n == 1)
  55.                 return 0;.1point3acres网
  56. }

  57. int main(void)
  58. {
  59.         ifstream fin("D:\\IntegerArray.txt"); 来源一亩.三分地论坛.
  60.         if (!fin)
  61.         {.留学论坛-一亩-三分地
  62.                 cout << "can't open file";
  63.                 return 1;. 1point3acres
  64.         }
  65.         int a[100000];
  66.         for (int i = 0; i < 100000; i++). visit 1point3acres for more.
  67.         {
  68.                 fin >> a[i];. more info on 1point3acres
  69.         }
  70.         long long ans = inven(a,100000);
  71.         cout << ans;
  72.         getchar();
  73.         getchar();
  74.         return 0;
  75. }
复制代码
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
 楼主| yangze0930 发表于 2015-7-8 18:30:16 | 显示全部楼层
蟹蟹大家啦!!!
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 10:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表