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/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
