(B卷,100分)- 最远足迹（Java & JS & Python）

题目描述

某探险队负责对地下洞穴进行探险。探险队成员在进行探险任务时，随身携带的记录器会不定期地记录自身的坐标，但在记录的间隙中也会记录其他数据。探索工作结束后，探险队需要获取到某成员在探险过程中相对于探险队总部的最远的足迹位置。

1. 仪器记录坐标时，坐标的数据格式为(x,y)，如(1,2)、(100,200)，其中0<x<1000，0<y<1000。同时存在非法坐标，如(01,1)、(1,01)，(0,100)属于非法坐标。
2. 设定探险队总部的坐标为(0,0)，某位置相对总部的距离为：x*x+y*y。
3. 若两个座标的相对总部的距离相同，则第一次到达的坐标为最远的足迹。
4. 若记录仪中的坐标都不合法，输出总部坐标（0,0）。

备注：

不需要考虑双层括号嵌套的情况，比如sfsdfsd((1,2))。

输入描述

字符串，表示记录仪中的数据。

如：ferga13fdsf3(100,200)f2r3rfasf(300,400)

输出描述

字符串，表示最远足迹到达的坐标。

如： (300,400)

用例

题目解析

本题首先需要解析出输入字符串s中，括号对中的坐标，我的策略是，遍历输入的字符串：

• 如果遇到 '(' 字符，则记录该字符的索引 i + 1 为L，即坐标的左边界（左闭）
• 如果遇到 ')' 字符，则取该字符的所有 i 为R，即坐标的右边界（右开），然后截取s.substr(L,R)，取得括号对中的内容

取得括号对中的内容后，首先需要按照“,”分隔，得到两个子串x，y，此时根据题意，需要对x，y做校验：

• 题目说(01,1)、(1,01)为非法坐标，即x，y不能含有前导0
• 题目说0<x<1000，0<y<1000，因此x，y转为整型后，只能处于0~1000范围之内，不含0，1000

如果校验合法，则此时计算坐标到起点的距离为 far = x * x + y * y，如果far > maxFar，则更新最远坐标信息，否则不更新。

若两个座标的相对总部的距离相同，则第一次到达的坐标为最远的足迹。

对于相同最远距离的坐标，由于后出现的最远距离坐标不满足far > maxFar，因此不会覆盖前面最远坐标信息。

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.nextLine()));
  }

  public static String getResult(String s) {
    int maxFar = 0;
    String ans = "(0,0)";

    int l = 0;
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      if (c == '(') {
        l = i + 1;
      } else if (c == ')') {
        String[] pos = s.substring(l, i).split(",");

        if (pos[0].charAt(0) == '0' || pos[1].charAt(0) == '0') continue;

        int x = Integer.parseInt(pos[0]);
        int y = Integer.parseInt(pos[1]);

        if (x <= 0 || x >= 1000 || y <= 0 || y >= 1000) continue;

        int far = x * x + y * y;
        if (far > maxFar) {
          maxFar = far;
          ans = "(" + x + "," + y + ")";
        }
      }
    }

    return ans;
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(line));
});

function getResult(s) {
  let maxFar = 0;
  let ans = "(0,0)";

  let l = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] == "(") {
      l = i + 1;
    } else if (s[i] == ")") {
      let [x, y] = s.slice(l, i).split(",");

      if (x[0] == "0" || y[0] == "0") continue;

      x = parseInt(x);
      y = parseInt(y);

      if (x <= 0 || x >= 1000 || y <= 0 || y >= 1000) continue;

      const far = x * x + y * y;
      if (far > maxFar) {
        maxFar = far;
        ans = `(${x},${y})`;
      }
    }
  }

  return ans;
}

Python算法源码

# 输入获取
s = input()


# 算法入口
def getResult():
    maxFar = 0
    ans = "(0,0)"

    l = 0
    for i in range(len(s)):
        if s[i] == '(':
            l = i + 1
        elif s[i] == ")":
            x, y = s[l:i].split(",")

            if x[0] == '0' or y[0] == '0':
                continue

            x = int(x)
            y = int(y)

            if x <= 0 or x >= 1000 or y <= 0 or y >= 1000:
                continue

            far = x ** 2 + y ** 2
            if far > maxFar:
                maxFar = far
                ans = f"({x},{y})"

    return ans


# 调用算法
print(getResult())