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

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

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

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

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

第一题:

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

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

#include 
#include 
#include 
#include 
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("%lldn", Ans);
  }
  return 0;
}

第二题:

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

#include 
#include 
#include 
#include 
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 
#include 
#include 
#include 
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("%dn", Ans);
  }
  return 0;
}

第四题：

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

#include 
#include 
#include 
#include 
#include