Leetcode 447 Number of Boomerangs

twisted-fate 的个人博客 / 0 / 0 / 创建于 5年前 / 更新于 5年前

复盘#

1. 注意计算距离可能的 int 越界问题 (int 32 位，范围: -2^31——2^31-1，即 - 2147483648——2147483647 , 大约 20 亿，10 位数 long long 64 位，范围: -9223372036854775808～9223372036854775807 (19 位数， 9e18) 2^63 - 1)

2. 查找表，灵活选择键值，明确想查找什么数据，这里查找的是其他点到该点 "距离相同" 的 "个数" , 确定一个枢纽，围绕着它查找 , 比如另一题，给你4 个点判断,判断是否为矩形 , 计算出 4 个点的中点，再计算出 4 个点到中点的距离，存入 map , 遍历 map , 如果有到中点距离个数为 4 的键值对，则可以确认是矩形

3. 三元组，排列问题，这里先锚定一个，再从该距离的个数里取一个 * (个数 - 1 里再取一个) 种排列

4. 没画图和写定义............ 之后补上

pesudo code :

res=0

foreach all point
    generate curr point dis map

    foreach dismap as disCount
        res=res+ disCount * disCount-1

return res

func main() {
    s:=[][]int{{0,0} ,{1,0},{2,0}}
    fmt.Println(numberOfBoomerangs(s))

}

func numberOfBoomerangs(points [][]int) int {
    res := 0
    for i, v1 := range points {
        map1:=make(map[int]int)
        for j, v2 := range points {
            if i == j {
                continue
            }
            map1[dis(v1,v2)]++
            fmt.Println(map1)
        }

        for _,v:=range map1 {
            res=res+ v*(v-1)
        }
    }

    return res
}

func dis(point1 []int, point2 []int) int {
    return (point2[0]-point1[0])*(point2[0]-point1[0])+ (point2[1]-point1[1])*(point2[1]-point1[1])
}