头条笔试五道编程题

题目过几天应该会放出来给大家练习

#include <iostream> using namespace std; const int mod = 1e9 + 7; int dp_1[10000],dp_2[10000]; int main() {     int n;     cin >> n;     dp_1[0] = 10;     for (int i = 1;i<n;i++)     {         dp_1[i] = dp_1[i - 1] * 10;     }     dp_2[0] = dp_1[0];     dp_2[1] = dp_1[1];     for (int i = 2;i<n;i++)     {         dp_2[i] = (dp_1[i] + dp_2[i - 2])%mod;         for (int j = 1;j<n-1;i++)         {             dp_2[i] += (dp_2[j] * dp_2[i - j - 1])%mod;         }         dp_2[i] %= mod;     }     cout << dp_2[n - 1]; } 第二题答案。 不能检测了，不敢说对。但思想没毛病。dp_1表示只有字符的情况。dp_2[i]要加上dp_2[i-2], 是考虑括号。最后的循环是考虑加号。

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() {          int a,b;     scanf("%d%d", &a, &b);     vector<int> ans(a, 0),tmp(a,1);     for (int i = 0;i<a;i++)     {         scanf("%d", &ans[i]);     }     for (int i = 1;i<a;i++)     {         for (int j = 0;j<i;j++)         {             if (ans[i]>=ans[j])             {                 tmp[i] = max(tmp[i], tmp[j] + 1);             }         }     }     cout << *max_element(tmp.begin(), tmp.end())+b-1; } //第四题答案，刚才转念一想，做复杂了。因为是重复的序列，我本来是在全局序列之中求最长上升子序列 其实只需在第一个序列之中求最长上升序列，并且其中的最大元素在后面的每个序列之中一定存在，顾加上 b-1。

//第一题 dfs import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class test1 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int num = scan.nextInt(); Queue<Integer>[] queue = (LinkedList<Integer>[]) new LinkedList[num+1]; for (int i = 1; i <= num; i++){ queue[i] = new LinkedList<>(); } for (int i = 1; i <= num; i++){ int k = scan.nextInt(); while (k != 0){ queue[i].add(k); queue[k].add(i); k = scan.nextInt(); } } boolean[] marked = new boolean[num+1]; //维护一个标记数组 int count = 0; for (int i = 1; i <= num; i++){ if (!marked[i]) { dfs(queue, marked, i); count++; } } System.out.println(count); } public static void dfs(Queue<Integer>[] queue, boolean[] marked, int v){ marked[v] = true; for (int w : queue[v]){ if (!marked[w]) { dfs(queue, marked, w); } } } }

这些题感觉非竞赛选手会做自闭的 ……

https://www.jianshu.com/p/0b0f11b89982 第二题还是没什么思路

抢沙发，等解答

等答案

第一题不是bfs么？各种超时

等答案

第三题读取一直有问题...最后没有回车怎么解决

等答案+1

坐等答案！！

坐等答案。

我也截图留下来了 两次都有（笑哭）

第五题我看输出格式就没有做的动力了。

太难了

//第一题DFS思路，空间还能优化，没提交，不知道对不对 #include <iostream> #include <vector> using namespace std; int n; int res; void dfs(vector<vector<int>>& friends, int x, int y,vector<vector<bool>>& mark){ if(x >= friends.size() || y >= friends[0].size() || x < 0 || y < 0) return; if(mark[x][y] == true) return; if(friends[x][y] == 0){ mark[x][y] = true; return; } // 对于已经搜索过的点要进行标记 mark[x][y] = true; res--; for(int j=1; j<n; j++){ dfs(friends, x, j, mark); } } void minM(vector<vector<int>>& friends) { if(friends.empty()) return; res = n; vector<vector<bool>> vecMark(friends.size(),vector<bool>(friends[0].size(),false));// 定义标记数组 //开始搜索 for(int i = 1;i < friends.size();i++){ for(int j = 1;j < friends[0].size();j++){ if(vecMark[i][j] == true) continue; if(friends[i][j] == 0){ vecMark[i][j] = true; continue; } dfs(friends, i, j, vecMark); } } cout << num << endl; } int main() { cin >> n; vector<vector<int>> friends(n+1, vector<int>(n+1,0)); int temp = 0; for(int i=1; i<=n; i++){ int j = 1; while(cin>>temp){ if(temp == 0) break; friends[i][j] = temp; j++; } } minM(friends); return 0; }

//第一题并查集思路，供参考 #include <stdio.h> #define N 100020 int friends[N];//每个人所属的连通分量，即构成朋友树时每个人的父节点 int rank[N];//连通分量的权值，即朋友树的大小 int res; void init(int n)//初始化initialization { for(int i=0;i<n;i++) { friends[i]=i; rank[i]=0; } } int findRoot(int x)//寻找x所属的朋友树的根节点 { //一直向上遍历寻找根节点 while(x != friends[x]) x = friends[x]; return x; } void connect(int x,int y) { int xRoot = findRoot(x); int yRoot = findRoot(y); if(xRoot == yRoot) return ; //判断树高，小树并在大树下 if(rank[xRoot] < rank[yRoot]) friends[xRoot]=yRoot; else { friends[yRoot] = xRoot; if(rank[xRoot]==rank[yRoot])//两树高相等，合并后树高+1 rank[xRoot]++; } --res; } int main() { int n; init(N);//初始化 scanf("%d",&n); res = n; for(int i=1;i<=n;i++){ int t; while(~scanf("%d",&t)){ if(t == 0) break; connect(i,t); } } printf("%d",res); return 0; }