08-18 15:41 门头沟学院 后端 发布于浙江
关注
科大讯飞笔试第三题
求每个位置的最大价值，我直接用l和r指向当前位置的左右邻居，然后比较如果大于当前最大价值，从左右合法的数里选最小的。然后一直卡20%。
感觉想出来的解答不对，动态规划看着也不像。请问各位大佬如何求解？ #科大讯飞求职进展汇总#
感觉想出来的解答不对，动态规划看着也不像。请问各位大佬如何求解？ #科大讯飞求职进展汇总#
全部评论
不服输的芭乐很理智
华中科技大学 C++
第三题是根据条件可知最长合并的情况是1，2， 4， 8， 16，...，2^30，说明区间长度最大不会超过30，直接对每个位置dfs加记忆化搜索
int m[1e5][30];
int ps[1e5]; // 前缀和
int n;
int arr[1e5];
int dfs(l, size) {
if(m[i][size]!=-1)return m[i][size];
int r = i+size-1;
int sum = ps[r+1]-ps[l];
int ans=sum;
if(r+1<n && sum < arr[r+1]){
ans = dfs(l, size+1);
}
if(l-1>=0 && sum < arr[l-1]){
ans = max(ans, dfs(l-1, size+1));
}
m[l][size] = ans;
return ans;
}
已注销
同20，问题在于没考虑到左右相等情况，我举个例子12 12 1 12 30，这里1左右都一样，但是选左边就不对，看别人说要用dfs
牛客48194111号
华东师范大学 Java
这样的话思路不对，比如100000 3 1 2这个例子从1开始扩展就会出错。因为我开始这是这么做的😂。我用dfs做的过了，就是每一步有向右扩展，向左扩展两种选择，直到无法扩展就停止记录下来此时的sum到一个list里面，然后找到list里面的最大值就可以了，本来以为会超时结果过了，神奇
隔离却吃席
吉林大学 嵌入式软件开发
递归深搜每一位，规定左右边界，满足条件向下递归，dp进去维护每一位最大值，这也不算动态规划，就模拟就好了
klk333
门头沟学院 后端
思路不对，比如5 3 1 2
牛客800736750号
电子科技大学 前端工程师
回溯 或者 dfs每次搜索左右就好了
我一点都不会写代码
西安交通大学 算法工程师
多少分过啊
在走神的劳伦斯很想吃烤肉
门头沟学院 深度学习
第三题dfs过了，第二题暴力只过了11%，然后改成维护数量后排序过了5％，感觉把排序改成堆可以多过一些，可惜最后没时间了，时间全浪费在最后一题了。。。
左家垅菜腿
中南大学 嵌入式软件开发
dfs爆搜😸
相关推荐
水滴公司氛围 20人发布
查看9道真题和解析