Contents

ARST打卡第176周[176/521]

Algorithm

lc827_最大人工岛

 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
58
59
60
61
/*
largestIsland 找到一个0填1之后的最大岛。
暴力是n^4, 但是n最大有500,所以可能最大是n^3,1.25e7。

所以预处理原来的每个分开的地方的岛屿值,然后再遍历加上也就是O(2*n^2).
然后看了题解,发现差不多.没有自己写了.
*/
func largestIsland(grid [][]int) (ans int) {
	dir4 := []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
	n, t := len(grid), 0
	tag := make([][]int, n)
	for i := range tag {
		tag[i] = make([]int, n)
	}
	area := map[int]int{}
	var dfs func(int, int)
	dfs = func(i, j int) {
		tag[i][j] = t
		area[t]++
		for _, d := range dir4 {
			x, y := i+d.x, j+d.y
			if 0 <= x && x < n && 0 <= y && y < n && grid[x][y] > 0 && tag[x][y] == 0 {
				dfs(x, y)
			}
		}
	}
	for i, row := range grid {
		for j, x := range row {
			if x > 0 && tag[i][j] == 0 { // 枚举没有访问过的陆地
				t = i*n + j + 1
				dfs(i, j)
				ans = max(ans, area[t])
			}
		}
	}

	for i, row := range grid {
		for j, x := range row {
			if x == 0 { // 枚举可以添加陆地的位置
				newArea := 1
				conn := map[int]bool{0: true}
				for _, d := range dir4 {
					x, y := i+d.x, j+d.y
					if 0 <= x && x < n && 0 <= y && y < n && !conn[tag[x][y]] {
						newArea += area[tag[x][y]]
						conn[tag[x][y]] = true
					}
				}
				ans = max(ans, newArea)
			}
		}
	}
	return
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

Review

【TED演讲】我们需要黑客

实话实说,没有太get到他表达的核心含义,好像是希望政府多放权,去支持一些新的加密技术(tor,bitcoin)的开放共享,以保证让大家更安全

感觉像宣传新技术的…

Tips

gRPC-go-Hello-World

Share-新版本的protoc使用grpc容易遇到的两个坑,gen gRPC,mustEmbedUnimplementedHelloServer

–go_out: protoc-gen-go: plugins are not supported; use ‘protoc –go-grpc_out=…’ to generate gRPC

这是因为你安装的是更新版本的protoc-gen-go,但是你却用了旧版本的生成命令。

但是这两种方法都是可以完成目标的,只不过api不太一样。推荐基于Google版本的protoc-gen-go进行示范。

1
protoc -I . --go_out=. --go-grpc_out=. ./hello.proto

至于其他更详细的资料,你可以在这里看到:https://github.com/protocolbuffers/protobuf-go/releases/tag/v1.20.0#v1.20-generated-code

mustEmbedUnimplementedHelloServer编译报错

1
2
3
4
 ⚡ 09/15|12:00:08  server  go build
## test/grpc/hello/server
./main.go:39:28: cannot use HelloService (variable of type helloService) as type hello.HelloServer in argument to pb.RegisterHelloServer:
        helloService does not implement hello.HelloServer (missing mustEmbedUnimplementedHelloServer method)

查询结果: https://github.com/grpc/grpc-go/issues/3794

解决方案一,结构实现多加一个必须加的结构体

1
2
3
4
// 定义helloService并实现约定的接口
type helloService struct {
	pb.UnimplementedHelloServer // 必须加的结构体
}

解决方案二,生成就去掉掉helloService

1
protoc --go-grpc_out=require_unimplemented_servers=false[,other options...]:. can solve this problem.