目录
321. 拼接最大数 Create Maximum Number 🌟🌟🌟
327. 区间和的个数 Count of Range Sum 🌟🌟🌟
321. 拼接最大数 Create Maximum Number
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
示例 1:
输入: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 输出: [9, 8, 6, 5, 3]
示例 2:
输入: nums1 = [6, 7] nums2 = [6, 0, 4] k = 5 输出: [6, 7, 6, 0, 4]
示例 3:
输入: nums1 = [3, 9] nums2 = [8, 9] k = 3 输出: [9, 8, 9]
代码：
package main
import "fmt"
func maxNumber(nums1 []int, nums2 []int, k int) []int {
n1, n2 := len(nums1), len(nums2)
if n1+n2 < k {
return nil
}
ans := make([]int, k)
for i := 0; i <= n1 && i <= k; i++ {
if k-i > n2 {
continue
}
s1 := getMaxSubsequence(nums1, i)
s2 := getMaxSubsequence(nums2, k-i)
s := merge(s1, s2)
if compare(s, 0, ans, 0) > 0 {
copy(ans, s)
}
}
return ans
}
func getMaxSubsequence(nums []int, k int) []int {
n := len(nums)
stack := make([]int, k)
top := -1
remain := n - k
for _, num := range nums {
for top >= 0 && stack[top] < num && remain > 0 {
top--
remain--
}
if top < k-1 {
top++
stack[top] = num
} else {
remain--
}
}
return stack
}
func merge(arr1, arr2 []int) []int {
n1, n2 := len(arr1), len(arr2)
if n1 == 0 {
return arr2
}
if n2 == 0 {
return arr1
}
ans := make([]int, n1+n2)
i, j, k := 0, 0, 0
for i < n1 && j < n2 {
if compare(arr1, i, arr2, j) > 0 {
ans[k] = arr1[i]
i++
} else {
ans[k] = arr2[j]
j++
}
k++
}
for i < n1 {
ans[k] = arr1[i]
i++
k++
}
for j < n2 {
ans[k] = arr2[j]
j++
k++
}
return ans
}
func compare(arr1 []int, i int, arr2 []int, j int) int {
for i < len(arr1) && j < len(arr2) {
diff := arr1[i] - arr2[j]
if diff != 0 {
return diff
}
i++
j++
}
return (len(arr1) - i) - (len(arr2) - j)
}
func main() {
nums1 := []int{3, 4, 6, 5}
nums2 := []int{9, 1, 2, 5, 8, 3}
k := 5
fmt.Println(maxNumber(nums1, nums2, k)) // 输出 [9, 8, 6, 5, 3]
nums1 = []int{6, 7}
nums2 = []int{6, 0, 4}
k = 5
fmt.Println(maxNumber(nums1, nums2, k)) // 输出 [6, 7, 6, 0, 4]
nums1 = []int{3, 9}
nums2 = []int{8, 9}
k = 3
fmt.Println(maxNumber(nums1, nums2, k)) // 输出 [9, 8, 9]
}
输出：
[9 8 6 5 3]
[6 7 6 0 4]
[9 8 9]
327. 区间和的个数 Count of Range Sum
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
示例 1：
输入：nums = [-2,5,-1], lower = -2, upper = 2 输出：3 解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
示例 2：
输入：nums = [0], lower = 0, upper = 0 输出：1
提示：
1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 1-10^5 <= lower <= upper <= 10^5- 题目数据保证答案是一个 32 位 的整数
代码：
package main
import "fmt"
func countRangeSum(nums []int, lower int, upper int) int {
preSum := make([]int, len(nums)+1)
for i, num := range nums {
preSum[i+1] = preSum[i] + num
}
return mergeSort(preSum, 0, len(preSum)-1, lower, upper)
}
func mergeSort(nums []int, l, r, lower, upper int) int {
if l >= r {
return 0
}
mid := (l + r) >> 1
count := mergeSort(nums, l, mid, lower, upper) + mergeSort(nums, mid+1, r, lower, upper)
i, j := mid+1, mid+1
for k := l; k <= mid; k++ {
for i <= r && nums[i]-nums[k] < lower {
i++
}
for j <= r && nums[j]-nums[k] <= upper {
j++
}
count += j - i
}
merge(nums, l, mid, r)
return count
}
func merge(nums []int, l, mid, r int) {
tmp := make([]int, r-l+1)
i, j, k := l, mid+1, 0
for i <= mid && j <= r {
if nums[i] < nums[j] {
tmp[k] = nums[i]
i++
} else {
tmp[k] = nums[j]
j++
}
k++
}
for i <= mid {
tmp[k] = nums[i]
i++
k++
}
for j <= r {
tmp[k] = nums[j]
j++
k++
}
copy(nums[l:r+1], tmp)
}
func main() {
nums := []int{-2, 5, -1}
lower := -2
upper := 2
fmt.Println(countRangeSum(nums, lower, upper))
nums = []int{0}
lower = -2
upper = 2
fmt.Println(countRangeSum(nums, lower, upper))
}
输出：
3
1
暴力枚举：
```golang
func countRangeSum(nums []int, lower int, upper int) int {
count := 0
for i := 0; i < len(nums); i++ {
for j := i; j < len(nums); j++ {
sum := 0
for k := i; k <= j; k++ {
sum += nums[k]
}
if sum >= lower && sum <= upper {
count++
}
}
}
return count
}
```
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/