早起刷题（Day 9）
洪笳淏 Lv4
 2022-04-10 22:00:00      

本文是对 2022.04.09 周赛的复盘

LeetCode6037. 按奇偶性交换后的最大数字

#数组

题目描述

给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。
返回交换 任意 次之后 num 的 最大 可能值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 1：
输入：num = 1234
输出：3412
解释：交换数字 3 和数字 1 ，结果得到 3214 。
交换数字 2 和数字 4 ，结果得到 3412 。
注意，可能存在其他交换序列，但是可以证明 3412 是最大可能值。
注意，不能交换数字 4 和数字 1 ，因为它们奇偶性不同。

示例 2：
输入：num = 65875
输出：87655
解释：交换数字 8 和数字 6 ，结果得到 85675 。
交换数字 5 和数字 7 ，结果得到 87655 。
注意，可能存在其他交换序列，但是可以证明 87655 是最大可能值。
 

提示：
1 <= num <= 109

解题思路

(1). 初始化三个数组 array、array1、array2，array用于记录数字对应位置上是奇数还是偶数、array1用于保存并排序所有的偶数、array2用于保存并排序所有的奇数；
(2). 根据 array 保存的对应位置的奇偶行，从大到小依次取出array1或array2 中的数；

时间复杂度

O(N)

解题代码

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
func largestInteger(num int) int {

	array1 := make([]int, 0)
	array2 := make([]int, 0)
	array := make([]bool, 0)

	for num > 0 {
		x := num % 10
		if x%2 == 0 {
			array1 = append(array1, x)
			array = append(array, true)
		} else {
			array2 = append(array2, x)
			array = append(array, false)
		}

		num /= 10
	}

	sort.Ints(array1)
	sort.Ints(array2)

	ret := 0
	for i:=len(array)-1; i>=0; i-- {
		ret *= 10
		if array[i] {
			ret += array1[len(array1)-1]
			array1 = array1[:len(array1)-1]
		} else {
			ret += array2[len(array2)-1]
			array2 = array2[:len(array2)-1]
		}
	}

	return ret
}

LeetCode6038. 向表达式添加括号后的最小结果

#字符串

题目描述

给你一个下标从 0 开始的字符串 expression ，格式为 “<num1>+<num2>” ，其中 <num1> 和 <num2> 表示正整数。
请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，并且计算后可以得到 最小 可能值。左括号 必须 添加在 ‘+’ 的左侧，而右括号必须添加在 ‘+’ 的右侧。
返回添加一对括号后形成的表达式 expression ，且满足 expression 计算得到 最小 可能值。如果存在多个答案都能产生相同结果，返回任意一个答案。
生成的输入满足：expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
示例 1：
输入：expression = "247+38"
输出："2(47+38)"
解释：表达式计算得到 2 * (47 + 38) = 2 * 85 = 170 。
注意 "2(4)7+38" 不是有效的结果，因为右括号必须添加在 '+' 的右侧。
可以证明 170 是最小可能值。

示例 2：
输入：expression = "12+34"
输出："1(2+3)4"
解释：表达式计算得到 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20 。

示例 3：
输入：expression = "999+999"
输出："(999+999)"
解释：表达式计算得到 999 + 999 = 1998 。
 
提示：
3 <= expression.length <= 10
expression 仅由数字 '1' 到 '9' 和 '+' 组成
expression 由数字开始和结束
expression 恰好仅含有一个 '+'.
expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围

解题思路

(1). 首先要完成一个对特定字符串结果的计算函数，这个函数主要是筛选出计算表达式的前中后三个部分即可；
(2). 分别将 “+” 前后的数字字符串提取出来，分别在可能的位置添加正反括号；
(3). 对于 ‘(‘ 而言，可能添加的位置在 b1 的 [0,len(b1))；
(3). 对于 ‘)’ 而言，可能添加的位置在 b2 的 [1,len(b2)]；

时间复杂度

O(len(s1)*len(s2))

解题代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
func minimizeResult(expression string) string {

	var cal func(string) int
	cal = func(s string) int {
		s1 := ""
		i := 0
		for ; i<len(s); i++ {
			if s[i] >= '0' && s[i] <= '9' {
				s1 += s[i:i+1]
			} else {
				break
			}
		}

		i++
		a, b, pre := "", "", true
		for ; i<len(s); i++ {
			if s[i] >= '0' && s[i] <= '9' && pre {
				a += s[i:i+1]
			} else if s[i] == '+' {
				pre = false
			} else if s[i] >= '0' && s[i] <= '9' && !pre {
				b += s[i:i+1]
			} else if s[i] == ')' {
				break
			}
		}

		var preNum int
		if s1 == "" {
			preNum = 1
		} else {
			preNum, _ = strconv.Atoi(s1)
		}

		mid1, _ := strconv.Atoi(a)
		mid2, _ := strconv.Atoi(b)
		
		s2 := ""
		for ; i<len(s); i++ {
			if s[i] >= '0' && s[i] <= '9' {
				s2 += s[i:i+1]
			}
		}

		if s2 != "" {
			lastNum, _ := strconv.Atoi(s2)
			return preNum*(mid1+mid2)*lastNum
		}

		return preNum*(mid1+mid2)
	}

	str := strings.Split(expression, "+")
	x1, _ := strconv.Atoi((str[0]))
	x2, _ := strconv.Atoi(str[1])
	ret := x1+x2
	retS := "("+expression+")"

	b1 := []byte(str[0])
	b2 := []byte(str[1])

	for i:=0; i<len(b1); i++ {
		b1 = append(b1[:i], append([]byte{'('}, b1[i:]...)...)
		// fmt.Println(b1)
		for j:=1; j<=len(b2); j++ {

			b2 = append(b2[:j], append([]byte{')'}, b2[j:]...)...)
			t := cal(string(b1)+"+"+string(b2))
			//fmt.Println(string(b1)+"+"+string(b2), t)
			if t < ret {
				ret = t
				retS = string(b1)+"+"+string(b2)
			}
			b2 = append(b2[:j], b2[j+1:]...)
		}

		b1 = append(b1[:i], b1[i+1:]...)
	}
	
	return retS
}

LeetCode6039. K 次增加后的最大乘积

#数组

题目描述

给你一个非负整数数组 nums 和一个整数 k 。每次操作，你可以选择 nums 中 任一 元素并将它 增加 1 。
请你返回 至多 k 次操作后，能得到的 nums的 最大乘积 。由于答案可能很大，请你将答案对 109 + 7 取余后返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
示例 1：
输入：nums = [0,4], k = 5
输出：20
解释：将第一个数增加 5 次。
得到 nums = [5, 4] ，乘积为 5 * 4 = 20 。
可以证明 20 是能得到的最大乘积，所以我们返回 20 。
存在其他增加 nums 的方法，也能得到最大乘积。


示例 2：
输入：nums = [6,3,3,2], k = 2
输出：216
解释：将第二个数增加 1 次，将第四个数增加 1 次。
得到 nums = [6, 4, 3, 3] ，乘积为 6 * 4 * 3 * 3 = 216 。
可以证明 216 是能得到的最大乘积，所以我们返回 216 。
存在其他增加 nums 的方法，也能得到最大乘积。
 

提示：
1 <= nums.length, k <= 105
0 <= nums[i] <= 106

解题思路

(1). 先从大到小排序数组；
(2). 进入循环，循环的结束条件是 k<0；
(3). 从数组的末尾向前遍历，如果当前数字等于上一次循环中未进行更改的后面数字，那么将当前数字加 1；
(4). 如果当前数字大于输一次循环中为进行更改的后面数字，那么回到数组末尾进行循环；
(5). 当从后向前遍历完整个数组，再次回到数组末尾；
(6). 跳出循环后，从头到尾计算结果。

时间复杂度

O(k*N)

解题代码

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
func maximumProduct(nums []int, k int) int {

	const Max = 1000000007
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] > nums[j]
	})

	i := len(nums)-1
	x := nums[i]
	for k > 0 {
		if i >= 0 {
			if nums[i] == x {
				nums[i]++
				i--
				k--
			} else if nums[i] >= x+1 {
				i = len(nums)-1
				x = nums[i]
			}
		} else {
			i = len(nums)-1
			x = nums[i]
		}
		//fmt.Println(nums)
	}

	//fmt.Println(nums)
	ret := 1
	for i:=0; i<len(nums); i++ {
		ret = ret*nums[i]%Max
	}
	
	return ret
}

LeetCode6040. 花园的最大总美丽值

#二分查找 #前缀和

题目描述

Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。
给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花 不能 移走。同时给你 newFlowers ，表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target ，full 和 partial 。
如果一个花园有 至少 target 朵花，那么这个花园称为 完善的 ，花园的 总美丽值 为以下分数之 和 ：
完善 花园数目乘以 full.
剩余 不完善 花园里，花的 最少数目 乘以 partial 。如果没有不完善花园，那么这一部分的值为 0 。
请你返回 Alice 种最多 newFlowers 朵花以后，能得到的 最大 总美丽值。

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
示例 1：
输入：flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
输出：14
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 2 朵花
- 在第 1 个花园种 3 朵花
- 在第 2 个花园种 1 朵花
- 在第 3 个花园种 1 朵花
花园里花的数目为 [3,6,2,2] 。总共种了 2 + 3 + 1 + 1 = 7 朵花。
只有 1 个花园是完善的。
不完善花园里花的最少数目是 2 。
所以总美丽值为 1 * 12 + 2 * 1 = 12 + 2 = 14 。
没有其他方案可以让花园总美丽值超过 14 。

示例 2：
输入：flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
输出：30
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 3 朵花
- 在第 1 个花园种 0 朵花
- 在第 2 个花园种 0 朵花
- 在第 3 个花园种 2 朵花
花园里花的数目为 [5,4,5,5] 。总共种了 3 + 0 + 0 + 2 = 5 朵花。
有 3 个花园是完善的。
不完善花园里花的最少数目为 4 。
所以总美丽值为 3 * 2 + 4 * 6 = 6 + 24 = 30 。
没有其他方案可以让花园总美丽值超过 30 。
注意，Alice可以让所有花园都变成完善的，但这样她的总美丽值反而更小。
 

提示：
1 <= flowers.length <= 105
1 <= flowers[i], target <= 105
1 <= newFlowers <= 1010
1 <= full, partial <= 105

解题思路

(1). 将 flowers 从小到大排序；
(2). 贪心：让靠后的 flowers[i] 增加至 target，其余的 flowers 的最小值尽量大；
(3). 外层循环在枚举完善花园个数的前提下，内层循环我们要去计算剩余newFlowers 花朵数目下不完善花园区间内能拿到的最小值，这里面我们通过二分查找的方式来枚举最小值（具有二段性），check 函数里面先找到大于等于mid 的位置，然后判断剩下的数全部补充到 mid 朵花够不够，最后二分的结果就是当前不完善花园区间内能拿到的最小值，更新答案即可。
注： 外层循环枚举时特判一下ii等于00的情况，因为此时j = i - 1会越界。

解题代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
func maximumBeauty(flowers []int, newFlowers int64, target int, full int, partial int) int64 {  
   sort.Ints(flowers)  
   n := len(flowers)  
  
   // count:已经完善的个数  
 count := 0  
 // 计算 >= target数目, 退出循环后 flowers[0, idx] < target idx := n - 1  
 for idx >= 0 && flowers[idx] >= target {  
      count++  
 idx--  
 }  
   //fmt.Println("idx:", idx, "count:", count)  
  
 // 全部都是完善的  
 if idx == -1 {  
      return int64(n * full)  
   }  
  
   sum := make([]int64, n + 1)  
   for i := 1; i <= n; i++ {  
      sum[i] = sum[i - 1] + int64(flowers[i - 1])  
   }  
  
   check := func(left, right, remain, t int) bool {  
      // 1.找到值 < t的区间的右端点  
 for left < right {  
         mid := left + (right - left + 1) / 2  
 if flowers[mid] < t {  
            left = mid  
         } else {  
            right = mid - 1  
 }  
      }  
      // 2.检查区间[0, left] 是否可以完善为t  
 return int64(remain) >= int64(t * (left + 1)) - sum[left + 1]  
  
   }  
  
   var res int64  
  
 // cnt: 新的变成完善的个数, 从右往左填  
 for cnt := 0; cnt <= idx + 1; cnt++ {  
      // 区间：[idx - cnt + 1,idx]完善, [0, idx - cnt]不完善，并计算[0, idx - cnt]中的最小值的最大值  
 // 填充完区间[idx - cnt + 1, idx]后剩余可种的花的数目  
 remain := newFlowers - (int64(target * cnt) - (sum[idx + 1] - sum[idx - cnt + 1]))  
  
      //fmt.Println("remain:", remain)  
 if remain < 0 {  
         break  
 }  
  
      // 计算 [0, i - 1]中的最小值, 直接二分答案。  
 left, right := flowers[0], target - 1  
  
 for left < right {  
         mid := left + (right - left + 1) / 2  
 // 检查是否能够将区间[0, idx -cnt]中，值 < mid的区间（假设是区间[0, j]）全部完善为mid  
 if check(0, idx - cnt, int(remain), mid) {  
            left = mid  
         } else {  
            right = mid - 1  
 }  
  
      }  
  
      //fmt.Println(i, count + idx - i + 1, left)  
  
 // 如果全部完善， 则只有 完善数目 * full if count + cnt == n {  
         res = max(res, int64((count + cnt) * full))  
      } else {  
         // 完善的数量：count + cnt, 未完善中最小值：left  
 res = max(res, int64((count + cnt) * full + left * partial))  
      }  
  
   }  
  
   return res  
  
}  
  
func max(a, b int64) int64 {  
   if a >= b {  
      return a  
   }  
   return b  
}
  • Post title：早起刷题（Day 9）
  • Post author：洪笳淏
  • Create time：2022-04-10 22:00:00
  • Post link：https://jiahaohong1997.github.io/2022/04/10/早起刷题（Day 9）/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments