4.24 京东笔试

第一题就是求众数 投票法a掉
第二题抽卡序列 动规解
题目描述:
初始位置0已有卡片0,现在有1~n的卡片,从卡牌中随机抽一张出来加入末尾,求满足下面条件的卡牌序列有多少种
1、最末尾位置为卡片n
2、相邻两位置卡片数字的差值绝对值大小不超过2

输入 3
输出 2
解释: 有2个合法的序列 {0,1,2,3}、{0,2,1,3}
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        dp[1] = 1; 
        dp[2] = 1; 
        dp[3] = 2; 

        int MOD = 998244353;

        for(int i = 4;i < n + 1;i++){
            dp[i] = (dp[i-1] + dp[i-3])%MOD;
        }
        System.out.println(dp[n]);

    }
}
简单说下我的思路,以i结尾的序列可以由i-1、i-3计算到
i-1非常直观 直接在dp[i-1]的每个序列后 添加一个i就可以
但是这种添加的方法实际上限定了最后两个位置分别是i-1,i

实际上最后2个位置还可以是i-2,i
所以在dp[i-3]的所有序列后面固定添加{i-1,i-2,i}的序列也是解

即dp[i] = dp[i-1]+dp[i-3]
#京东##笔试题目#
全部评论
第二题愣是没推出状态转移方程,用的DFS递归+回溯,时间复杂度太高了,n在60以上就超时,1000以上直接栈溢出,最后只过了36%🤣
2 回复 分享
发布于 2021-04-24 21:59
第一次全ac,不过选择很多是懵的
1 回复 分享
发布于 2021-04-24 21:39
同样做法,忘记取模了。。
1 回复 分享
发布于 2021-04-24 21:12
楼主可以贴一下第一题的题目和答案吗🤣
点赞 回复 分享
发布于 2021-04-25 13:34
大伙都这么强我怕是过不了线
点赞 回复 分享
发布于 2021-04-25 11:04
大佬几个offer了
点赞 回复 分享
发布于 2021-04-25 01:37
投票法做不出来吧 投票得是 1 1234 最后输出的是4
点赞 回复 分享
发布于 2021-04-25 00:49
请问笔试结束后 官网状态还是投递吗
点赞 回复 分享
发布于 2021-04-24 22:16
麻了第二题
点赞 回复 分享
发布于 2021-04-24 21:43
问一下没有提交子卷,最后系统会自动提交吗
点赞 回复 分享
发布于 2021-04-24 21:05
求第二题解答
点赞 回复 分享
发布于 2021-04-24 21:02
求第二题
点赞 回复 分享
发布于 2021-04-24 20:54
我22号投的,可是没有笔试通知啊,然后官网状态是“ 笔试完成,初试官筛选中”,这是什么情况?java开发岗。
点赞 回复 分享
发布于 2021-04-24 20:09

相关推荐

不愿透露姓名的神秘牛友
07-07 13:46
点赞 评论 收藏
分享
人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
缒梦&独舞:这家公司是这样的,去年给我实习offer了,不过也是面着玩儿的,他周六还要去做公益志愿活动
点赞 评论 收藏
分享
码农索隆:单休一个月少休息4天,一年就是48天,平时节假日,别人3天假期,单休的两天
点赞 评论 收藏
分享
评论
5
15
分享

创作者周榜

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