求offer的菜鸡很害怕一个人 level
获赞
2
粉丝
1
关注
0
看过 TA
135
Northeastern University
2024
golang
IP属地:美国
暂未填写个人简介
私信
关注
0 点赞 评论 收藏
分享
go写的第二题思路是用一个map存出现过的整数数量,然后只要判断减去的两个数等于2*avg就可以,这个思路只过了36%第四题dp,有券的时候可以用或不用取最小,有效期每轮-1,代码如下:package mainimport ("fmt""strconv")func main() {T := 0fmt.Scan(&T)for t := 0; t n := 0fmt.Scan(&n)nums := make([]int, n)for j := 0; j fmt.Scan(&nums[j])}m := make(map[triple]int)var dfs func(int, int, string) intdfs = func(i, credit int, valid string) int {if i == n-1 {if valid != "" {return 0} else {return nums[i]}}if val, ok := m[triple{i, credit, valid}]; ok {return val}res := 0if valid == "" {credit += nums[i]if credit >= 100 {credit -= 100valid = "3"}res += dfs(i+1, credit, valid) + nums[i]} else if valid[0] == '1' {res += dfs(i+1, credit, minus1(valid[1:]))} else {if credit+nums[i] >= 100 {a := credit + nums[i] - 100res += min(dfs(i+1, credit, minus1(valid[1:])), nums[i]+dfs(i+1, a, minus1(valid)+"3"))} else {res += min(dfs(i+1, credit, minus1(valid[1:])), nums[i]+dfs(i+1, credit+nums[i], minus1(valid)))}}m[triple{i, credit, valid}] = resreturn res}fmt.Println(dfs(0, 0, ""))}fmt.Println(minus1("123"))}func minus1(s string) string {res := ""for _, v := range s {v1, _ := strconv.Atoi(string(v))v1--if v1 > 0 {res += strconv.Itoa(v1)}}return res}type triple struct {i      intcredit intvalid  string}func min(a, b int) int {if a return a}return b}
投递拼多多集团-PDD等公司10个岗位
0 点赞 评论 收藏
分享
关注他的用户也关注了:
牛客网
牛客企业服务