拼多多3.30研发笔试

1. 宝石

动态规划,dp[i]表示到第i关可以获得的最大金币数量。

dp[i] = dp[i-1],第i关是boss

dp[i] = max(dp[i-1], dp[j-1] + Vk),j是离i最近的获得宝石k的关卡。

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> dp(n + 1, 0);
    unordered_map<int, int> collections;
    for (int i = 1; i <= n; ++i)
    {
        char boss;
        int type;
        int value;
        cin >> boss >> type >> value;
        if (boss == 'b')
        {
            collections[type] = i;
            dp[i] = dp[i - 1];
        }
        else
        {
            if (!collections.count(type))
            {
                dp[i] = dp[i - 1];
            }
            else
            {
                dp[i] = max(dp[i - 1], dp[collections[type]] + value);
            }
        }
    }

    cout << dp[n];
    return 0;
}

2. 修路

#include <bits/stdc++.h>

using namespace std;

int dfs(int start, vector<vector<pair<int, int>>>& adj, vector<int> &visited){
  visited[start] = true;
  if(adj[start].size() == 0){
    return 0;
  }
  int res = 0;
  for(auto next : adj[start]){
    if(visited[next.first]){
      continue;
    }
    int next_count = dfs(next.first, adj, visited);
    if(next_count > 0){
      res += next_count;
    }
    else if(next.second){
      res += 1;
    }
  }
  return res;
}


int main(){
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> adj(n+1, vector<pair<int, int>>());
  for(int i = 0; i < n-1; ++i){
    int start, end, is_bad;
    cin >> start >> end >> is_bad;
    adj[start].push_back({end, is_bad});
    adj[end].push_back({start, is_bad});
  }
  vector<int> visited(n+1, 0);
  int res = dfs(1, adj, visited);
  cout << res;
  return 0;
}

3. 最大积连续子数组的开始下标和结束下标

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int main(){
  int n;
  cin >> n;
  vector<int> nums(n);
  for(int i = 0; i < n; ++i){
    cin >> nums[i];
  }
  vector<ll> max_dp(n, LLONG_MIN);  //max_dp[i]以下标i结束的连续子数组的最大积
  vector<ll> min_dp(n, LLONG_MAX);  //min_dp[i]以下标i结束的连续子数组的最小积

  vector<int> max_start(n, 0);      //max_start[i] 表示以下标i结束的最大积连续子数组的起始下标
  vector<int> min_start(n, 0);      //min_start[i] 表示以下标i结束的最小积连续子数组的起始下标

  int res_start = 0;
  int res_end = 0;
  ll res_max = nums[0];
  max_dp[0] = nums[0];
  min_dp[0] = nums[0];
  for(int i = 1; i < n; ++i){
    if(nums[i] == 0){
      max_dp[i] = 0;
      min_dp[i] = 0;
      max_start[i] = 0;
      min_start[i] = 0;
    }
    else if(nums[i] > 0){
      if(nums[i] > max_dp[i-1] * nums[i]){
        max_dp[i] = nums[i];
        max_start[i] = i;
      }
      else{
        max_dp[i] = max_dp[i-1] * nums[i];
        max_start[i] = max_start[i-1];
      }
      if(nums[i] < min_dp[i-1] * nums[i]){
        min_dp[i] = nums[i];
        min_start[i] = i; 
      }
      else{
        min_dp[i] = min_dp[i-1] * nums[i];
        min_start[i] = min_start[i-1];
      }
    }
    else{
      if(nums[i] > min_dp[i-1] * nums[i]){
        max_dp[i] = nums[i];
        max_start[i] = i;
      }
      else{
        max_dp[i] = min_dp[i-1] * nums[i];
        max_start[i] = max_start[i-1];
      }
      if(nums[i] < max_dp[i-1] * nums[i]){
        min_dp[i] = nums[i];
        min_start[i]  = i;
      }
      else{
        min_dp[i] = max_dp[i-1] * nums[i];
        min_start[i]  = min_start[i-1];
      }
    }
    if(max_dp[i] > res_max){
      res_max = max_dp[i];
      res_start = max_start[i];
      res_end = i;
    }
    else if(max_dp[i] == res_max && i - max_start[i] > res_end - res_start){
      res_start = max_start[i];
      res_end = i;
    }
  }
  if(res_max <= -1){
    cout << -1;
  }
  else{
    cout << res_start << " " << res_end;
  }
  return 0;
}

4. 使数组成为非严格递增数组的最小操作次数

#include <bits/stdc++.h>

using namespace std;

int scan_num(vector<int>& nums){
  for(int i = 1; i < nums.size(); ++i){
    if(nums[i-1] > nums[i]){
      return i-1;
    }
  }
  return -1;
}

int main(){
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++){
      cin >> nums[i];
    }
    int count = 0;
    int index = scan_num(nums);
    while(index != -1){
      count++;
      for(int i = 0; i < nums.size(); i++){
        if(nums[i] == nums[index]){
          nums[i] = 0;
        }
      }
      index = scan_num(nums);
    }
    cout << count;
  }
  return 0;
}

#我的实习求职记录#
全部评论
大佬牛的呀
点赞 回复 分享
发布于 2023-04-13 16:39 黑龙江
3.30参加的数据分析笔试,编程题全a,已经挂了。。
点赞 回复 分享
发布于 2023-04-04 20:19 湖南
楼主知道pdd笔试是只能做一次吗?还是可以刷笔试成绩
点赞 回复 分享
发布于 2023-04-03 16:43 湖北

相关推荐

来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
榕城小榕树:1200单休,我去干点啥别的不好
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
评论
3
14
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务