基于C++的拼多多算法在线笔试题示例

软件编程 C 语言 分类:[default] 更新日期: 2017-07-31
这篇文章主要介绍了基于C++的拼多多算法在线笔试题,列举了四个拼多多的算法笔试题,包括分治法、大数相乘、贪心算法以及迷宫问题,需要的朋友可以参考下

本文实例讲述了基于C++的拼多多算法在线笔试题。分享给大家供大家参考,具体如下:

最近在狼厂实习中,很久没做题了。秋招第一发, 拼多多。。。  四个简单题,看到有些人竟然觉得难? 我来降一发自己的RP,这题目觉得难的,如果你拿到比我好的Offer,我是不服气的。。

四个题。。。其实我也就写了40分钟吧。。不过最后也没有满分, 390/400, 第三题不知道为嘛一直有10分过不了。。

更一下, 刚刚好像发现第三题。。。这个>号, 我写的是>= ....? 可是我看题目好像是 >= 呀。。。

第一题:

要求时间复杂度O(n), 空间复杂度O(1)。

那么其实答案有两种情况,最大的三个数相乘 || 最小的两个数 * 最大的数。  时间复杂度O(n),瞬间想到时间复杂度O(n)求k大的经典算法,分治法!

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
long long a[N];
int k;
int partition(int l,int r) {
  while(l != r)
  {
    while(a[r] >= a[l] && r > l)
      r--;
    if(l == r)
      break;
    swap(a[r],a[l]);
    while(a[l] < a[r] && r > l)
      l++;
    if(l < r)
      swap(a[r],a[l]);
  }
  return l;
}
long long solve(int l,int r) {
  int now = partition(l,r);
  if(k < now)
    return solve(l,now-1);
  else if(k > now)
    return solve(now+1,r);
  else
    return a[now];
}
int main() {
  int n;
  while(~scanf("%d", &n)) {
    for(int i = 0; i < n; ++i) {
      scanf("%lld", &a[i]);
    }
    k = n - 1;
   long long x1 = solve(0, n-1);
    k = n - 2;
    long long x2 = solve(0, n-2);
    k = n - 3;
    long long x3 = solve(0, n-3);
    long long Ans = x1 * x2 * x3;
    if(n > 3) {
      k = 0;
      long long y1 = solve(0, n-1);
      k = 1;
      long long y2 = solve(0, n-2);
      Ans = max(Ans, y1*y2*x1);
    }
    printf("%lld\n", Ans);
  }
  return 0;
}

第二题:

大数相乘,模板题, 找了个模板。。。

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
string c1, c2;
int a[N], b[N], r[N];
void solve(int a[], int b[], int la, int lb) {
  int i, j;
  for(i = 0; i != N; i++) r[i] = 0;
  for(i = 0; i != la; i++)
  {
    for(j = 0; j != lb; j++)
    {
      int k = i + j;
      r[k] += a[i] * b[j];
      while(r[k] > 9)
      {
        r[k + 1] += r[k] / 10;
        r[k] %= 10;
        k++;
      }
    }
  }
  int l = la + lb - 1;
  while(r[l] == 0 && l > 0) l--;
  for(int i = l; i >= 0; i--) cout << r[i];
  cout << endl;
}
int main() {
  while(cin >> c1 >> c2)
  {
    int la = c1.size(), lb = c2.size();
    for(int i = 0; i != la; i++)
      a[i] = (int)(c1[la - i - 1] - '0');
    for(int i = 0; i != lb; i++)
      b[i] = (int)(c2[lb - i - 1] - '0');
    solve(a, b, la, lb);
  }
  return 0;
}

第三题:

贪心啊, 我是按照 尽量满足最小人的需求来贪心的。。。一直90%?  有人是用尽量使用掉最大的巧克力来贪的,100%, 来个反例好不好?

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 3e6 + 10;
long long w[N], h[N];
int main() {
  int n, m;
  while(~scanf("%d", &n)) {
    for(int i = 0; i < n; ++i) {
      scanf("%lld", &h[i]);
    }
    scanf("%d", &m);
    for(int i = 0; i < m; ++i) {
      scanf("%lld", &w[i]);
    }
    sort(h, h + n);
    sort(w, w + m);
    int Ans = 0;
    for(int i = 0, j = 0; i < n && j < m; ) {
      if(w[j] >= h[i]) {
        ++Ans;
        ++i, ++j;
      }
      else {
        ++j;
      }
    }
    printf("%d\n", Ans);
  }
  return 0;
}

第四题:

迷宫问题, 有趣的是多了一把钥匙。。。  一看门不超过10个。。。M, N <=100...想了想状态数。。。直接状态压缩吧。。  之后就是一个非常暴力可耻的状态压缩bfs。。。然后就一发AC了。。

#include <cstdio>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
const int N = 110;
char mz[N][N];
bool vis[N][N][N*10];
int fx[4] = {0, 0, 1, -1};
int fy[4] = {1, -1, 0, 0};
int m, n;
map<char, int> key;
struct node {
  int x, y, cnt, sta;
  node():cnt(0), sta(0) {}
};
queue<node> que;
int bfs(int sx, int sy, int ex, int ey) {
  while(!que.empty()) que.pop();
  node tmp;
  tmp.x = sx, tmp.y = sy;
  que.push(tmp);
  while(!que.empty()) {
    node p = que.front();
    if(p.x == ex && p.y == ey) {
      return p.cnt;
    }
    que.pop();
    for(int i = 0; i < 4; ++i) {
      int newx = p.x + fx[i];
      int newy = p.y + fy[i];
      if(newx < 0 || newx >= m || newy < 0 || newy >= n) continue;
      if(mz[newx][newy] == '0') continue;
      int sta = p.sta;
      if(mz[p.x][p.y] >= 'a' && mz[p.x][p.y] <= 'z') {
        sta |= (1<<key[mz[p.x][p.y]]);
      }
      if(vis[newx][newy][sta]) continue;
      if(mz[newx][newy] >= 'A' && mz[newx][newy] <= 'Z') {
        if((sta & (1<<(key[mz[newx][newy] - 'A' + 'a'])))== 0) {
          continue;
        }
      }
      vis[newx][newy][sta] = true;
      tmp.x = newx, tmp.y = newy, tmp.cnt = p.cnt + 1, tmp.sta = sta;
      que.push(tmp);
    }
  }
  return -1;
}
int main() {
  while(~scanf("%d %d", &m, &n)) {
    int sx, sy, ex, ey;
    int cnt = 0;
    for(int i = 0; i < m; ++i) {
      scanf("%s", mz[i]);
      for(int j = 0; j < n; ++j) {
        if(mz[i][j] == '2') {
          sx = i, sy = j;
        }
        if(mz[i][j] == '3') {
          ex = i, ey = j;
        }
        if(mz[i][j] >= 'a' && mz[i][j] <= 'z') {
          key[mz[i][j]] = cnt++;
        }
      }
    }
    for(int i = 0; i < m; ++i) {
      for(int j = 0; j < n; ++j) {
        for(int s = 0; s < (1<<cnt); ++s) {
          vis[i][j][s] = false;
        }
      }
    }
    int Ans = bfs(sx, sy, ex, ey);
    printf("%d\n", Ans);
  }
  return 0;
}

希望本文所述对大家C++程序设计有所帮助。


> 本站内容系网友提交或本网编辑转载,其目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题,请及时与本网联系,我们将在第一时间删除内容!

相关文章
  • PHP微信开发之查询微信精选文章
    这篇文章主要为大家详细介绍了PHP微信开发之简单实现查询微信精选文章的相关资料,感兴趣的小伙伴们可以参考一下查询微信里的一些精选的,点击量比较大的文章. 别忘记申请apikey(登录百度账号即可获取),要完成的功能是: 1.用户回复"文章",公众号要返回文章分类的编号(比如9.科技). 2.用户回复wz9,1,腾讯     则能返回科技类 ...
  • PHP微信开发之查询城市天气
    PHP微信开发之查询城市天气
    这篇文章主要为大家详细介绍了PHP微信开发之简单实现查询城市天气的相关资料,感兴趣的小伙伴们可以参考一下PHP微信查询城市天气,首先,你需要找到一个获取天气的API,此处,我用的是百度的apistore,申请和使用API的网址:http://apistore.baidu.com/apiworks/servicedetail/112.html  登录百度账号, ...
  • PHP微信开发之有道翻译
    这篇文章主要为大家详细介绍了PHP微信开发之简单实现有道翻译的相关资料,感兴趣的小伙伴们可以参考一下首先,你需要去有道翻译API官网去申请key:http://fanyi.youdao.com/openapi?path=data-mode得到key之后,就可以开始从该API获得查询的数据了(返回json还是XML,看个人喜好,这里我用的是json) 下面我直 ...
  • PHP微信开发之文本自动回复
    PHP微信开发之文本自动回复
    这篇文章主要为大家详细介绍了PHP微信开发之简单实现文本自动回复的相关资料,感兴趣的小伙伴们可以参考一下首先,先去微信公众平台注册一个账号(注册要填的东西挺多的),注册好之后,登录进去.可以看到左侧的"开发者中心",开启开发者中心前好像还要你完善一些资料,按照步骤完善即可.进入开发者中心之后,先去编辑 修改配置,修改配置的时候,注意: U ...
  • php英文单词统计器
    php英文单词统计器
    这篇文章主要为大家详细介绍了php英文单词统计器的实现代码,本文实例为大家分享了英文单词统计器php 实现,供大家参考,具体内容如下 程序开始运行, 按"浏览"钮选择一个英文文档, 再按"统计 Statistics"钮, 即可得到按字母顺序列出的所有单词,及其出现的次数 用于测试的数据文档: data.txt驱动程序: ...
  • 解读ASP.NET5&MVC6系列教程1:ASP.NET5简介
    这篇文章主要介绍ASP.NET 5简介以及对各个版本号进行解释,ASP.NET 5中新的变化,需要的朋友可以参考下.ASP.NET 5简介 ASP.NET 5是一个跨时代的改写,所有的功能和模块都进行了独立拆分,做到了彻底解耦.为了这些改写,微软也是蛮 拼的,几乎把.NET Framwrok全部改写了一遍,形成了一个.NET Core的东西. 在.NET C ...
猜你喜欢