2021-04-11 百度 笔试

第三题根据 https://www.nowcoder.com/discuss/637603?type=post&order=create&pos=&page=1&channel=-1&source_id=search_post_nctrack   大佬提供的思路，使用dp写了一版Java代码，测试用例都过了，贴在这里交流下。 思路如下： 动态规划： * 1. 定义状态：dp[i][j] （0=<i<k, 0<=j<s.length）代表第（i+1）次操作时，将字符串s开头的j个字符交换到s的末尾的路径数 * 2. 状态转移方程：dp[i][j] = sum(dp[i-1][l], 0<= l <s.length && j != l) *    边界：i-1>=0, i>=1, i=0是边界 * 3. 初始化: dp[0][0] = 0; dp[0][j] = 1,(0< j <s.length) * 4. 输出：当s.substring(j,len) + s.substring(0,j)) == t 时，j∈[0,s.length), 输出dp[k-1][j]

今天又看了下第二题，考试前没刷过图的题不会做，这下顺道学了一下图的遍历。第二题用图存储输入数据，计算牛牛顶点的出度（胜了几个人）和入度（输了几个人），在这个范围内遍历输出就是排名。写一版Java代码，弄了两个测试用例通过。

第一题路径长度是怎么算的，我怎么没看懂

我编程只有两题。。第一题是密码解密 第二题是前缀交换求不同结果。。。

请问楼主收到面试通知了吗？