Algorithm
lc1422_分割字符串的最大得分_前缀和或2次遍历
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
|
/*
maxScore 分割字符串,返回左边0,右边1的最大得分.
思路: 直接遍历,dp计算左边0的个数,然后第二次遍历,直接获取左边0,右边1的个数最大值
WA 1:
通过测试用例:
96 / 104
输入:
"00"
输出:
2
预期结果:
1
*/
func maxScore(s string) int {
sz := len(s)
zeroArr := make([]int, sz)
var ans int
for i, c := range s {
if c == '0' {
if i == 0 {
zeroArr[i]++
continue
}
zeroArr[i] = zeroArr[i-1] + 1
} else {
if i == 0 {
continue
}
zeroArr[i] = zeroArr[i-1]
}
}
// fmt.Printf("zeroArr: %v\n", zeroArr)
for i := range s {
// WA 1
if i == sz-1 {
break
}
// fmt.Printf("right: %v\n", (sz - (i + 1) - (zeroArr[sz-1] - zeroArr[i])))
tmpAns := zeroArr[i] + (sz - (i + 1) - (zeroArr[sz-1] - zeroArr[i]))
if tmpAns > ans {
ans = tmpAns
}
}
return ans
}
// 答案没用累计和,用的左右移动过程中,分数值变动的方式
func maxScoreAns(s string) int {
score := int('1'-s[0]) + strings.Count(s[1:], "1")
ans := score
for _, c := range s[1 : len(s)-1] {
if c == '0' {
score++
} else {
score--
}
ans = max(ans, score)
}
return ans
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
|
Review
API v3 of the yaml package for Go is available
yaml.v3 is really more stronger. It’s yaml.Node struct gives more feature.
Such as comment and supporting for anchors and aliases.
But something make us hard to turn to yaml.v3.
It’s MapSlice is gone. But our code have many MapSlice.
So, When I make a new project, I maybe use the yaml.v3.
Tips
map[interface{}]interface{} on a map[string]interface{}
对于yaml.v2默认为map[interface{}]interface{}
,然后项目中用了一些yaml.mapItem
和yaml.mapSlice
的话,那么可能升级yaml.v3可以帮你解决掉map[interface{}]interface{}
变成map[string]interface{}
的问题,但是却需要把前面两个数据结构转成较为复杂的yaml.Node
结构体,所以不想这样搞的可以直接用以上Tips中大佬们写的转化方法
Share
给不确定层数的嵌套map赋嵌套key-value值
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
|
package main
import "fmt"
func main() {
tmpConfVar := 1
dpMap := make(map[interface{}]interface{})
// dpMap["a"] = map[interface{}]interface{}{"DoingTaskMaxCnt": 3}
dpMap["a"] = map[interface{}]interface{}{"c": 3}
InserttmpMap := map[interface{}]interface{}{"k": 5}
dpMap["b"] = map[interface{}]interface{}{"j": InserttmpMap, "c": 3}
// confNewkeys := []string{"z", "k", "v", "b", "c"}
// confNewkeys := []string{"b", "j", "e"}
confNewkeys := []string{"b", "j", "k"}
joinMap := dpMap
for i := 0; i < len(confNewkeys); i++ {
key := confNewkeys[i]
val, ok := joinMap[key]
// 找到分叉口,构造配置项
if !ok {
tmpSupMap := make(map[interface{}]interface{})
tmpTmpMap := make(map[interface{}]interface{})
// 后面可以直接dfs递归回溯了
for j := len(confNewkeys) - 1; j > i; j-- {
if j == len(confNewkeys)-1 {
tmpTmpMap[confNewkeys[j]] = tmpConfVar
tmpSupMap[confNewkeys[j-1]] = tmpTmpMap
continue
}
// 每次都要新开一片内存来取tmpMap的值,而不是直接用tmpMap赋值,否则会内存错误
tmpTmpMap = make(map[interface{}]interface{})
tmpTmpMap[confNewkeys[j]] = tmpSupMap[confNewkeys[j]]
tmpSupMap[confNewkeys[j-1]] = tmpTmpMap
fmt.Printf("tmpSupMap 2: %v\n", tmpSupMap)
delete(tmpSupMap, confNewkeys[j])
fmt.Printf("tmpSupMap 3: %v\n", tmpSupMap)
}
// 同嵌套层级的命名修改,key就是新的命名
if len(confNewkeys)-1 == i {
tmpSupMap[key] = tmpConfVar
}
joinMap[key] = tmpSupMap[key]
break
}
if joinMap, ok = val.(map[interface{}]interface{}); !ok {
fmt.Printf("%v can't convert to map[interface{}]interface{}\n", val)
break
}
}
fmt.Println(dpMap)
}
|