前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >一道网易面试编程题

一道网易面试编程题

作者头像
ShenduCC
发布2018-04-27 12:27:21
7760
发布2018-04-27 12:27:21
举报
文章被收录于专栏:算法修养

一条长为n的路,需要用路灯点亮,其中"."表示需要点亮的位置,"X"表示无需点亮的位置,假设灯立在i处,则它可以点亮i-1,i,i+1三个位置,问至少需要多少灯才能点亮整条路。

乍一看,肯定是动态规划:

上代码,敲了两个小时的动态规划:

代码语言:javascript
复制
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>

using namespace std;
const int  INF=10000000;
char a[105];
//到i点至少点燃了x个灯,最后一个灯的位置为j的情况下,道路被点亮了
int dp[105][105];
int main()
{
    
    scanf("%s",a+1);
    int len = strlen(a+1);
    
    for(int i=0;i<=100;i++)
    {
        for(int j=0;j<=100;j++)
        {
            dp[i][j]=INF;
        }
    }
  
    dp[0][0]=0;
    for(int i=1;i<=len;i++)
    {
        
        for(int j=0;j<=i-1;j++)
        {
            if(dp[i-1][j]==INF) continue;
            if(a[i]=='X')
            {
                dp[i][j]=min(dp[i][j],dp[i-1][j]);
              
            }
            else if(a[i]=='.')
            {
                if(j==i-1&&j!=0)
                    dp[i][j]=min(dp[i][j],dp[i-1][j]);
                else
                    dp[i][i]=min(dp[i][i],dp[i-1][j]+1);
            }
            
          
        }
        for(int j=0;j<=i-2;j++)
        {
            if(dp[i-2][j]==INF) continue;
            if(a[i]=='X'&&a[i-1]=='X')
                dp[i][j] = min(dp[i][j],dp[i-2][j]);
            else
            {
                if(j==i-2&&j!=0)
                {
                    if(a[i]=='X')
                        dp[i][j] = min(dp[i][j],dp[i-2][j]);
                    else if(a[i]=='.')
                        dp[i][i] = min(dp[i][i],dp[i-2][j]+1);
                }
                else
                {
                    dp[i][i] = min(dp[i][i],dp[i-2][j]+1);
                    dp[i][i-1]=min(dp[i][i-1],dp[i-2][j]+1);
                }
                
            }
            
        }
        
        for(int j=0;j<=i-3;j++)
        {
            if(dp[i-3][j]==INF) continue;
            if(a[i]=='X'&&a[i-1]=='X'&&a[i-2]=='X')
                dp[i][j] = min(dp[i][j],dp[i-3][j]);
            
            else
            {
                if(j==i-3&&j!=0)
                {
                    if(a[i]=='X'&&a[i-1]=='X')
                        dp[i][j] = min(dp[i][j],dp[i-3][j]);
                    else
                    {
                        dp[i][i] = min(dp[i][i],dp[i-3][j]+1);
                        dp[i][i-1]=min(dp[i][i-1],dp[i-3][j]+1);
                    }
                }
                else
                {
                    if(a[i]=='X')
                        dp[i][i-2]=min(dp[i][i-2],dp[i-3][j]+1);
                    else if(a[i-2]=='X')
                        dp[i][i]=min(dp[i][i],dp[i-3][j]+1);
                    else
                        dp[i][i-1]=min(dp[i][i-1],dp[i-3][j]+1);
                }
            }
           
        }
        
        
    }
    for(int i=0;i<=len;i++)
    {
        if(dp[len][i]!=INF)
        {
            printf("%d\n",dp[len][i]);
            break;
        }
    }
    return 0;
}

 而实际上呢,如果不要那么浮躁,再看看题目,你就会发现,这题目贪心就能解决。只要有"."在长度为3的范围内,点亮一个火把就可以了。

代码语言:javascript
复制
#include <iostream>

using namespace std;
char s[105];

int solve(char s[], int n) {
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == '.') {
            ans++;
            s[i] = 'X';
            if(i+1 < n&&s[i+1] == '.') s[i+1] = 'X';
            if(i+2 < n&&s[i+2] == '.') s[i+2] = 'X';
        }
    }
    return ans;
}
int main()
{
    scanf("%s",s);
    printf("%d",solve(s,strlen(s)));
    return 0;
}

从这道题目,也可以看出,一个浮躁状态的人是不会多想,有一点想法就会去义无反顾的走下去,浪费时间精力,并且在没有想清楚的情况下就去否定别人的解决,想当然,并且急躁。

一个好的编程人员,一定是会有一个好的编程心境!这至关重要!

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-03-28 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档