Contents

ARST打卡第166周[166/521]-长期上努力,并及时行乐

Algorithm

lc741_摘樱桃

思路: 每种情况都递归一下的两种情况,然后记录每条线吃到的果子数量,如果走不到最后,则去除这条路的果子数

特别处理一下起点和终点的果子数,起点终点的果子要去重一下返回的(起点为1 + 终点为1)*(结果数 - 1)

  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
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
package main

import (
	"fmt"
	"math"
)

/*
ans_v: 4
ans_v: 3
ans_v: 3
8

完了,路径上的去重没有去掉...
可以直接来一个路径集合,这样就可以去重了
map[i*nLen + j]bool, 需要深拷贝路径数组,好像有点丑...而且go中数组传递好像只有传指针,还要自己重新申请一下内存

是一种思路,但是感觉答案可能不一样,搞了一小时了,还是看答案吧...

答案用了巧妙的状态设计,让相同的格子直接是x1 = x2,从而简化了状态的存储

**而且只能从终点回起点一次,所以我上面的想法的答案是无限次,是不行的**

设两人的坐标为 (x_1,y_1)和 (x_2,y_2),则 x_1+y_1 = x_2+y_2 = k。那么当 x_1=x_2x时,必然有 y_1=y_2y,即两个人到达了同一个格子。
定义 f[k][x_1][x_2] 表示两个人(设为 A 和 B)分别从 (x_1,k-x_1))和(x_2,k−x_2) 同时出发,到达 (N-1,N-1)(N−1,N−1) 摘到的樱桃个数之和的最大值。
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/cherry-pickup/solution/zhai-ying-tao-by-leetcode-solution-1h3k/

其中比较难理解的东西: x1 := max(k-n+1, 0)
x1 + y1 = n
如果 x1 < k - (n - 1), 那么 x1 < (x1 + y1) - (n - 1), (n - 1) < y1, 所以 x1 不能 小于 k-n+1
*/
func cherryPickupMy(grid [][]int) int {
	nLen := len(grid)
	ans := make([]int, 0, 5)
	var dfs func(_grid [][]int, cnt, i, j int)
	dfs = func(_grid [][]int, cnt, i, j int) {
		// 非法终止条件
		// panic, index out of range
		// if -1 == _grid[i][j] {
		if nLen == i || nLen == j || -1 == _grid[i][j] {
			return
		}

		// 判断当前值
		cnt += _grid[i][j]

		// 答案终止条件
		if i == nLen-1 && j == nLen-1 {
			ans = append(ans, cnt)
			return
		}

		// dfs链路
		dfs(_grid, cnt, i+1, j)
		dfs(_grid, cnt, i, j+1)
	}

	// 运行计算
	dfs(grid, 0, 0, 0)

	ansLen := len(ans)
	if ansLen == 0 {
		return 0
	}
	ansInt := 0
	for _, v := range ans {
		fmt.Printf("ans_v: %d\n", v)
		ansInt += v
	}

	// 起始点不为-1,但要判断去重 `(起点为1 + 终点为1)*(结果数 - 1)`
	ansInt -= (grid[0][0] + grid[nLen-1][nLen-1]) * (nLen - 1)
	return ansInt
}

func cherryPickup(grid [][]int) int {
	n := len(grid)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = math.MinInt32
		}
	}
	f[0][0] = grid[0][0]
	// k = 1, 先更新 向下向右走了一步的情况
	for k := 1; k < n*2-1; k++ {
		/*
			其中比较难理解的东西: x1 := max(k-n+1, 0)
			x1 + y1 = n
			如果 x1 < k - (n - 1),
			那么 x1 < (x1 + y1) - (n - 1), (n - 1) < y1
			所以 x1 不能 小于 k-n+1
		*/
		for x1 := min(k, n-1); x1 >= max(k-n+1, 0); x1-- {
			for x2 := min(k, n-1); x2 >= x1; x2-- {
				y1, y2 := k-x1, k-x2
				if grid[x1][y1] == -1 || grid[x2][y2] == -1 {
					f[x1][x2] = math.MinInt32
					continue
				}
				res := f[x1][x2] // 都往右
				if x1 > 0 {
					res = max(res, f[x1-1][x2]) // 往下,往右
				}
				if x2 > 0 {
					res = max(res, f[x1][x2-1]) // 往右,往下
				}
				if x1 > 0 && x2 > 0 {
					res = max(res, f[x1-1][x2-1]) // 都往下
				}
				res += grid[x1][y1]
				if x2 != x1 { // 避免重复摘同一个樱桃
					res += grid[x2][y2]
				}
				f[x1][x2] = res
			}
		}
	}
	return max(f[n-1][n-1], 0)
}

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

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

func main() {
	grid := [][]int{{0, 1, -1},
		{1, 0, -1},
		{1, 1, 1}}
	fmt.Println(cherryPickup(grid))
}

Review

How hard should I push myself?

短期的压力可以让我们自己机能更加灵敏强大,但是长期压力会让我们自己的身心健康受到巨大的损害,比如长期心率高、泵血变快就会导致高血压。

所以我们要学会控制自己感受到的压力,然后及时释放压力。

工作和生活休息要结合起来,一张一弛,才能长久

所以在人生目标上保持长期主义,长期向一个目标去走,但每天不能把自己逼的太死,反而慢慢来,更加有效果

所以在大方向保持长期主义,然后短期来说要保持行动和放松的均衡,不要把自己憋坏了,导致身心出问题

人只能接受自己的能力极限,然后合理运用,打出自己人生能打出的最好最快乐的牌就行了,不用一定要比别人强

专注在大方向,持续积累,一定会在某些方面能创造比较多的价值,从而能获取一些资源来快乐的生活,此生足够了

更何况各种黑天鹅事件都无法预测,很可能让你以前所有的努力都前功尽弃,所以不要太努力伤了自己

不妨总体大方向,加及时行乐

Tips

git切换到某个tag

Share-对于go web中间件的个人理解

利用adapter函数的思想,以及接口实现后就是那种接口的思路结合在一起,就可以实现类似python装饰器一样的效果,然后就可以实现层层嵌套的中间件

这种简单的中间件不像装饰器

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func hello(wr http.ResponseWriter, r *http.Request) {
    wr.Write([]byte("hello"))
}

func timeMiddleware(next http.Handler) http.Handler {
    return http.HandlerFunc(func(wr http.ResponseWriter, r *http.Request) {
        timeStart := time.Now()

        // next handler
        next.ServeHTTP(wr, r)

        timeElapsed := time.Since(timeStart)
        logger.Println(timeElapsed)
    })
}

func main() {
    http.Handle("/", timeMiddleware(http.HandlerFunc(hello)))
    err := http.ListenAndServe(":8080", nil)
    ...
}

只有达到下面这一层的中间件才能长得像python装饰器

1
2
3
4
5
r = NewRouter()
r.Use(logger)
r.Use(timeout)
r.Use(ratelimit)
r.Add("/", helloHandler)

总得来说,还是python装饰器很舒服的语法糖