ARST打卡第171周[171/521]

Algorithm

lc1422_分割字符串的最大得分_前缀和或2次遍历

/*
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值

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)
}