正文

leetcode周赛第288场周赛（go语言实现版）(代码片段)

jiangxiaoju  jiangxiaoju  2022-11-30  189

关键词：

原创不易，未经允许，请勿转载。

文章目录

6037. 按奇偶性交换后的最大数字
6038. 向表达式添加括号后的最小结果
6039. K 次增加后的最大乘积
6040. 花园的最大总美丽值

代码收录在 https://github.com/jiang4869/go-algorithm 欢迎给个star

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

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

题意

给定一个数字num，可以把num中奇偶性相同的任意两位数字（即，都是奇数或者偶数）。改操作可以进行任意次数。

思路

因为go语言里面string是不可以修改的，所以只能先把数字转成int数组。
使用类似冒泡排序的思想，通过两个数的奇偶性和大小关系判断是否需要交换。具体看下方代码实现

代码实现

func largestInteger(num int) int 
	arr := make([]int, 0) // 注意这里转成数组后，数字是倒叙的
	for true 
		arr = append(arr, num%10)
		num /= 10
		if num == 0 
			break
		
	
	for i := 0; i < len(arr); i++ 
		for j := i + 1; j < len(arr); j++ 
			if arr[i]%2 == arr[j]%2 && arr[i] > arr[j]   // 奇偶性相同并且前面的数比后面的数大的话，就交换
				arr[i], arr[j] = arr[j], arr[i]
			
		
	
	num = 0 // 最后把数组转成最后的数字
	for i := len(arr) - 1; i >= 0; i-- 
		num = num*10 + arr[i]
	

	return num

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

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

题意

给一个加法表达式，仅有两个数字和一个加号组成。需要向表达式中添加一个括号，使得最后的计算结果最小。
例如247+38，添加括号后2(47+38)，结果为2*(47+38) = 2*85 = 170
左括号一定要在+号左侧，右括号一定要在+号右侧。并且添加后还要是一个合法的数学表达式。

思路

可以枚举括号添加的位置。例如对247+38这个表达式添加括号的话，左括号可能添加的情况有(247、2(47、24(7这三种。相当于是把一个数分割成了两个数（当括号在最左端时例外）

代码实现

func minimizeResult(expression string) string 
	splits := strings.Split(expression, "+")
	var minNum int32
	minNum = math.MaxInt32
	res := ""
	for i := 0; i <= len(splits[0]); i++ 
		for j := 0; j <= len(splits[1]); j++ 
			num1 := splits[0][0:i]
			num2 := splits[0][i:]
			num3 := splits[1][0:j]
			num4 := splits[1][j:]
            if len(num3) == 0   // 右括号不能再第二个数的最左右边，例如)24  这种情况是不合法的
				continue
			
			if len(num2) == 0  // 左括号不能再第一个数的最右边，例如247(  这种情况是不合法的
				continue
			
			var tmp int32
			tmp = 1
			if len(num1) > 0 
				tmp *= toNum(num1)
			
			if len(num4) > 0 
				tmp *= toNum(num4)
			
			n2 := toNum(num2)
			n3 := toNum(num3)
			tmp *= n2 + n3
			if tmp < minNum 
				minNum = tmp
				res = num1 + "(" + num2 + "+" + num3 + ")" + num4
			
		
	

	return res



func toNum(str string) int32 
	atoi1, _ := strconv.Atoi(str)
	return int32(atoi1)

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

K 次增加后的最大乘积

题意

给定一个数组nums和一个整数k。可以选择数组中的任意一个元素增加1。问操作k次后，nums数组最大的乘积是多少。

思路

加入我们选择数组中的一个元素a进行加1。其他元素的乘积为num。原数组最后乘积为a*num，当a加一后，最后乘积增加了num。根据贪心的思想，要使得最后的乘积最大，那么每次选择一个元素a后，剩余元素的乘积num越大，则最后的乘积也就越大。所以选择的元素a要最小。

代码实现

使用container中的heap来实现最小堆。每次取出堆顶的元素进行+1操作


type IntHeap struct 
	sort.IntSlice


func (h IntHeap) Push(x interface) 


func (h IntHeap) Pop() interface 
	return nil


const mod = int(1e9 + 7)

func maximumProduct(nums []int, k int) int 
	que := IntHeapnums
	heap.Init(&que)
	for k > 0 
		que.IntSlice[0]++
		heap.Fix(&que, 0)
		k--
	
	res := 1
	for _, val := range que.IntSlice 
		res = res * val % mod
	
	return res

6040. 花园的最大总美丽值

花园的最大总美丽值

题意

有n个花园，每个花园有flowers[i]朵花，给你一个newFlowers，表示还可以额外中的花的最大数目（不一定要种到这么多），同时给你的还有整数target ，full 和 partial。
如果一个花园有至少 target 朵花，那么这个花园称为完善的，花园的总美丽值为以下分数之和：

完善花园数目乘以 full.
剩余不完善花园里，花的最少数目乘以 partial 。如果没有不完善花园，那么这一部分的值为 0 。

问种最多 newFlowers 朵花以后，能得到的最大总美丽值。

思路

复制一个flowers数组nums，然后对flowers进行从大到小排序，对nums进行从小到大排序。
记录nums数组的前缀和。
枚举完善的花园数目，对于剩余不完善的部分，通过二分判断最少的花的数量是多少。
二分判断中的judge函数为func(nf int64, mid int, pos int)。nf为还可以种的花的数量，mid最少的花的数量。pos表示查找的区间nums[0:pos)。

代码实现

刚开始写的时候不知道go里面有现成的二分查找，所以手写了一个lower_bound。
lower_bound函数类似于c++中的lower_bound，找到第一个大于等于key的元素的位置。

func maximumBeauty(flowers []int, newFlowers int64, target, full, partial int) int64 
	var res int64
	nums := make([]int, len(flowers))
	copy(nums, flowers)
	sort.Slice(flowers, func(i, j int) bool 
		return flowers[i] > flowers[j]
	)
	pre := make([]int64, len(flowers)+10)
	size := len(flowers)
	if flowers[size-1] >= target 
		res = int64(size) * int64(full)
		return res
	

	sort.Ints(nums)
	for idx := range nums 
		pre[idx+1] = int64(nums[idx]) + pre[idx]
	

	judge := func(nf int64, mid int, pos int) bool 
		p := lowerBound(nums, 0, pos, mid)
		var tmp int64
		tmp = int64(p)*int64(mid) - pre[p]
		return tmp <= nf
	

	for idx, val := range flowers 
		if val >= target 
			continue
		
		l, r := flowers[size-1], target-1
		tmp := 0
		for l <= r 
			mid := l + (r-l)/2
			if judge(newFlowers, mid, size-idx) 
				tmp = int(max(int64(mid), int64(tmp)))
				l = mid + 1
			 else 
				r = mid - 1
			
		
		res = max(res, int64(full)*int64(idx)+int64(partial)*int64(tmp))
		newFlowers -= int64(target - val)
		if newFlowers <= 0 
			return res
		
	

	if newFlowers >= 0 
		res = max(res, int64(full)*int64(size))
	

	return res


func max(a, b int64) int64 
	if a > b 
		return a
	 else 
		return b
	


func lowerBound(nums []int, begin, end int, key int) int 
	l, r := begin, end
	for l < r 
		mid := l + (r-l)/2
		if nums[mid] >= key 
			r = mid
		 else 
			l = mid + 1
		
	
	return l

如果这篇文章对您有所帮助，麻烦点个一键三连。

原创不易，未经允许，请勿转载。

博客主页：https://xiaojujiang.blog.csdn.net/

leetcode周赛第288场周赛（go语言实现版）(代码片段)

原创不易，未经允许，请勿转载。文章目录6037.按奇偶性交换后的最大数字题意思路代码实现6038.向表达式添加括号后的最小结果题意思路代码实现6039.K次增加后的最大乘积题意思路代码实现6040.花园的最大总美丽值题意... 查看详情

leetcode周赛第288场周赛（go语言实现版）(代码片段)

leetcode周赛第291场周赛（go语言实现版）(代码片段)

原创不易，未经允许，请勿转载。代码收录在https://github.com/jiang4869/go-algorithm欢迎点个star文章目录6047.移除指定数字得到的最大结果题意思路代码实现6048.必须拿起的最小连续卡牌数题意思路代码实现6049.含最多K个可整除... 查看详情

leetcode周赛第291场周赛（go语言实现版）(代码片段)

leetcode第302场周赛(代码片段)

LeetCode第302场周赛第302场周赛6120.数组能形成多少数对6164.数位和相等数对的最大和6121.裁剪数字后查询第K小的数字6122.使数组可以被整除的最少删除次数总结第302场周赛我走得很慢！但我从不后退！6120.数组能形成多少数... 查看详情

leetcode第302场周赛(代码片段)

leetcode第303场周赛(代码片段)

LeetCode第303场周赛第303场周赛2351.第一个出现两次的字母2352.相等行列对2353.设计食物评分系统2354.优质数对的数目第303场周赛自己选择的路，就开心的走下去2351.第一个出现两次的字母第一个出现两次的字母循环扫描字符串s&#x... 查看详情

leetcode第303场周赛(代码片段)

leetcode第302场周赛(代码片段)

leetcode第304场周赛(代码片段)

文章目录LeetCode第304场周赛6132.使数组中所有元素都等于零6133.分组的最大数量6134.找到离给定两个节点最近的节点6135.图中的最长环LeetCode第304场周赛我总是不太聪明的样子，但是我总是想让自己变聪明的路上6132.使数组中所... 查看详情

leetcode第304场周赛(代码片段)

我也是leetcode周赛“三道题选手”啦第270场周赛(代码片段)

第270场周赛小结我的WeeklyContest270战况什么是LeetCode周赛？showmycode!复盘解决Hard题我的WeeklyContest270战况参加周赛有7次了，1928/12931应该是目前最好一次排名了，上周的周赛和双周赛也是只做对3道题，我也是LeetCode周... 查看详情

leetcode第136场周赛(代码片段)

菜鸡我只做出了一道。。。5055. 困于环中的机器人在无限的平面上，机器人最初位于 (0,0) 处，面朝北方。机器人可以接受下列三条指令之一："G"：直走1个单位"L"：左转90度"R"：右转90度机器人按顺序执行指令 instru... 查看详情

leetcode地平线专场——第308场周赛题解(代码片段)

前言：很久没做周赛了，上次做周赛还是本科期间(两年前)，因为过几个月就要找实习了，所以最近开始打周赛，希望能继续加油。上次打周赛还是两年前贪心+前缀和：6160.和有限的最长子序列这题的关... 查看详情

解题报告力扣第265场周赛

...题报告加群须知简单题1、算法线性枚举2、解题报告LeetCode2057.值相等的最小索引中等题1、算法链表2、解题报告LeetCode2058.找出临界点之间的最小和最大距离中等题1、算法广度优先搜索2、解题报告LeetCode2059.转化数字... 查看详情

解题报告力扣第280场周赛

...2、解题报告加群须知简单题1、算法递归2、解题报告LeetCode2169.得到0的操作数中等题1、算法贪心+线性最值（哈希表）2、解题报告LeetCode2170.使数组变成交替数组的最少操作数中等题1、算法贪心+排序2、... 查看详情