早起刷题（Day 16）
洪笳淏 Lv4
 2022-04-18 06:00:00      

本文是对 2022.04.17 周赛的回顾

LeetCode6070. 计算字符串的数字和

#字符串 #模拟

题目描述

给你一个由若干数字（0 - 9）组成的字符串 s ，和一个整数。
如果 s 的长度大于 k ，则可以执行一轮操作。在一轮操作中，需要完成以下工作：
将 s 拆分 成长度为 k 的若干 连续数字组 ，使得前 k 个字符都分在第一组，接下来的 k 个字符都分在第二组，依此类推。注意，最后一个数字组的长度可以小于 k 。
用表示每个数字组中所有数字之和的字符串来 替换 对应的数字组。例如，”346” 会替换为 “13” ，因为 3 + 4 + 6 = 13 。
合并 所有组以形成一个新字符串。如果新字符串的长度大于 k 则重复第一步。
返回在完成所有轮操作后的 s 。

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
示例 1：
输入：s = "11111222223", k = 3
输出："135"
解释：
- 第一轮，将 s 分成："111"、"112"、"222" 和 "23" 。
  接着，计算每一组的数字和：1 + 1 + 1 = 3、1 + 1 + 2 = 4、2 + 2 + 2 = 6 和 2 + 3 = 5 。 
  这样，s 在第一轮之后变成 "3" + "4" + "6" + "5" = "3465" 。
- 第二轮，将 s 分成："346" 和 "5" 。
  接着，计算每一组的数字和：3 + 4 + 6 = 13 、5 = 5 。
  这样，s 在第二轮之后变成 "13" + "5" = "135" 。 
现在，s.length <= k ，所以返回 "135" 作为答案。

示例 2：
输入：s = "00000000", k = 3
输出："000"
解释：
将 "000", "000", and "00".
接着，计算每一组的数字和：0 + 0 + 0 = 0 、0 + 0 + 0 = 0 和 0 + 0 = 0 。 
s 变为 "0" + "0" + "0" = "000" ，其长度等于 k ，所以返回 "000" 。
 

提示：
1 <= s.length <= 100
2 <= k <= 100
s 仅由数字（0 - 9）组成。

解题思路

(1). 总体思路就是反复合并的过程，直到字符串长度小于等于 k；
(2). 需要注意的就是怎样寻找每个长度为 k（最后一个小于等于 k）的子串的起始索引。

解题代码

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
func digitSum(s string, k int) string {

	if len(s) <= k {
		return s
	}

	for len(s) > k {

		t := ""
		for i:=0; i<=(len(s)/k)*k; i=i+k {
			x := ""
			if i == (len(s)/k)*k {
				x = s[i:]
			} else {
				x = s[i:i+k]
			}

			if x == "" {
				break
			}

			var n int
			for j:=0; j<len(x); j++ {
				n += int(x[j])-'0'
			}

			t += strconv.Itoa(n)
		}
		s = t
	}

	return s
}

LeetCode6071. 完成所有任务需要的最少轮数

#动态规划 #枚举

题目描述

给你一个下标从 0 开始的整数数组 tasks ，其中 tasks[i] 表示任务的难度级别。在每一轮中，你可以完成 2 个或者 3 个 相同难度级别 的任务。
返回完成所有任务需要的 最少 轮数，如果无法完成所有任务，返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
示例 1：
输入：tasks = [2,2,3,3,2,4,4,4,4,4]
输出：4
解释：要想完成所有任务，一个可能的计划是：
- 第一轮，完成难度级别为 2 的 3 个任务。 
- 第二轮，完成难度级别为 3 的 2 个任务。 
- 第三轮，完成难度级别为 4 的 3 个任务。 
- 第四轮，完成难度级别为 4 的 2 个任务。 
可以证明，无法在少于 4 轮的情况下完成所有任务，所以答案为 4 。


示例 2：
输入：tasks = [2,3,3]
输出：-1
解释：难度级别为 2 的任务只有 1 个，但每一轮执行中，只能选择完成 2 个或者 3 个相同难度级别的任务。因此，无法完成所有任务，答案为 -1 。
 

提示：
1 <= tasks.length <= 10^5
1 <= tasks[i] <= 10^9

解题思路

(1). 本题中并不关心具体的任务难度的差别，任务难度的级别仅仅是作为对任务的区分，相当于任务的编号；
(2). 首先要计算每种任务各有多少个，并且记录下最多的某类任务个数；
(3). 然后就可以使用动态规划，创建数组，数组的长度是最多的任务个数+1；
(4). 然后就转变为类似跳台阶的问题；
(5). 之后枚举所有任务，根据动态规划数组计算总轮数。

解题代码

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
func minimumRounds(tasks []int) int {

	m := make(map[int]int)
	maxNum := 0

	for i:=0; i<len(tasks); i++ {
		m[tasks[i]]++
		maxNum = max(maxNum, m[tasks[i]])
	}

	if maxNum < 2 {
		return -1
	}

	dp := make([]int, maxNum+1)
	dp[0], dp[1], dp[2] = 0, 0, 1

	for i:=3; i<=maxNum; i++ {
		if i == 3 {
			dp[i] = 1
			continue
		}

		if dp[i-2] == 0 && dp[i-3] == 0 {
			dp[i] = 0
		} else if dp[i-2] == 0 {
			dp[i] = dp[i-3]+1
		} else if dp[i-3] == 0 {
			dp[i] = dp[i-2]+1
		} else {
			dp[i] = min(dp[i-2], dp[i-3])+1
		}
	}
	
	ret := 0
	for _,v := range m {
		if dp[v] == 0 {
			return -1
		}
		ret += dp[v]
	}

	return ret
}

  

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

  

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}

LeetCode6072. 转角路径的乘积中最多能有几个尾随零

#前缀和 #枚举

题目描述

给你一个二维整数数组 grid ，大小为 m x n，其中每个单元格都含一个正整数。
转角路径 定义为：包含至多一个弯的一组相邻单元。具体而言，路径应该完全 向水平方向 或者 向竖直方向 移动过弯（如果存在弯），而不能访问之前访问过的单元格。在过弯之后，路径应当完全朝 另一个 方向行进：如果之前是向水平方向，那么就应该变为向竖直方向；反之亦然。当然，同样不能访问之前已经访问过的单元格。
一条路径的 乘积 定义为：路径上所有值的乘积。
请你从 grid 中找出一条乘积中尾随零数目最多的转角路径，并返回该路径中尾随零的数目。

注意：

  • 水平 移动是指向左或右移动。
  • 竖直 移动是指向上或下移动。
1
示例 1:

avatar

1
2
3
4
5
6
7
8
9
输入：grid = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]]
输出：3
解释：左侧的图展示了一条有效的转角路径。
其乘积为 15 * 20 * 6 * 1 * 10 = 18000 ，共计 3 个尾随零。
可以证明在这条转角路径的乘积中尾随零数目最多。
中间的图不是一条有效的转角路径，因为它有不止一个弯。
右侧的图也不是一条有效的转角路径，因为它需要重复访问已经访问过的单元格。

示例 2：

avatar

1
2
3
4
5
6
7
8
9
10
11
12
输入：grid = [[4,3,2],[7,6,1],[8,8,8]]
输出：0
解释：网格如上图所示。
不存在乘积含尾随零的转角路径。
 

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 10^5
1 <= m * n <= 10^5
1 <= grid[i][j] <= 1000

解题思路

(1). 尾零的个数就是路径上的数的因子 2 的个数和，与因子 5 的个数之和的较小值；
(2). 那么数越多越好，路径的起点和终点都应该在边界上。预处理因子的前缀和，然后枚举所有的路径：

  • 从上往下走，枚举左拐/右拐；
  • 从下往上走，枚举左拐/右拐；
    (3). 所有路径上的 $min(s_2,s_5)$ 的最大值即为答案，这里 $s_2$ 为路径上的因子 2 的个数之和，$s_5$ 为路径上的因子 5 的个数之和。

解题代码

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
var c25 [1001][2]int

func init() {
	// 预处理：递推算出每个数的因子 2 的个数和因子 5 的个数
	for i := 2; i <= 1000; i++ {
		if i%2 == 0 { c25[i][0] = c25[i/2][0] + 1 }
		if i%5 == 0 { c25[i][1] = c25[i/5][1] + 1 }
	}
}

func maxTrailingZeros(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	s := make([][][2]int, m)
	for i, row := range grid {
		s[i] = make([][2]int, n+1)
		for j, v := range row {
			s[i][j+1][0] = s[i][j][0] + c25[v][0] // 每行的因子 2 的前缀和
			s[i][j+1][1] = s[i][j][1] + c25[v][1] // 每行的因子 5 的前缀和
		}
	}

	for j := 0; j < n; j++ {
		s2, s5 := 0, 0
		for i, row := range grid { // 从上往下，枚举左拐还是右拐
			s2 += c25[row[j]][0]
			s5 += c25[row[j]][1]
			ans = max(ans, max(min(s2+s[i][j][0], s5+s[i][j][1]), min(s2+s[i][n][0]-s[i][j+1][0], s5+s[i][n][1]-s[i][j+1][1])))
		}
		s2, s5 = 0, 0
		for i := m - 1; i >= 0; i-- { // 从下往上，枚举左拐还是右拐
			s2 += c25[grid[i][j]][0]
			s5 += c25[grid[i][j]][1]
			ans = max(ans, max(min(s2+s[i][j][0], s5+s[i][j][1]), min(s2+s[i][n][0]-s[i][j+1][0], s5+s[i][n][1]-s[i][j+1][1])))
		}
	}
	return
}

func max(a, b int) int { if a < b { return b }; return a }
func min(a, b int) int { if a > b { return b }; return a }
  • Post title：早起刷题（Day 16）
  • Post author：洪笳淏
  • Create time：2022-04-18 06:00:00
  • Post link：https://jiahaohong1997.github.io/2022/04/18/早起刷题（Day 16）/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments