前言
这次蛮难的，第三题要用优先队列（堆来模拟），复杂度O(nlogn)，第四题hard不会。。。
第一题
2231.按奇偶性交换后的最大数字
2231.按奇偶性交换后的最大数字
题解
题目要求把给定数字最大化，偶数位置上的数字可以互换，奇数同理
思路：记录偶数位置的值和奇数的值，排序，还原即可
代码
func largestInteger(num int) int { mp := make(map[int][]int) idx := make([]byte, 0) //这里这里的切片idx存的下标 //原来数字第一位，第二位，第三位 ---> 第三位 第二位 第一位 //所以还原的时候要倒着遍历 for num != 0 { cnt := num % 10 num /= 10 if cnt%2 == 0 { //偶数 mp[0] = append(mp[0], cnt) idx = append(idx, '0') } else { mp[1] = append(mp[1], cnt) idx = append(idx, '1') } } //从小到大 sort.Ints(mp[0]) sort.Ints(mp[1]) ans := 0 for i := len(idx) - 1; i >= 0; i-- { if idx[i] == '0' { //偶数 length := len(mp[0]) ans = ans*10 + mp[0][length-1] mp[0] = mp[0][:length-1] } else { length := len(mp[1]) ans = ans*10 + mp[1][length-1] mp[1] = mp[1][:length-1] } } return ans }
第二题
2232.向表达式添加括号后的最小结果
2232.向表达式添加括号后的最小结果
题解
题目要求：在加号两边加括号，使得表达式算出来的值最小
3 <= expression.length <= 10 数据量较小，暴力即可
思路：先通过加号，把字符串分成两部分，partA和partB，然后在partA中枚举左括号的位置，在partB中枚举右括号的位置。那么partA被(分隔为两部分al和ar，partB同理被分割为bl和br，然后计算al * (ar + bl) * br即可
代码
func minimizeResult(expression string) string { plusIdx := strings.Index(expression, "+") minAns := math.MaxInt32 ans := "" for i := 0; i < plusIdx; i++ { //i是左括号的位置 partAL := expression[:i] partAR := expression[i:plusIdx] for j := plusIdx + 2; j <= len(expression); j++ { //j是右括号的位置 partBL := expression[plusIdx+1 : j] partBR := expression[j:] al, _ := strconv.Atoi(partAL) ar, _ := strconv.Atoi(partAR) bl, _ := strconv.Atoi(partBL) br, _ := strconv.Atoi(partBR) if al == 0 { al = 1 } if br == 0 { br = 1 } cnt := al * (ar + bl) * br //fmt.Println(partAL + "(" + partAR + "+" + partBL + ")" + partBR,"=",cnt) if minAns > cnt { minAns = cnt ans = partAL + "(" + partAR + "+" + partBL + ")" + partBR } } } return ans }
第三题
2233.K次增加后的最大乘积
2233.K次增加后的最大乘积
题解
题目：给你一个切片和一个k，切片中的数字可以递增1，所有元素递增次数共为k次，求切片所有元素的最大乘积
思路：想要最大乘积，那么必然要把数小的进行递增，所以每次把切片中最小的数取出来，然后加1，然后下一轮再取出最小的，再加1
1 <= nums.length, k <= 10^5
可以看到k的复杂度很高，那么for里面必须要用复杂度低的才能过
这里用小根堆来模拟优先队列
建堆：O(n)，修改元素，Push，Pop,Remove—>O(log n)
代码
func maximumProduct(nums []int, k int) int { if len(nums) == 1 { return nums[0] + k } var temp hp for i := 0; i < len(nums); i++ { heap.Push(&temp, nums[i]) } for k != 0 { temp[0]++ heap.Fix(&temp, 0) k-- } ans := 1 for i := 0; i < len(temp); i++ { ans *= temp[i] ans %= 1000000000 + 7 } return ans } type hp []int func (h hp) Len() int { return len(h) } func (h hp) Less(i, j int) bool { return h[i] < h[j] } func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *hp) Push(v interface{}) { *h = append(*h, v.(int)) } func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
第四题
2234.花园的最大总美丽值
2234.花园的最大总美丽值
题解
题目：给你一个花园切片，可种植花数目，和target，如果一个花园的花的数量>=target,那么这个花园就是完善的，否则就是不完善的，最后求所有完善的花园的数量 * full + 不完善花园中花的数量最少的花的数目 * partial
思路：
- 先排序
- 枚举完善花园数量
- 在枚举完善花园数量的同时，去计算不完善花园的花最大能到达多少个花
第三步计算不完善花数量重点在于这里
for ; x < i; x++ { if sumImperfectFlowers+restFlowers >= flowers[x]*x { sumImperfectFlowers += flowers[x] } else { break } }
剩余给不完善花园种植花的数量，加上原来不完善花的数量，处理计算出来的x，就是 剩余 不完善 花园里，花的 最少数目
代码
func maximumBeauty(flowers []int, newFlowers int64, target int, full int, partial int) int64 { sort.Ints(flowers) n := len(flowers) //最小的都满足，说明全都满足，直接剪枝 if flowers[0] >= target { return int64(full * n) } canPlantFlowers := int(newFlowers) preSum := make([]int, n+1) for i := 0; i < n; i++ { if flowers[i] > target { flowers[i] = target } //计算前缀和 preSum[i+1] = preSum[i] + flowers[i] } ans := 0 x := 0 sumImperfectFlowers := 0 //枚举完善数量 for i := 0; i <= n; i++ { perfectNum := n - i //计算(i,n]处变成完善，需要填充的鲜花数量 perfectNeed := target*perfectNum - (preSum[n] - preSum[i]) //如果需要的数量大于可以填充的数量，那就直接下一轮 if perfectNeed > canPlantFlowers { continue } //剩余可种植的数量，给不完善的用，尽量增大不完善数量中的最小值 restFlowers := canPlantFlowers - perfectNeed //最大化其余花园的花的最小数目,我认为这里是重点！很妙 for ; x < i; x++ { if sumImperfectFlowers+restFlowers >= flowers[x]*x { sumImperfectFlowers += flowers[x] } else { break } } imperfectNum := 0 if x > 0 { imperfectNum = (sumImperfectFlowers + restFlowers) / x //不能超过target-1，否则就变成完善的了 imperfectNum = min(imperfectNum, target-1) } ans = max(ans, partial*imperfectNum+full*perfectNum) } return int64(ans) } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b }
