ARST打卡第159周[159/521]

Algorithm

lc464_我能赢吗

思路: 好像是一个除数奇偶和余数叠加在一起的判断

假设: 如果除法结果是偶数,那么先手必胜

因为先手可以先给出余数-1,然后就可以一直用这个策略,保持除法结果在偶数

规律没这么简单,暂时想了比较久没有找到,看答案吧

结果发现无法找规律(不该没有先看数据范围…),而是要 记忆化搜索 + 状态压缩

链接:https://leetcode.cn/problems/can-i-win/solution/wo-neng-ying-ma-by-leetcode-solution-ef5v/

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
func canIWin(maxChoosableInteger, desiredTotal int) bool {
if (1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal {
return false
}

dp := make([]int8, 1<<maxChoosableInteger)
for i := range dp {
dp[i] = -1
}
var dfs func(int, int) int8
dfs = func(usedNum, curTot int) (res int8) {
// 下面这个defer记忆搜索的操作很秀,学习之,C++需要自己每次在末尾赋值
dv := &dp[usedNum]
if *dv != -1 {
return *dv
}
defer func() { *dv = res }()
for i := 0; i < maxChoosableInteger; i++ {
if usedNum>>i&1 == 0 && (curTot+i+1 >= desiredTotal || dfs(usedNum|1<<i, curTot+i+1) == 0) {
return 1
}
}
return
}
return dfs(0, 0) == 1
}

Review

【TED演讲】美国被遗忘的工人阶级

马太效应一直在持续,贫穷的马太效应也一样如此,我们需要一个更好的解决方法,让父母减少给孩子的负面影响

并且还需要让人们知道不要受限于自己的处境,你能做你想做的一切,为而不争地去做

但是现实是没有更好的生活,大家连生育都不想进行,所以还是需要很多的思考和努力去解决这些问题

Tips

【Golang】怎样优雅的清空切片

Share

VScode ssh免密登录设置