切比雪夫距离 ( Chebyshev Distance )
发布时间
阅读量：
阅读量
切比雪夫距离Chebyshev Distance
- 前言
- 一、简介
- 二、自己的理解
- 总结
前言
如今想要进入互联网大厂工作，并非易事。虽然我的专业方向是Android图形开发，并非专注于互联网领域。但也始终怀有进入大厂工作的梦想，在力扣平台我也开始了自己的刷题之旅。最近解决的第1226号题目让我印象深刻——相较于其他看似简单的题目而言, 这道题确实耗费了不少时间。做完后沾沾自喜的时候才发现, 其实已经有前辈总结出了一个公式——切比雪夫距离 ( Chebyshev Distance )
一、简介
啥是切比雪夫距离 ( Chebyshev Distance )呢？具体描述如下：
国王能够移动到相邻的8个方格中的任意一个。那么如何计算国王从格子(x₁,y₁)到格子(x₂,y₂)所需的最小步数？通过计算可以发现,最少步数总是等于坐标差的最大值,即max(|x₂−x₁|,|y₂−y₁|) 步。这一计算方法被称为切比雪夫距离。二维平面两点a(x₁,y₁)与b(x₂,y₂)间的切比雪夫距离为D_{Chebyshev}(a,b)=\max(|x_2 - x_1|, |y_2 - y_1|)
二、自己的理解
个人认为仅凭上面的介绍难以弄清其推导过程。接着进行了大量搜索。浏览了许多博客后终于弄懂了。随后绘制了一幅图。一清了之。
所以力扣1226题从各种if…else直接改成了max( | x2-x1 | , | y2-y1 | ) ，一行代码直接搞定。
总结
虽然有一些无用的知识存在时有遗忘的情况，切比雪夫距离虽然曾经学过却遗忘了具体内容，在学习的时候也曾不屑一顾地认为其实没什么实用价值；然而等到真正需要用到它的时候才发现确实实用性不强真是"书到用时方恨少"啊！
全部评论 (0)
还没有任何评论哟~