最新华为OD机试真题-多段线路径压缩(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 多段线路径压缩(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🎚 多段线路径压缩

题目描述

LYA 是一名出色的程序员,她正在开发一款图像处理软件。在处理图像时,需要存储图像中的多段线路径。为了节省存储空间,LYA 想要对路径进行压缩。

路径由若干个像素点组成,每个像素点用其行号和列号表示。为简化处理,多段线的走向只能是水平、竖直或 度斜向。例如,一条路径可以表示为:

但是,这种表示方法存在冗余。实际上,我们只需存储路径的关键点(起点、拐点和终点),就可以完整地表示整条路径。在上面的例子中,只需存储以下 个点即可:

现在,给定一条包含若干冗余点的路径,请你将其压缩为最简形式。

输入格式

输入一行,包含偶数个整数,表示原始路径。每两个整数表示一个像素点的行号和列号,整数之间用空格隔开。

输出格式

输出一行,包含偶数个整数,表示压缩后的路径。每两个整数表示一个像素点的行号和列号,整数之间用空格隔开。

样例输入

2 8 3 7 3 6 3 5 4 4 5 3 6 2 7 3 8 4 7 5

样例输出

2 8 3 7 3 5 6 2 8 4 7 5

数据范围

• 行号和列号的范围为 。
• 输入数据至少包含两个像素点。

题解

我们可以遍历原始路径中的所有像素点,依次判断每个点是否为关键点。判断方法如下:

1. 如果当前点是路径的起点,则它一定是关键点。
2. 如果当前点与前一个关键点在同一条直线上,则它不是关键点,否则它是关键点。

为了判断三个点是否在同一条直线上,我们可以分别计算前两个点的斜率和后两个点的斜率,如果两个斜率相等,则这三个点在同一条直线上。注意,由于坐标都是整数,为避免除法带来的精度问题,我们可以通过计算两个向量的叉积是否为零来判断斜率是否相等。

参考代码

• Python

def gcd(a, b):
    if a == 0 or b == 0:
        return 1
    while b:
        a, b = b, a % b
    return a

points = list(map(int, input().split()))
compressed = []

for i in range(0, len(points) - 2, 2):
    x1, y1 = points[i], points[i + 1] 
    x2, y2 = points[i + 2], points[i + 3]
    if not compressed:
        compressed.append(x1)
        compressed.append(y1)
    else:
        x0, y0 = compressed[-2], compressed[-1]
        dx1, dy1 = x1 - x0, y1 - y0
        dx2, dy2 = x2 - x1, y2 - y1
        g1, g2 = gcd(dx1, dy1), gcd(dx2, dy2)
        if dx1 // g1 != dx2 // g2 or dy1 // g1 != dy2 // g2:
            compressed.append(x1)
            compressed.append(y1)

compressed.extend(points[-2:])
print(*compressed)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        int n = input.length;
        int[] points = new int[n];
        for (int i = 0; i < n; i++) {
            points[i] = Integer.parseInt(input[i]);
        }
        
        List<Integer> compressed = new ArrayList<>();
        for (int i = 0; i < n - 2; i += 2) {
            int x1 = points[i], y1 = points[i + 1];
            int x2 = points[i + 2], y2 = points[i + 3];
            if (compressed.isEmpty()) {
                compressed.add(x1);
                compressed.add(y1);
            } else {
                int x0 = compressed.get(compressed.size() - 2);
                int y0 = compressed.get(compressed.size() - 1);
                int dx1 = x1 - x0, dy1 = y1 - y0;
                int dx2 = x2 - x1, dy2 = y2 - y1;
                int g1 = gcd(dx1, dy1), g2 = gcd(dx2, dy2);
                if (dx1 / g1 != dx2 / g2 || dy1 / g1 != dy2 / g2) {
                    compressed.add(x1);
                    compressed.add(y1);
                }
            }
        }
        
        compressed.add(points[n - 2]);
        compressed.add(points[n - 1]);
        for (int num : compressed) {
            System.out.print(num + " ");
        }
    }
    
    private static int gcd(int a, int b) {
        if (a == 0 || b == 0) {
            return 1;
        }
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;

int gcd(int a, int b) {
    if (a == 0 || b == 0) {
        return 1;
    }
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

int main() {
    vector<int> points;
    int num;
    while (cin >> num) {
        points.push_back(num);
    }
    
    vector<int> compressed;
    for (int i = 0; i < points.size() - 2; i += 2) {
        int x1 = points[i], y1 = points[i + 1];
        int x2 = points[i + 2], y2 = points[i + 3];
        if (compressed.empty()) {
            compressed.push_back(x1);
            compressed.push_back(y1);
        } else {
            int x0 = compressed[compressed.size() - 2];
            int y0 = compressed[compressed.size() - 1];
            int dx1 = x1 - x0, dy1 = y1 - y0;
            int dx2 = x2 - x1, dy2 = y2 - y1;
            int g1 = gcd(dx1, dy1), g2 = gcd(dx2, dy2);
            if (dx1 / g1 != dx2 / g2 || dy1 / g1 != dy2 / g2) {
                compressed.push_back(x1);
                compressed.push_back(y1);
            }
        }
    }
    
    compressed.push_back(points[points.size() - 2]);
    compressed.push_back(points[points.size() - 1]);
    for (int num : compressed) {
        cout << num << " ";
    }
    return 0;
}