C/C++教程

leetcode5964. 执行所有后缀指令(mid)(273周赛)

本文主要是介绍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周赛)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!