Easy

题目描述

给定一个数组 points，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，如果这些点构成一个回旋镖则返回 true。

回旋镖定义为由三个点组成的集合，这三个点各不相同且不在一条直线上。

示例 1：

输入：points = [[1,1],[2,3],[3,2]]
输出：true

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：false

提示：

  • points.length == 3
  • points[i].length == 2
  • 0 <= xi, yi <= 100
  • 三个点构成回旋镖当且仅当由它们组成的三角形面积不为零

解题思路

要判断三个点是否构成回旋镖，本质上就是判断三个点是否在同一条直线上。如果三个点不共线，则构成回旋镖。

有三种常见的解法：

方法一：斜率比较法 计算前两个点连线的斜率和后两个点连线的斜率，如果斜率相等则三点共线。需要注意处理垂直线的情况（分母为0）。

方法二：向量叉积法（推荐） 利用向量叉积的几何意义：两个向量的叉积等于由它们构成的平行四边形的面积。如果三点共线，则向量叉积为0。设三个点为A、B、C，向量AB和AC的叉积为：(B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)。

方法三：三角形面积法 使用海伦公式或向量法计算三角形面积，面积为0则三点共线。

向量叉积法最简洁且不需要处理除法的特殊情况，因此推荐使用。

代码实现

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];
        
        // 使用向量叉积判断是否共线
        // 向量AB = (x2-x1, y2-y1), 向量AC = (x3-x1, y3-y1)
        // 叉积 = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)
        return (x2 - x1) * (y3 - y1) != (y2 - y1) * (x3 - x1);
    }
};

class Solution:
    def isBoomerang(self, points: List[List[int]]) -> bool:
        x1, y1 = points[0]
        x2, y2 = points[1]
        x3, y3 = points[2]
        
        # 使用向量叉积判断是否共线
        # 向量AB = (x2-x1, y2-y1), 向量AC = (x3-x1, y3-y1)
        # 叉积 = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)
        return (x2 - x1) * (y3 - y1) != (y2 - y1) * (x3 - x1)

public class Solution {
    public bool IsBoomerang(int[][] points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];
        
        // 使用向量叉积判断是否共线
        // 向量AB = (x2-x1, y2-y1), 向量AC = (x3-x1, y3-y1)
        // 叉积 = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)
        return (x2 - x1) * (y3 - y1) != (y2 - y1) * (x3 - x1);
    }
}

/**
 * @param {number[][]} points
 * @return {boolean}
 */
var isBoomerang = function(points) {
    const [x1, y1] = points[0];
    const [x2, y2] = points[1];
    const [x3, y3] = points[2];
    
    // 使用向量叉积判断是否共线
    // 向量AB = (x2-x1, y2-y1), 向量AC = (x3-x1, y3-y1)
    // 叉积 = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)
    return (x2 - x1) * (y3 - y1) !== (y2 - y1) * (x3 - x1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)只需要进行常数次数学运算
空间复杂度O(1)只使用常数个额外变量