Contents

ARST打卡第158周[158/521]

Algorithm

lc812_最大三角形面积

感觉有点像找出最边缘的3个点,然后组成最大面积的计算,但我竟然有点不会直接计算这个三角形([[1,0],[0,1],[2,2]])面积,只会用切割法计算

不太记得了,看答案: https://leetcode.cn/problems/largest-triangle-area/solution/zui-da-san-jiao-xing-mian-ji-by-leetcode-yefh/

竟然不只是凸包,还能枚举,但是我是不知道怎么计算三角形面积了…

相量叉乘就好了

这题挺难的,并不是简单

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
func cross(p, q, r []int) int {
    // x1*y2 - y1*x2
    return (q[0]-p[0])*(r[1]-q[1]) - (q[1]-p[1])*(r[0]-q[0])
}

func getConvexHull(points [][]int) [][]int {
    n := len(points)
    if n < 4 {
        return points
    }

    // 按照 x 从小到大排序,如果 x 相同,则按照 y 从小到大排序
    sort.Slice(points, func(i, j int) bool { a, b := points[i], points[j]; return a[0] < b[0] || a[0] == b[0] && a[1] < b[1] })

    hull := [][]int{}
    // 求凸包的下半部分
    for _, p := range points {
        for len(hull) > 1 && cross(hull[len(hull)-2], hull[len(hull)-1], p) <= 0 {
            hull = hull[:len(hull)-1]
        }
        hull = append(hull, p)
    }
    // 求凸包的上半部分
    m := len(hull)
    for i := n - 1; i >= 0; i-- {
        for len(hull) > m && cross(hull[len(hull)-2], hull[len(hull)-1], points[i]) <= 0 {
            hull = hull[:len(hull)-1]
        }
        hull = append(hull, points[i])
    }
    // hull[0] 同时参与凸包的上半部分检测,因此需去掉重复的 hull[0]
    return hull[:len(hull)-1]
}

func triangleArea(x1, y1, x2, y2, x3, y3 int) float64 {
    return math.Abs(float64(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2)) / 2
}

func largestTriangleArea(points [][]int) (ans float64) {
    convexHull := getConvexHull(points)
    n := len(convexHull)
    for i, p := range convexHull {
        for j, k := i+1, i+2; j+1 < n; j++ {
            q := convexHull[j]
            for ; k+1 < n; k++ {
                curArea := triangleArea(p[0], p[1], q[0], q[1], convexHull[k][0], convexHull[k][1])
                nextArea := triangleArea(p[0], p[1], q[0], q[1], convexHull[k+1][0], convexHull[k+1][1])
                // 这里需要想象凸包里固定低,枚举高时,面积先变大后变小的情况
                if curArea >= nextArea {
                    break
                }
            }
            ans = math.Max(ans, triangleArea(p[0], p[1], q[0], q[1], convexHull[k][0], convexHull[k][1]))
        }
    }
    return
}

Reviews

gopkg.in/check.v1测试库

直接ctrl点击import里面的库就能跳转看到go的官方包说明,真的爽

研究gopkg.in/check.v1

因为 gopkg.in/check.v1 , 中的 setUpSuite函数,所以又看了一下 Package suite

这种点击就能直接看到官方文档说明的感觉很舒服,golang nice

Tips

解决go: go.mod file not found in current directory or any parent directory; see ‘go help modules‘

这个问题出现的概率挺大的,特别是需要在非go root路径下做小测试的时候

1
2
3
go env -w GO111MODULE=on
## xxx 是当前文件目录名
go mod init xxx

Share-wsl下创建windows目录下文件权限全是777的解决方案之一

在测试go写文件的时候,发现自己用remote-wsl…竟然在编辑windows共享目录的文件,仅仅只是用了wsl的go开发环境

然后导致go写出来的文件权限全是777,网上看了一下解决方案,有点麻烦,只写~/.vscode-server/server-env-setup这个文件,还不能成功,

所以决定还是用remote-wsl编辑wsl上的文件,把我学习的代码mv到wsl文件系统上面去,这里需要chmod 777 /root, 否则windows文件写不进去

并且还不能在软链接的目录下mv,否则还是写不进去,要在外面mv

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 ⚡ 05/11|18:07:23  /  chmod 777 /root 
 ⚡ 05/11|18:11:30  /  cd -           
~/code/go_learn
 ⚡ 05/11|18:11:34  go_learn  mv workWithGo ../code/
mv: cannot move 'workWithGo' to '../code/': Permission denied
 ✘ ⚡ 05/11|18:11:49  go_learn  pwd
/root/code/go_learn
 ⚡ 05/11|18:11:53  go_learn  ll
total 0
drwxrwxrwx 1 root root 4.0K May  7 18:17 gopl.io
drwxrwxrwx 1 root root 4.0K May 10 21:22 workWithGo
 ⚡ 05/11|18:12:05  go_learn  cd ..
 ⚡ 05/11|18:12:20  code  pwd
/root/code
 ⚡ 05/11|18:12:22  code  mv go_learn/workWithGo ./
mv: setting attribute 'system.wsl_case_sensitive' for 'system.wsl_case_sensitive': Invalid argument
mv: setting attribute 'system.wsl_case_sensitive' for 'system.wsl_case_sensitive': Invalid argument
 ⚡ 05/11|18:12:38  code  ll
total 0
drwxr-xr-x 1 root root 4.0K May 10 14:55 estor-server
drwxr-xr-x 1 root root 4.0K May 11 17:33 estorgosdk
lrwxrwxrwx 1 root root   42 May 10 20:57 go_learn -> /mnt/c/Users/shanl/Documents/Code/go_learn
drwxrwxrwx 1 root root 4.0K May 10 21:22 workWithGo
 ⚡ 05/11|18:13:50  code  

到外面就正常了

1
2
3
4
5
6
7
 ⚡ 05/11|18:15:53  workWithGo  umask
022
 ⚡ 05/11|18:15:56  workWithGo  touch test
 ⚡ 05/11|18:16:01  workWithGo  ll
total 0
drwxrwxrwx 1 root root 4.0K May 11 18:05 code
-rw-r--r-- 1 root root    0 May 11 18:16 tes