【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【模拟/数学】2023C-多段线数据压缩【欧弟算法】全网注释最详细分类最全的华为OD真题题解

���LeetCode算法/华为OD考试扣扣交流群可加 948025485

可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题

绿色聊天软件戳 od1336了解算法冲刺训练

文章目录

• 题目描述与示例
• • 题目描述
  • 输入描述
  • 输出描述
  • 补充说明
  • 示例
  • • 输入
    • 输出
    • 说明
    • 解题思路
    • 代码
    • • Python
      • Java
      • C++
      • 时空复杂度
      • 华为OD算法/大厂面试高频题算法练习冲刺训练

        题目描述与示例

        题目描述

        下图中，每个方块代表一个像素，每个像素用其行号和列号表示。

        为简化处理，多段线的走向只能是水平、竖直、斜向45度。

        上图中的多段线可以用下面的坐标串表示:(2,8),(3,7),(3,6),(3,5),(4,4),(5,3),(6,2),(7,3),(8,4),(7,5)。

        但可以发现，这种表示不是最简的，其实只需要存储6个蓝色的关键点即可，它们是线段的起点、拐点、终点，而剩下4个点是冗余的。

        现在，请根据输入的包含有几余数据的多段线坐标列表，输出其最化的结果。

        输入描述

        形如2 8 3 7 3 6 3 5 4 4 5 3 6 2 7 3 8 4 7 5

        1、所有数字以空格分隔，每两个数字一组，第一个数字是行号，第二个数字是列号;

        2、行号和列号范围为[0,64)，用例输入保证不会越界，考生不必检查;

        3、输入数据至少包含两个坐标点。

        输出描述

        形如2 8 3 7 3 5 6 2 8 4 7 5

        压缩后的最简化坐标列表，和输入数据的格式相同。

        补充说明

        输出的坐标相对顺序不能变化。

        示例

        输入

        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

        说明

        如上图所示，6个蓝色像素的坐标依次是(2,8)、(3,7)、(3,5)、(6,2)、(8,4)、(7,5)。

        将他们按顺序出即可。

        解题思路

        本题的核心在于如何判定三点共线。

        已知三个点A、B、C坐标分别为(x1, y1)、(x2, y2)、(x3, y3)，那么向量AB和AC分别可以用(x2-x1, y2-y1)以及(x3-x1, y3-y1)来表示。

        三点共线等价于这两个向量平行，即等价于(x2-x1)*(y3-y1) == (x3-x1)*(y2-y1)成立。

        因此我们可以固定一个起始端点start_point来表示某一段线段的起始端点。start_point初始化为所有点中的第一个坐标。起始端点需要加入到答案列表ans中。

        然后遍历所有点points，考虑临近的两个点points[i]和poins[i-1]。若start_point、points[i]和poins[i-1]

        • 位于同一条直线上，那么说明中间的点poins[i-1]是可以忽略的。即如下图所示的情况
          • 不位于同一条直线上，那么说明中间的点poins[i-1]是不可以忽略的，是一个拐点，需要加入到答案列表ans中。同时将start_point修改为poins[i-1]，表示下一个线段的起始端点为poins[i-1]。

            注意遍历结束后，最后一个点（终点）还需要加入到答案列表ans中。总体的核心代码如下

            start_point = points[0]ans = [start_point]for i in range(1, n):    if check_same_line(start_point, points[i-1], points[i]):        continue    else:        ans.append(points[i-1])        start_point = points[i-1]ans.append(points[-1])print(" ".join(f"{p[0]} {p[1]}" for p in ans))

            代码

            Python

            # 题目：【模拟】2023C-多段线数据压缩# 分值：100# 作者：许老师-闭着眼睛学数理化# 算法：模拟# 代码看不懂的地方，请直接在群上提问# 检查是否三点共线的函数# p1, p2, p3分别为二元组，表示一个点def check_same_line(p1, p2, p3):    x1, y1 = p1    x2, y2 = p2    x3, y3 = p3    return (x2-x1)*(y3-y1) == (x3-x1)*(y2-y1)# 输入一行数据，包含2*n个坐标lst = list(map(int, input().split()))# 将lst转化为n个点，储存在二维列表points中points = [[lst[i], lst[i+1]] for i in range(0, len(lst), 2)]# 获得点的个数nn = len(points)# 初始化起始端点start_point = points[0]# 初始化答案列表，包含起始端点ans = [start_point]for i in range(1, n):    # 检查start_point、points[i-1]和points[i]是否三点共线    # 若是，说明points[i-1]被忽略，则可以直接跳过    if check_same_line(start_point, points[i-1], points[i]):        continue    # 否则，说明points[i-1]是一个拐点，加入ans中    # 同时需要修改points[i-1]为新的起始端点start_point    else:        ans.append(points[i-1])        start_point = points[i-1]# 加入最后一个点的坐标，为终止点ans.append(points[-1])# 将ans中的所有二元组输出为1行print(" ".join(f"{p[0]} {p[1]}" for p in ans))

            Java

            import java.util.*;public class Main {    // 检查是否三点共线的函数    public static boolean checkSameLine(int[] p1, int[] p2, int[] p3) {        int x1 = p1[0], y1 = p1[1];        int x2 = p2[0], y2 = p2[1];        int x3 = p3[0], y3 = p3[1];        return (x2 - x1) * (y3 - y1) == (x3 - x1) * (y2 - y1);    }    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        String[] input = scanner.nextLine().split(" ");        int n = input.length / 2; // 获取点的个数n        int[][] points = new int[n][2]; // 初始化存储点的二维数组        // 将输入转化为二维数组        for (int i = 0; i  
            C++
             
            #include #include using namespace std;// 检查是否三点共线的函数bool checkSameLine(const vector& p1, const vector& p2, const vector& p3) {    int x1 = p1[0], y1 = p1[1];    int x2 = p2[0], y2 = p2[1];    int x3 = p3[0], y3 = p3[1];    return (x2 - x1) * (y3 - y1) == (x3 - x1) * (y2 - y1);}int main() {    // 输入一行数据，包含2*n个坐标    vector points;    int num;    while (cin >> num) {        points.push_back(num);    }    int n = points.size() / 2; // 获取点的个数n    vector ans; // 初始化存储点的二维数组    ans.push_back({points[0], points[1]}); // 将起始端点加入结果中    // 从第二个点开始遍历    for (int i = 1; i