算法思路

本题的关键是从起点（0, 0）开始，根据给定的指令（例如A10, S20等）计算移动后的最终坐标。需要做的是：

  1. 解析指令，并根据指令修改坐标。
  2. 跳过无效的指令，避免影响最终结果。
  3. 合法的指令格式为：一个方向符号（A, D, W, S）加上一个两位数以内的数字，其他格式为无效指令。

具体步骤如下：

  1. 解析指令：每个指令由一个方向符号（A, D, W, S）和一个数字组成，指令之间使用分号 ; 分隔。
  2. 判断指令合法性：有效的指令应该符合以下格式：
    • 以A, D, W, S中的一个字符开头，后面紧跟着1到2位的数字。
    • 其他的字符串或格式错误的指令需要被忽略。
  3. 处理坐标变化：
    • A: 向左移动，x坐标减小。
    • D: 向右移动，x坐标增加。
    • W: 向上移动，y坐标增加。
    • S: 向下移动，y坐标减小。
  4. 输出最终坐标：所有有效的指令处理完毕后，输出最终的坐标。

Code

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // 读取输入字符串
    const input = await readline();
    
    // 初始化起始坐标
    let x = 0, y = 0;

    // 将输入按分号分割成各个指令
    const instructions = input.split(';');
    
    // 遍历每个指令
    for (const instruction of instructions) {
        // 使用正则表达式匹配有效的指令格式
        const match = instruction.match(/^[ADWS](\d{1,2})$/);
        
        if (match) {
            // 获取数字部分
            const value = parseInt(match[1]);
            
            // 根据方向符号更新坐标
            switch (instruction[0]) {
                case 'A': // 向左
                    x -= value;
                    break;
                case 'D': // 向右
                    x += value;
                    break;
                case 'W': // 向上
                    y += value;
                    break;
                case 'S': // 向下
                    y -= value;
                    break;
            }
        }
    }

    // 输出最终坐标
    console.log(`${x},${y}`);
}();

复杂度分析

  • 时间复杂度：
    • 输入的字符串最长长度为 10,000，每个指令最多包含 3 个字符（例如A10）。因此，字符串的总长度为 O(n)。
    • 遍历每个指令，并对每个指令进行正则匹配，匹配的时间复杂度为 O(1)，因为每个指令的长度是固定的。
    • 因此，整体的时间复杂度为 O(n)，其中 n 是输入字符串的长度。
  • 空间复杂度：
    • 我们使用了一个字符串数组来存储指令（split(';')），这个数组的大小为 O(n)。
    • 另外，使用了常数空间来存储坐标和临时变量。因此，空间复杂度为 O(n)。