华为OD机试真题：最远足迹 (E卷、C++)

华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

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

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

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

输入描述

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

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

输出描述

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

如： (300,400)

示例1

输入：
ferg(3,10)a13fdsf3(3,4)f2r3rfasf(5,10)输出：
(5,10)说明：
记录仪中的合法坐标有3个： (3,10)， (3,4)， (5,10)，其中(5,10)是相距总部最远的坐标， 输出(5,10)。

示例2

输入：
asfefaweawfaw(0,1)fe输出：
(0,0)说明：
记录仪中的坐标都不合法，输出总部坐标（0,0）。

C++

#include <bits/stdc++.h>using namespace std;// 判断字符串是否为合法的整数
bool isValidNum(const string &str) {// 检查是否没有前导零if (str.empty() || str[0] == '0') return false;for (char ch: str) if (!isdigit(ch)) return false;return true;
}int main() {string input;getline(cin, input);  // 读取输入字符串// 使用正则表达式提取所有形如 (x,y) 的坐标// regex loc_pattern("\\((\\d+),(\\d+)\\)");  // 转义字符串字面量写法regex loc_pattern(R"(\((\d+),(\d+)\))");  // 原始字符串字面量写法smatch match;int max_distance = 0;  // 最大距离的平方string ans = "(0,0)";  // 默认返回总部坐标auto begin = input.cbegin();while (regex_search(begin, input.cend(), match, loc_pattern)) {string x_str = match[1].str();string y_str = match[2].str();// 验证x和y是否为合法的数字，并且没有前导零if (isValidNum(x_str) && isValidNum(y_str)) {int x = stoi(x_str);int y = stoi(y_str);// 验证坐标范围是否合法if(x < 1000 && y < 1000){// 计算距离平方int distance = x * x + y * y;// 如果新的坐标距离更远，更新最远坐标if (distance > max_distance) {max_distance = distance;ans = match[0].str();}}}// 更新匹配起始位置，继续查找下一个begin = match[0].second;}// 输出最远的坐标cout << ans << endl;return 0;
}

这道题目要求我们从一串杂乱的字符串中提取出合法的坐标，并找出距离总部(0,0)最远的坐标。如果所有坐标都不合法，则输出总部坐标 (0,0)。

解题思路

输入解析：从字符串中提取所有形如 (x,y) 的坐标。需要注意的是，坐标中的 x 和 y 可能存在不合法的情况（例如前导零、负数、超过 1000 等）。
合法性判断：
坐标的 x 和 y 必须是正整数，并且不能以零开头。
坐标 (x,y) 的合法性通过检查 x 和 y 是否是有效的正整数并且不以 0 开头来判断。

距离计算：
给定一个坐标 (x,y)，它到总部 (0,0) 的距离为 x^2 + y^2。我们需要通过计算每个坐标的这个值来找出最远的坐标。

返回最远坐标：
在多个坐标具有相同的距离时，选择首次到达的坐标。

边界情况：
如果输入字符串中没有合法坐标，返回 (0,0)。

算法步骤

使用正则表达式提取所有形如 (x,y) 的坐标。
对每个坐标进行合法性判断。
计算每个合法坐标的距离，如果距离比当前最大距离大，则更新最远坐标。
如果没有合法坐标，则输出 (0,0)。

相关知识点

C++ 正则表达式分组捕获入门指南

原始字符串字面量

在 C++ 中，R"(...)" 表示原始字符串字面量（raw string literal），其中的 R 是关键字，表示这是一个原始字符串字面量。

解释：

R：表示原始字符串字面量的开始。
"(...)"：在这个括号内，你可以写任何字符，C++ 会原样保留字符串中的字符，而不需要转义。

原始字符串字面量的作用是让你在字符串中使用特殊字符（如反斜杠 \）而不需要对它们进行转义。例如，正则表达式中的反斜杠 \ 本来在普通字符串中需要写成 \\，但在原始字符串字面量中，反斜杠就能直接使用。

举个例子：
std::string str = "This is a string with a new line\nand a tab\t!";
在常规字符串字面量中，\n 和 \t 是转义字符。你需要特别处理这些字符。

如果你使用原始字符串字面量：
std::string str = R"(This is a string with a new line\nand a tab\t!)";
这里的 \n 和 \t 不再是转义字符，而是字面上的 \ 和 n、\ 和 t，即它们被当作普通字符处理。

在例子中：
regex loc_pattern(R"(\((\d+),(\d+)\))");
这里的 R"(\((\d+),(\d+)\))" 是原始字符串字面量，表示字符串 \((\d+),(\d+)\)，其中 \( 和 \) 会被当作普通字符处理，而不需要转义。