首页 > 代码库 > 大众点评笔试题最后两题题解
大众点评笔试题最后两题题解
问题1:
这是一道动态规划的问题,状态转移方程为
dp[i] = dp[i-3] + dp[i-1] , i>= 3(i<3时dp[i]=1,只有1种情况)
我这里直接开了一个dp数组解决这个问题。在init方法中进行了初始化。
另外,考虑到为了方便测试,我用了一个递归函数dfs(m,n,str)来进行对所有情况的输出。具体见代码:dfs函数的功能就是输出所有的可行方案。
如:当我输入5的时候,输出:
4
所有方案:
11111
211
121
112
同时我设定了数n的范围,当n<0时或n大于我设定的范围时,会提示出错。
下面是C++代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <string> using namespace std; const int maxn = 1010; int dp[maxn]; void init() { dp[0] = dp[1] = dp[2] = 1; for(int i=3;i<maxn;i++) dp[i] = dp[i-1] + dp[i-3]; } void dfs(int m,int n,string str) { if(m == 0) { cout << str << endl; return; } if(m >= 1) dfs(m-1 , n , "1"+str); if(m >= 3) dfs(m-3 , n , "2"+str); return; } int main() { int n; init(); while(scanf("%d" , &n) != EOF) { if(n < 0) { puts("这段路的长度不能为负数!\n"); continue; } if(n >= 1010) { puts("我这里设定的最大长度是1009,如果需要改变长度,请联系相关人员!"); continue; } int ans = dp[n]; printf("%d\n" , ans); printf("所有方案:\n"); dfs(n , n , ""); } return 0; }
问题2:
首先通过代码得到二进制数:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; void get(int n) { if(n == 0) return; get(n/2);printf("%d" , n%2); } int main() { get(3593); return 0; }
1)至少需要开12个线程。
首先我把3593表示成二进制数,为111000001001,一共有12位,然后我开十二个进程,第i个进程中包含所有二进制表示中第i位为0的用户的集合,如果算法能够检测到违规用户,那么违规用户的第i位二进制数就是0,否则为1.这样开12个线程就能得到第i位用户的所有二进制位的数字,以此得到该违规用户的数字。
2)至少需要开6个。
第一秒先判断3593的前6个二进制位;
第二秒判断3593的后6个二进制位。
方法同1)。
注:2)的解答不一定对。
大众点评笔试题最后两题题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。