leetcode5964. 执行所有后缀指令(mid)(273周赛)
2021/12/27 6:09:15
本文主要是介绍leetcode5964. 执行所有后缀指令(mid)(273周赛),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
执行所有后缀指令
- 题目描述
- 解题思路
- 代码(暴力)
- 复杂度
力扣链接
这一周只完成了这两题,第三题有几个用例过不去,我知道啥时候会过不去,但不知道怎么解决,大佬说是前缀和+二分,但是我不知道这个前缀和从哪里搞起,经验不够,太菜
题目描述
现有一个 n x n
大小的网格,左上角单元格坐标 (0, 0)
,右下角单元格坐标 (n - 1, n - 1)
。给你整数 n
和一个整数数组 startPos
,其中 startPos = [startrow, startcol]
表示机器人最开始在坐标为 (startrow, startcol)
的单元格上。
另给你一个长度为 m
、下标从 0 开始的字符串 s
,其中 s[i]
是对机器人的第 i
条指令:'L'
(向左移动),'R'
(向右移动),'U'
(向上移动)和 'D'
(向下移动)。
机器人可以从 s
中的任一第 i
条指令开始执行。它将会逐条执行指令直到 s 的末尾,但在满足下述条件之一时,机器人将会停止:
- 下一条指令将会导致机器人移动到网格外。
- 没有指令可以执行。
返回一个长度为m
的数组answer
,其中answer[i]
是机器人从第i
条指令 开始 ,可以执行的 指令数目 。
示例 1:
输入:n = 3, startPos = [0,1], s = "RRDDLU" 输出:[1,5,4,3,1,0] 解释:机器人从 startPos 出发,并从第 i 条指令开始执行: - 0: "RRDDLU" 在移动到网格外之前,只能执行一条 "R" 指令。 - 1: "RDDLU" 可以执行全部五条指令,机器人仍在网格内,最终到达 (0, 0) 。 - 2: "DDLU" 可以执行全部四条指令,机器人仍在网格内,最终到达 (0, 0) 。 - 3: "DLU" 可以执行全部三条指令,机器人仍在网格内,最终到达 (0, 0) 。 - 4: "LU" 在移动到网格外之前,只能执行一条 "L" 指令。 - 5: "U" 如果向上移动,将会移动到网格外。
示例 2:
输入:n = 2, startPos = [1,1], s = “LURD”
输出:[4,1,0,0]
解释:
- 0: “LURD”
- 1: “URD”
- 2: “RD”
- 3: “D”
示例 3:
输入:n = 1, startPos = [0,0], s = “LRUD”
输出:[0,0,0,0]
解释:无论机器人从哪条指令开始执行,都会移动到网格外。
提示:
m == s.length
1 <= n, m <= 500
startPos.length == 2
0 <= startrow, startcol < n
s
由'L'
、'R'
、'U'
和'D'
组成
解题思路
- 暴力
代码(暴力)
public int[] executeInstructions(int n, int[] startPos, String s) { int m = s.length(); int[] ans = new int[m]; for (int i = m - 1; i >= 0; --i) { int j = i; int[] temp = Arrays.copyOf(startPos, startPos.length); while (j <= m - 1) { char c = s.charAt(j); boolean flag = false; switch (c) { case 'U' : { if (temp[0] - 1 >= 0) { ++ans[i]; temp[0] -= 1; flag = true; } break; } case 'D' : { if (temp[0] + 1 <= n - 1) { ++ans[i]; temp[0] += 1; flag = true; } break; } case 'L' : { if (temp[1] - 1 >= 0) { ++ans[i]; temp[1] -= 1; flag = true; } break; } default : { if (temp[1] + 1 <= n - 1) { ++ans[i]; temp[1] += 1; flag = true; } } } if (flag) { ++j; } else { break; } } } return ans; } }
复杂度
- 时间复杂度: O(n^2)
- 空间复杂度: O(n)
这篇关于leetcode5964. 执行所有后缀指令(mid)(273周赛)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享