前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【LeetCode】5728. 最少侧跳次数

【LeetCode】5728. 最少侧跳次数

作者头像
韩旭051
发布2021-04-14 14:55:14
2490
发布2021-04-14 14:55:14
举报
文章被收录于专栏:刷题笔记刷题笔记
  1. 最少侧跳次数 显示英文描述 通过的用户数1397 尝试过的用户数2030 用户总通过次数1416 用户总提交次数3621 题目难度Medium 给你一个长度为 n 的 3 跑道道路 ,它总共包含 n + 1 个 点 ,编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ,它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles ,其中 obstacles[i] (取值范围从 0 到 3)表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ,那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。

比方说,如果 obstacles[2] == 1 ,那么说明在点 2 处跑道 1 有障碍。 这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍,这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道(这两条跑道可以不相邻),但前提是跳过去的跑道该点处没有障碍。

比方说,这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。 这只青蛙从点 0 处跑道 2 出发,并想到达点 n 处的 任一跑道 ,请你返回 最少侧跳次数 。

注意:点 0 处和点 n 处的任一跑道都不会有障碍。

示例 1:

输入:obstacles = [0,1,2,3,0] 输出:2 解释:最优方案如上图箭头所示。总共有 2 次侧跳(红色箭头)。 注意,这只青蛙只有当侧跳时才可以跳过障碍(如上图点 2 处所示)。 示例 2:

输入:obstacles = [0,1,1,3,3,0] 输出:0 解释:跑道 2 没有任何障碍,所以不需要任何侧跳。 示例 3:

输入:obstacles = [0,2,1,0,3,0] 输出:2 解释:最优方案如上图所示。总共有 2 次侧跳。

提示:

obstacles.length == n + 1 1 <= n <= 5 * 105 0 <= obstacles[i] <= 3 obstacles[0] == obstacles[n] == 0

我写了这么多也没过

代码语言:javascript
复制
class Solution {
public:
    int minSideJumps(vector<int>& obstacles) {
        int len = obstacles.size();
        vector<vector<int>>v(len,vector<int>(3,999999));
        v[0][1]=0;
        if(obstacles[0]!=0){
            v[0][0]=1;
        }
        if(obstacles[0]!=2){
            v[0][2]=1;
        }
        for(int i=1;i<len;i++){
           if(obstacles[i]==0){
               v[i][0]=v[i-1][0];
               v[i][1]=v[i-1][1];
               v[i][2]=v[i-1][2];
           }
            else if(obstacles[i]==1){
               //v[i][0]=v[i-1][0];
               v[i][1]=v[i-1][1];
               v[i][2]=v[i-1][2];
           }
           else if(obstacles[i]==2){
               v[i][0]=v[i-1][0];
               //v[i][1]=v[i-1][1];
               v[i][2]=v[i-1][2];
           }
           else if(obstacles[i]==3){
               v[i][0]=v[i-1][0];
               v[i][1]=v[i-1][1];
               //v[i][2]=v[i-1][2];
           }
            int mix = 999999;
            if(v[i][0]<mix)mix =v[i][0];
             if(v[i][1]<mix)mix =v[i][1];
             if(v[i][2]<mix)mix =v[i][2];
            
            if(obstacles[i]==0){
                if(v[i][0]>(mix+1))v[i][0]=mix+1;
                if(v[i][1]>(mix+1))v[i][1]=mix+1;
                if(v[i][2]>(mix+1))v[i][2]=mix+1;
            }else if(obstacles[i]==1){
                 //if(v[i][0]>mix)v[i][0]=mix+1;
                if(v[i][1]>(mix+1))v[i][1]=mix+1;
                if(v[i][2]>(mix+1))v[i][2]=mix+1;
             
             }else if(obstacles[i]==2){
                 if(v[i][0]>(mix+1))v[i][0]=mix+1;
                //if(v[i][1]>mix)v[i][1]=mix+1;
                if(v[i][2]>(mix+1))v[i][2]=mix+1;
             
             }else if(obstacles[i]==3){
                 if(v[i][0]>(mix+1))v[i][0]=mix+1;
                if(v[i][1]>(mix+1))v[i][1]=mix+1;
                //if(v[i][2]>mix)v[i][2]=mix+1;
             }
            if(i>900){
                //cout<<mix<<endl;
            }
            
        }
        int i = len -1;
         int mix = 999999;
            if(v[i][0]<mix)mix =v[i][0];
             if(v[i][1]<mix)mix =v[i][1];
             if(v[i][2]<mix)mix =v[i][2];
            return mix;
    }
};

知道是 dp 为啥别人写的 就很精简 其实思路 都是那个思路 咋我那个就容易出问题 就没AC

代码语言:javascript
复制
class Solution
{
public:
	vector<int> run(vector<int> last, int ob) {
		vector<int> cur(3);
		for (int i = 0; i < 3; ++i) {
			cur[i] = (i == ob ? 1000000 : last[i]);
		}
        for (int i = 0; i < 3; ++i) {
            if (i != ob) {
                for (int j = 0; j < 3; ++j) {
                    if (i != j) {
                        cur[i] = min(cur[i], cur[j] + 1);
                    }
                }
            }
		}
		return cur;
	}
    int minSideJumps(vector<int>& obstacles) 
	{
		vector<int> dp = {1, 0, 1};
		for (int i = 1; i < obstacles.size(); ++i) {
			dp = run(dp, obstacles[i] - 1);
		}
		return min(dp[0], min(dp[1], dp[2]));
	}
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-04-11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

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