前言
C++算法与数据结构
打开打包代码的方法兼述单元测试
数论:质数、最大公约数、菲蜀定理
组合数学汇总
计算几何
博弈论
曼哈顿距离与切比雪夫距离
红线是哈曼顿距离,绿线是切比雪夫距离。
二维曼哈顿距离转切比雪夫距离
曼哈顿距离:|x1-x2|+|y1-y2|。典型应用:某个棋子只能向4联通移动(上下左右),哈曼顿距离就是就是两点间的移动次数。
切比雪夫距离:max(|x1-x2|,|y1-y2|)。典型应用:某个棋子只能向8联通移动(上下左右及四角),切比雪夫距离就是就是两点间的移动次数。
利用f(x,y)=(x+y,x-y)将点1(x1,y1)点2(x2,y2)转成点3(x3,y3)和点4(x4,y4)后,点1到点2的哈曼顿距离等于点3到点4的切比雪夫距离。下面来证明:
哈曼顿距离:max(x1-x2,x2-x1)+max(y1-y2,y2-y1) = max(x1-x2+y1-y2,x1-x2+y2-y1,x2-x1+y1-y2,x2-x1+y2-y1)
= max(x3-x4,y3-y4,y4-y3,x4-x3)
= max(|x3-x4|,|y3-y4|)即点3到点4的切比雪夫距离。
切比雪夫距离转哈曼顿距离:解2元一次方程组。
多维哈顿曼距离转切比雪夫距离
n维哈曼顿距离可以转化成2n-1维哈曼顿距离:
三维:(x,y,z)
→
\rightarrow
→ (x+y+z,-x+y+z,x-y+z,x+y-z)。
思维及以上是我的估计,不一定正确:
a+b+c+d,a+b+c-d,a+b-c+d,a+b-c-d,a-b+c+d,a-b+c-d,a-b-c+d,a-b-c-d。
即:a只取正号,其它(n-1)维,全部取正负,共2n-1种可能。
题解2024年11月9
曼哈顿距离
难度分 | |
---|---|
【C++ 曼哈顿距离 数学】1131. 绝对值表达式的最大值 | 2059 |
【C++数学 曼哈顿距离】3102. 最小化曼哈顿距离 | 2215 |
【键值皆有序map 线段树 数学 】3102. 最小化曼哈顿距离 | 2215 |
博弈论
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。