京东2022届暑期实习 Java研发笔试真题 4/24场

题目描述

题目比较简单 总共两道
第一道题 就是求数组中出现最多的数和次数,用投票法可秒,类似剑指 Offer 39. 数组中出现次数超过一半的数字

第二道题:抽卡牌游戏

题目描述:
初始位置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-1i-3
i-1非常直观 直接在dp[i-1]的每个序列后 添加一个i就可以
但是这种添加的方法实际上 限定了最后两个位置分别是i-1i的形式

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

dp[i] = dp[i-1]+dp[i-3]

举个例子:
以1结尾的序列有:01
以2结尾的序列有:012
以3结尾的所有序列有: 0123、0213
以4结尾的所有序列可以从

  • 以3结尾的序列末尾直接添加4得到 01234、02134
  • 以1结尾的序列末尾添加324得到,01324
    所以以4结尾的合法序列总共有3种
    dp[4]=dp[3]+dp[1]

类似地也有以5结尾的序列有:

  • 以4结尾的序列末尾直接添加4得到 012345、021345、013245
  • 以2结尾的序列末尾添加435得到,012435