本次刷题日记的第 58 篇,力扣题为:1037. 有效的回旋镖,简单
一、题目描述:
回旋镖,看上去好像又是一个数学题,尝试一下看看咋解
二、这道题考察了什么思想?你的思路是什么?
这题是一个简单题,乍一看好像很简单,来看看题目说了啥:
- 题目介绍什么是回旋镖,回旋镖有 3 个点,这 3 个点不能在同一条直线上,那么才能构成一个回旋镖
- 题目会给出一组数据,里面有 3 个点的坐标,我们通过程序的方式来确认,这 3 个点是否可以组成一个回旋镖
分析
就这么简单看来好像很简单,给出的 3 个点的数据,不能在同一条直线上,那么我们第一时间是否会想到,只要 3 个点的 横坐标和纵坐标不完全相等,那么是不是就可以了
于是会写出下面这个水货代码
稍微一跑就发现,这玩意行不通,思考的还是太少了,比如下面这中情况就没有考虑到
这种情况的话,实际上是某个点到中心原点 (0,0) 的斜率是相等的,因此也是在一条线上
那么,考虑这个问题我们就不能简单的通过每个坐标的横纵坐标来思考了,应该要往数学的角度去思考了
思考片刻
两个点能够确定一条直线, 3 个点能够确定一个面,那么 3 个点,实际上其两两分别组成的直线,加起来也是 3 条,例如这样
那么我们就可以很明确的看出来,要组成这么一个面,这 3 个点,组成的线,一定是要相交的,谈到相交,我们以前是不是学过,两条向量如果是相交,那么他俩相乘,一定不等于 0 向量
因此,看到这里,我们就知道,这个哪里是啥编程题,实际上就是一个妥妥的数学题,好像还算是初中的数学题吧
三、编码
根据上述逻辑和分析,我们就可以翻译成如下代码
对于向量的知识就不过多赘述了,咱们就用在学校学过的数学方法来计算两条向量相乘是否为 0 即可
编码如下:
func isBoomerang(points [][]int) bool { // 任意一条向量 1 v1 := [2]int{points[1][0] - points[0][0], points[1][1] - points[0][1]} // 任意一条向量 2 v2 := [2]int{points[2][0] - points[0][0], points[2][1] - points[0][1]} return v1[0]*v2[1]-v1[1]*v2[0] != 0 }
四、总结:
就这个题而言,有时候可能我们会想不到用数学的方式,其实学好数学才能理解很多现象和原理
不多说,本题解法的时间复杂度为 O(1) ,空间复杂度也是 O(1)
原题地址:1037. 有效的回旋镖
今天就到这里,学习所得,若有偏差,还请斧正
欢迎点赞,关注,收藏
朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力
好了,本次就到这里
技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。
我是阿兵云原生,欢迎点赞关注收藏,下次见~