前言
四题A两题。。。。菜。。
第一题
2243.计算字符串的数字和
2243.计算字符串的数字和
题解
对着题目模拟即可，简单题，练习如何写的更加优雅
代码
func digitSum(s string, k int) string { if len(s) <= k { return s } str := "" for i := 0; i < len(s); i += k { cur := 0 for j := i; j < i+k && j < len(s); j++ { cur += int(s[j] - '0') } str += strconv.Itoa(cur) } fmt.Println(str) return digitSum(str, k) }
第二题
2244.完成所有任务需要的最少轮数
2244.完成所有任务需要的最少轮数
题解
题目：每一轮只能完成相同等级的任务，并且只能完成2个或者3个，求完成所有任务要多少轮
思路：统计同等级的任务有多少个，贪心，优先每一轮完成3个，3个不行则2个，发现规律，设任务为v，则需要(v + 2) / 3轮
任务数量: 1 2 3 4 5 6 7 8 9 10 11 12 13 完成轮数:-1 1 1 2 2 2 3 3 3 4 4 4 4
代码
func minimumRounds(tasks []int) int { mp := make(map[int]int) for _, v := range tasks { mp[v]++ } ans := 0 for _, v := range mp { if v == 1 { return -1 } else { ans += (v + 2) / 3 } } return ans }
第三题
2245.转角路径的乘积中最多能有几个尾随零
2245.转角路径的乘积中最多能有几个尾随零
题解
题目：只能转一次，求路径中每个元素相乘的结果有几个零
思路：
- 正数的乘积结果中尾 0 的个数由乘数中 因子 2，5 的个数中较小的决定,即 尾随零=min(num2,num5)
- 路径要么是横，竖，要么是UL，UR，DL，DR
- 用前缀和维护每一行和每一列因子 22 与因子 55 的数量
- 枚举拐点（i,j）计算答案
代码
func maxTrailingZeros(grid [][]int) int { //初始化 n := len(grid) m := len(grid[0]) factor := make([][]pair, n+1) //2和5的数量 x := make([][]pair, n+1) //列 x y := make([][]pair, n+1) //行 y for i := 0; i <= len(grid); i++ { factor[i] = make([]pair, m+1) x[i] = make([]pair, m+1) y[i] = make([]pair, m+1) } //计算前缀和 for i := 1; i <= n; i++ { for j := 1; j <= m; j++ { factor[i][j] = getRes(grid[i-1][j-1]) x[i][j].two = x[i-1][j].two + factor[i][j].two x[i][j].five = x[i-1][j].five + factor[i][j].five y[i][j].two = y[i][j-1].two + factor[i][j].two y[i][j].five = y[i][j-1].five + factor[i][j].five } } //计算答案 ans := 0 for i := 1; i <= n; i++ { for j := 1; j <= m; j++ { upAndLeft := min(x[i][j].two+y[i][j].two-factor[i][j].two, x[i][j].five+y[i][j].five-factor[i][j].five) upAndRight := min(x[i][j].two+y[i][m].two-y[i][j].two, x[i][j].five+y[i][m].five-y[i][j].five) downAndLeft := min(x[n][j].two+y[i][j].two-x[i][j].two, x[n][j].five+y[i][j].five-x[i][j].five) downAndRight := min(x[n][j].two+y[i][m].two-x[i-1][j].two-y[i][j].two, x[n][j].five+y[i][m].five-x[i-1][j].five-y[i][j].five) ans = max(ans, upAndLeft) ans = max(ans, upAndRight) ans = max(ans, downAndLeft) ans = max(ans, downAndRight) } } return ans } func getRes(val int) pair { two, five := 0, 0 a, b := val, val for a%2 == 0 && a != 0 { a /= 2 two++ } for b%5 == 0 && b != 0 { b /= 5 five++ } return pair{two: two, five: five} } func min(i, j int) int { if i > j { return j } return i } func max(i, j int) int { if i > j { return i } return j }
第四题
2246.相邻字符不同的最长路径
2246.相邻字符不同的最长路径
题解
题目：给一棵树的每个节点赋一个字符，求一个最长路径，相邻节点的字符不能一样
思路：
- 路径为 t1 <- target -> t2
- t1和t2可以为零
- 枚举target
- 用dfs枚举所有情况
代码
func longestPath(parent []int, s string) (ans int) { n := len(parent) //key 父节点 val 子节点，存图 g := make(map[int][]int) for i := 1; i < n; i++ { fa := parent[i] g[fa] = append(g[fa], i) } var dfs func(x int) (tLen int) dfs = func(x int) (maxLen int) { //最长，次长 fstLong, scdLong := 0, 0 //遍历所有子节点 for _, y := range g[x] { subLong := dfs(y) //相邻节点字符不相等 if s[x] != s[y] { if subLong > fstLong { scdLong = fstLong fstLong = subLong } else if subLong > scdLong { scdLong = subLong } } } //更新答案，路径长=最长+次长+本节点1 ans = max(ans, fstLong+scdLong+1) //返回当前节点下的最长路径+本身这个节点1 return fstLong + 1 } dfs(0) return ans } func max(a, b int) int { if b > a { return b } return a }
