360笔试(8.31)编程第二题 散步

思路

参考:https://blog.csdn.net/likewind1993/article/details/100176127

这次的两道编程题都比较简单,看到第二题大家用dfs来做的比较多,这里提供一个动态规划的思路。

设置两个长度为n+1的dp1、dp2数组,dp[i]表示某次停下是否能到第i个位置,dp[i] = 0表示不能到达,dp[i] = 1表示能到达

  1. 初始dp1[1...n] = 1,表示可以从任意的位置出发,

  2. 对每走Di距离,方向可以向左走或向右走,那么走完Di距离后,可到达的位置用dp2表示,即,转移方程为:

    if (dp1[j] == 1 && j + d[i] <= n )
         dp2[j + d[i]] = 1;
    if (dp1[j] == 1 && j - d[i] >= 1 )
         dp2[j - d[i]] = 1;
  3. dp1 = dp2,重复步骤2。

对每走一步都要对进行一次遍历,总共N x M次, 所以时间复杂度,空间复杂度

代码

#include <iostream>
#include <vector>
using namespace std;

void get_res(int n, int m, vector<int> & d)
{
    vector<int> dp1(n + 1, 0);
    vector<int> dp2(n + 1, 0);

    for (int i = 0; i <= n; ++i)
        dp1[i] = 1;
    for (int i = 0; i < m; ++i)
    {
        for(int j = 1; j<= n; ++j)
            dp2[j] = 0;
        for (int j = 1; j <= n; ++j)
        {
            if (dp1[j] == 1 && j + d[i] <= n )
                dp2[j + d[i]] = 1;
            if (dp1[j] == 1 && j - d[i] >= 1 )
                dp2[j - d[i]] = 1;
        }
        dp1 = dp2;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (dp2[i] == 1)
            ++ans;
    }
    cout << ans << endl;
}

int main()
{
    int n = 0, m = 0;
    cin >> n >> m;
    vector<int> D(m, 0);
    for (int i = 0; i < m; ++i)
        cin >> D[i];

    get_res(n, m, D);
    return 0;
}
#360公司##笔试题目#
全部评论
应该是这样的 void get_res(int n, int m, vector<int> & d) {     vector<int> dp1(n + 1, 1);     for (int i = 0; i < m; ++i)     {         vector<int> dp2(n + 1, 0);         for (int j = 1; j <= n; ++j)         {             if (dp1[j] == 1 && j + d[i] <= n)                 dp2[j + d[i]] = 1;             if (dp1[j] == 1 && j - d[i] >= 1)                 dp2[j - d[i]] = 1;         }         dp1 = dp2;     }     int ans = 0;     for (int i = 1; i <= n; ++i)     {         if (dp1[i] == 1)             ++ans;     }     cout << ans << endl; }
点赞 回复 分享
发布于 2019-08-31 21:27
这个代码有问题吧,dp2清0的位置好像不对
点赞 回复 分享
发布于 2019-08-31 20:51
有dfs做的吗 我用dfs只对了40%多
点赞 回复 分享
发布于 2019-08-31 22:14
dp2[]操作的循环结束后,将dp2赋给dp1是为什么,是说这个最终不能到达的终点,不可以作为另一条 反转路径的起点吗?求解答
点赞 回复 分享
发布于 2019-08-31 22:05
很强
点赞 回复 分享
发布于 2019-08-31 21:27
思路很清晰。
点赞 回复 分享
发布于 2019-08-31 20:18

相关推荐

07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
3
14
分享

创作者周榜

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