首页 > 腾讯 0823 技术研究 数据分析笔试题&题解 4.9分
头像
面鲸
编辑于 2020-08-24 10:05
+ 关注

腾讯 0823 技术研究 数据分析笔试题&题解 4.9分

第一题

题目描述

现在给你一个只包含""括号的字符串,问你至少加多少个字符是合法的,对于字符串合法的定义为:

  • 字符串为空是合法的
  • 若字符串A合法,则字符串(A), [A]也是合法的
  • 若字符串A和字符串B均合法,则AB合法
    输入
  • 第一行输入一个字符串s,保证只有题目要求的字符
  • 1 <= len(s) <= 200
    输出
  • 输出最少需要添加几个字符可以构成合法的字符串
    样例输入
  • 样例输出
  • 1
    样例输入
  • )(][][)(
    样例输出
  • 3
    分析
  • 如果只有一种括号的话就是leetcode921的原题
  • 有2种括号的话需要用DP去搞。我们先求出来通过添加字符,从i到j能构成的合法串的最短长度是多少。然后状态转移一波(分情况讨论)。
    解法
    #include <bits/stdc++.h>
    using namespace std;
    int dp[205][205];
    int main(){
      string s;
      int i,j,k,p;
      while(cin>>s){
          memset(dp,0,sizeof(dp));
          if(s.size()==1){
              puts("1");
              continue;
          }
          for(i=0;i+1<s.size();i++){
              if((s[i]=='('&&s[i+1]==')')||(s[i]=='['&&s[i+1]==']'))
              dp[i][i+1]=2;
          }
          for(i=3;i<=s.size();i++){
              for(j=0;j+i-1<s.size();j++){
                  k=j+i-1;
                  dp[j][k]=max(dp[j][k],dp[j+1][k-1]);
                  dp[j][k]=max(dp[j][k],max(dp[j+1][k],dp[j][k-1]));
                  if((s[j]=='('&&s[k]==')')||(s[j]=='['&&s[k]==']')){
                      dp[j][k]=max(dp[j][k],dp[j+1][k-1]+2);
                  }
                  for(p=j+1;p<k;p++){
                      dp[j][k]=max(dp[j][k],dp[j][p]+dp[p+1][k]);
                  }
              }
          }
          cout<<s.size()-dp[0][s.size()-1]<<endl;
      }
      return 0;
    }

第二题

题目描述
  • 求抛物线与直线,直线以及x轴所围成的封闭图形的面积。
    输入
  • 第一行为一个整数T,表示测试数据的组数
  • 接下来每行输入四个整数A, B, C, D
  • 1 <= T <= 1000, 1 <= A, B <= 100, -100 <= C <= 100
    输出
  • 每组测试数据输出一个答案,为封闭图形的面积
    样例输入
  • 1
  • 2 3 1 2
    样例输出
  • 9.16667
    分析
  • 简单的微积分,也可以用辛普森公式直接计算:
  • 在平面直角坐标系中,由任意三点(x1, y1), (x2, y2), (x3, y3)(x1<x2<x3,x2 = (x1 + x3)/2)确定的抛物线y= f(x)在[x1, x3]的定积分为
    • 解法
      #include <bits/stdc++.h>
      using namespace std;
      double calc(int a, int b, double x) {
      return 1.0 * a * x * x + x + b;
      }
      int main() {
      int T; cin >> T;
      while (T--) {
          int a, b, c,d;
          cin >> a >> b >> c >> d;
          double mid = (c + d) / 2.0;
          double y1 = calc(a, b, c);
          double y2 = calc(a, b, mid);
          double y3 = calc(a, b, d);
          printf("%.6lf\n", 1.0/6 * (d - c) * (y1 + 4 * y2 + y3));
      }
      return 0;
      }

第三题

题目描述
  • 小Q所在的部门有n个人,要从这n个人中选任意数量的人组成一只队伍,再在这些人中选出一名队长,求不同的方案数对1e9+7取模的结果。如果两个方案选取的人的集合不同或者选出的队长不同,则认为这两个方案是相同的。
    输入
  • 一行一个数字n,1<=n <= 1e9
    输出
  • 一行一个数字表示答案
    样例输入
  • 2
    样例输出
  • 4
    分析
  • 一个组合数学题,如果不选队长的话选出k个人的方案数就是,要考虑队长的话方案数就是,最终的方案数为。经过一顿推导可以得到最终的结果为
    解法
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    const ll mod = 1000000000 + 7;
    ll poww(ll base, ll a) {
      ll ans = 1;
      while (a != 0) {
          if (a & 1) {
              ans *= base;
              ans %= mod;
          }
          base *= base;
          base %= mod;
          a >>= 1; 
      }
      return ans;
    }
    int main() {
      int n;
      while (cin >> n) {
          cout << (n* poww(2, n-1)) % mod << endl;
      }
      return 0;
    }

第四题

题目描述
  • 我们定义集合g(x)为:与x相邻的节点的集合;从而定义图的价值为:图中满足g(x)=g(y)这样的点对(x,y)的数量
  • 现在给定一个n个节点和m条边的无向联通图,请你计算出当前图的价值
    输入
  • 第一行输入两个正整数n和m,表示点的数量和边的数量
  • 接下来m行,每行输入两个整数x和y,表示x和y之间连边
  • 2<=n<=100000, 1<=m <= 200000, 1 <= x, y <= n
  • 输入保证图连通,且没有重边和环
    输出
  • 输出结果
    样例输入
  • 4 3
  • 1 2
  • 2 3
  • 2 4
    样例输出
  • 3
    分析
  • 对于每一个顶点,可以得到它相邻的点的集合,将相邻的点的列表做个哈希,最后直接判断即可过90%。
    解法
    #include <bits/stdc++.h>
    using namespace std;
    const int siz=100005;
    vector<int> G[siz];
    map<int,int> mp;
    int main(){
      int n,m,i,j,k,x,y,ans,tmp;
      while(scanf("%d%d",&n,&m)!=EOF){
          for(i=0;i<=n;i++)
          G[i].clear();
          for(i=0;i<m;i++){
              cin>>x>>y;
              G[x].push_back(y);
              G[y].push_back(x);
          }
          ans=0;
          mp.clear();
          for(i=1;i<=n;i++){
              for(j=0;j<G[i].size();j++)
              mp[i]+=(G[i][j]*G[i][j]);
          }
          for(i=1;i<=n;i++){
              if(G[i].size()<=1)
              continue;
              for(j=0;j<G[i].size();j++){
                  for(k=j+1;k<G[i].size();k++){
                      if(G[G[i][j]].size()!=G[G[i][k]].size())
                      continue;
                      if(mp[G[i][j]]==mp[G[i][k]])
                      ans++;
                  }
              }
          }
          printf("%lld\n",ans);
      }
      return 0;
    }

第五题

题目描述
  • 现在有n个点,有m条双向路径,其中有一个宝物在n点,已知有k个传送门,每一个传送门可以从x点到达y点,传送门单向的,通过传送门传送不算距离,现在从1点开始,若能拿到宝物,输出走过的最短距离,若无法拿到,请输出-1。

    输入
  • 第一样输入3个数n, m 和k,代表有n个点,m条双向路径以及k个传送门

  • 接下来m行,每一行输入三个数x,y,l代表双向路径从x到y的距离是l

  • 接下来k行,每一行输入两个数x,y表示x和y之间有传送门

  • 1<=n<=2000, 1<=m<=50000, 1<=k<=100, 1<=x,y<=n, 1<=l<=100

    输出
  • 对于每一组数据,输出一个答案代表拿到宝物走过的最短距离

    样例输入
  • 5 3 2

  • 1 2 1

  • 2 3 1

  • 3 4 1

  • 4 5

  • 1 2

    样例输出
  • 2

    分析
  • 最直接的最短路,直接建图跑dijkstra即可

    解法
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 2002;
    const int INF = 0x3f3f3f3f;
    struct Edge {
      int u, v, w;
      int next;
    }E[maxn *100];
    int head[maxn];
    int cnt;
    void init() {
      memset(head, -1, sizeof(head));
      cnt = 0;
    }
    void add_edge(int u, int v, int w) {
      E[cnt].u = u;
      E[cnt].v = v;
      E[cnt].w = w;
      E[cnt].next = head[u];
      head[u] = cnt++;
    }
    int n;
    int vis[maxn];
    int dis[maxn];
    int gao(int s, int t){
      for(int i = 1;i <= n;i++) vis[i] = 0;
      for(int i = 1;i <= n;i++) dis[i] = (i == s ? 0 : INF);
      dis[1] = 0;
      for(int i = 1;i <= n;i++) {
          int x, minn = INF;
          for(int j = 1;j <= n;j++){
              if(!vis[j] && dis[j] <= minn){
                  x = j;
                  minn = dis[j];
              }
          }
          vis[x] = 1;
          for(int j = head[x]; j != -1; j = E[j].next){
              int y = E[j].v;
              int w = E[j].w;
              dis[y] = min(dis[y], dis[x] + w);
          }
      }
      if (dis[n] == INF) return -1;
      return dis[n];
    }
    int main() {
      int m, k;
      while (cin >> n >> m >> k) {
          init();
          int a, b, w;
          while (m--) {
              cin >> a >> b >> w;
              add_edge(a, b, w);
              add_edge(b, a, w);
          }
          while (k--) {
              cin >> a >> b;
              add_edge(a, b, 0);
          }
    
          cout << gao(1, n) << endl;
      }
      return 0;
    }

    文章首发于公众号“面鲸”,欢迎关注~

全部评论

(15) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐