华为OD机考算法题：最远足迹

目录

题目部分

解读与分析

代码实现

---

题目部分

---

解读与分析

题目解读：

此题要求从输入字符串中过滤出所有合法的坐标，计算出最远坐标，并输出它。合法坐标的意思是：
1. 首字母是'('，尾字母是')'，中间是两个数字，用',' 隔开。
2. 两个数字的首位都不能为 0（数字不能等于0，而且大于0的数字不能有前导 0）。 
如果不存在合法坐标，则输出 (0,0)。

本题题干关于坐标合法，没有明确的说，只能通过题目的样例总结。
一个好的题目，应该使用概括的语言描述合法（或不合法）的情况，然后举例说明。否则，举例如果不能覆盖所有的场景，将会产生歧义。

分析与思路：

先设置两个变量：
1. maxPosition ，字符串类型，用以记录最远的坐标，初始值为 "(0,0)"。
2. maxDistance，整形数字，记录最远的距离，初始值为0。

遍历字符串，在遍历字符串的过程中，找到一个合法坐标后，计算其到总部的距离，设为 tmpDistance，如果 tmpDistance 大于 maxDistance，则把它赋值给 maxDistance，并把把它坐标赋值给 maxPosition。继续遍历字符串，寻找下一个合法坐标，循环判断到总部距离，直到字符串结束。

在计算到总部的距离时，假设坐标为 (x,y) ， 则距离为 sqrt( x * x + y * y )。由于此题只关心坐标的相对距离，不需要绝对值，所以可以使用 x * x + y * y 代替其平方根值进行比较，以减少计算量。

代表合法坐标的字符串，在去除首位的小括号后必须满足如下条件：
1. 中间某个位置（既不是首字母，也不是尾字母）包含字符','。
2. 通过分隔符 ',' 分开为 2 个字符串，这两个字符串首字母不为 0，且都能解析成正整数。

此算法只需要遍历一次字符串，时间复杂度为 O(n)，使用了 2 个额外的原始数据类型变量，空间复杂度为 O(1)。

---

代码实现

Java代码

import java.util.Scanner;
 
/**
 * 最远足迹
 * 
 * @since 2023.09.07
 * @version 0.1
 * @author Frank
 *
 */
public class MaxDistance {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String record = sc.nextLine();
 
		int i = 0;
		int maxDistance = 0;
		String maxPosition = "(0,0)";
		while (i < record.length()) {
			int leftPT = record.indexOf('(', i);
			int rightPT = record.indexOf(')', i);
 
			if (leftPT < 0) {
				break;
			}
 
			String position = record.substring(leftPT + 1, rightPT);
			int tmpDistance = getDistance(position);
			if (tmpDistance > maxDistance) {
				maxDistance = tmpDistance;
				maxPosition = "(" + position + ")";
			}
			i = rightPT + 1;
		}
		System.out.println(maxPosition);
	}
 
	private static int getDistance(String position) {
		int ret = 0;
		String[] posArr = position.split(",");
		if (posArr == null || posArr.length != 2) {
			return 0;
		}
		for (int i = 0; i < posArr.length; i++) {
			String strPos = posArr[i];
			if (strPos.length() == 0 || strPos.startsWith("0")) {
				return 0;
			}
			try {
				int intPos = Integer.parseInt(strPos);
				ret += (intPos * intPos);
			} catch (NumberFormatException e) {
				return 0;
			}
 
		}
 
		return ret;
	}
 
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
 
function getDistance( position ) {
    var ret = 0;
    var posArr = position.split(",");
    if (posArr == null || posArr.length != 2) {
        return 0;
    }
    for (var i = 0; i < posArr.length; i++) {
        var strPos = posArr[i];
        if (strPos.length == 0 || strPos.startsWith("0")) {
            return 0;
        }
        var intPos = Number(strPos);
        if( Number.isNaN( intPos) )
        {
            return 0;
        }
        ret += (intPos * intPos);
 
    }
 
    return ret;
}
 
function processInput( line )
{
    var record = line;
    var i = 0;
    var maxDistance = 0;
    var maxPosition = "(0,0)";
    if( !record )
    {
        console.log(maxPosition);
        return;
    }
    while (i < record.length) {
        var leftPT = record.indexOf('(', i);
        var rightPT = record.indexOf(')', i);
 
        if (leftPT < 0) {
            break;
        }
 
        var position = record.substring(leftPT + 1, rightPT);
        var tmpDistance = getDistance(position);
        if (tmpDistance > maxDistance) {
            maxDistance = tmpDistance;
            maxPosition = "(" + position + ")";
        }
        i = rightPT + 1;
    }
    console.log(maxPosition);
}
 
void async function() {
    let input = [];
    while (line = await readline()) {
        processInput( line );
    }
 
}();

(完)