4.29京东笔试求题解

贴一个第一题100%代码 import java.util.*; class Main{     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int k = sc.nextInt();         int dp[] = new int[n+1];         for(int i=0;i<k;i++){             dp[i] = 1;         }         // dp[k] = 1;         for(int i=k;i<=n;i++){             dp[i] = (dp[i-1] + dp[i-k])%998244353;         }         System.out.println(dp[n]);     }    }

第二题是连通域+二分，我A了80%，后面的超时了，时间复杂度O(n²logN)，n为元素个数，N为坐标最大值，估计是因为用的python，没时间改写Java了。按理O(n²logN)不应该超时的。 连通域的求解可以是并查集、dfs、bfs，都行，二分的指标是距离也就是那个参数k，最终满足所有路由器恰好只有一个连通域。

第一个就是小青蛙跳台阶的dp 一次跳一步和一次跳k步 求第二题题解

https://www.nowcoder.com/discuss/945159    代码太多  要求1000个以内  我就单独发了  需要的可以瞅瞅  java的

求个第二题代码

没有一道100%😥

第一题我用的dfs，81%，第二题用的最小生成树36%，蹲一个解答

第二题改一下迪杰斯特拉？

原来第一题dp就可以。。我用的dfs超时了。 第二题我只过了18%，我是把坐标转化为图的邻接矩阵，然后魔改fyoid算法，把求最短路径改为“找这样一个路径：组成该路径的最长边尽可能短”。

第一题暴力回溯81%，第二题没看懂 18%😣

第一题一直所有测试样例报错，直接输出4反倒过了18