2021-04-05：给两个长度分别为M和N的整型数组nums1和nums2，其中每个值都不大于9，

2021-04-05：给两个长度分别为M和N的整型数组nums1和nums2，其中每个值都不大于9，再给定一个正数K。你可以在nums1和nums2中挑选数字，要求一共挑选K个，并且要从左到右挑。返回所有可能的结果中，代表最大数字的结果。

福大大答案2021-04-05：

自然智慧想不到，需要练敏感度。
1.动态规划+选元素+双指针的合并。无代码。
2.动态规划+选元素+双指针的DC3合并。有代码。
2.1.dp[i][j]，i是数组序号，j是[0,K]的数，dp[i][j]是最优位置。
2.2.从arr1和arr2中选元素。
2.3.合并arr1中的选中的元素和arr2中的选中的元素，采用dc算法。
2.4.返回最大值。

代码用golang编写。代码如下：

package mainimport (    "fmt"    "index/suffixarray"    "unsafe")func main() {    nums1 := []int{3, 4, 6, 5}    nums2 := []int{9, 1, 2, 5, 8, 3}    k := 5    ret := maxNumber(nums1, nums2, k)    fmt.Println(ret)}func maxNumber(nums1 []int, nums2 []int, k int) []int {    len1 := len(nums1)    len2 := len(nums2)    if k < 0 || k > len1+len2 {        return nil    }    res := make([]int, k)    //两个动态规划    dp1 := getdp(nums1)    dp2 := getdp(nums2)    for get1 := getMax(0, k-len2); get1 <= getMin(k, len1); get1++ {        //arr1中挑元素        pick1 := maxPick(nums1, dp1, get1)        //arr2中挑元素        pick2 := maxPick(nums2, dp2, k-get1)        //和并挑的元素        merge := mergeBySuffixArray(pick1, pick2)        //获取最大值        if !moreThan(res, merge) {            res = merge        }    }    return res}func moreThan(pre []int, last []int) bool {    i := 0    j := 0    for i < len(pre) && j < len(last) && pre[i] == last[j] {        i++        j++    }    return j == len(last) || (i < len(pre) && pre[i] > last[j])}func mergeBySuffixArray(nums1 []int, nums2 []int) []int {    size1 := len(nums1)    size2 := len(nums2)    nums := make([]int, size1+1+size2)    for i := 0; i < size1; i++ {        nums[i] = nums1[i] + 2    }    nums[size1] = 1    for j := 0; j < size2; j++ {        nums[j+size1+1] = nums2[j] + 2    }    all := make([]byte, len(nums))    for i := 0; i < len(nums); i++ {        all[i] = byte(nums[i])    }    dc3 := NewFddSa(all)    ans := make([]int, size1+size2)    i := 0    j := 0    r := 0    for i < size1 && j < size2 {        if dc3.Rank[i] > dc3.Rank[j+size1+1] {            ans[r] = nums1[i]            r++            i++        } else {            ans[r] = nums2[j]            r++            j++        }    }    for i < size1 {        ans[r] = nums1[i]        r++        i++    }    for j < size2 {        ans[r] = nums2[j]        r++        j++    }    return ans}func maxPick(arr []int, dp [][]int, pick int) []int {    res := make([]int, pick)    for resIndex, dpRow := 0, 0; pick > 0; pick, resIndex = pick-1, resIndex+1 {        res[resIndex] = arr[dp[dpRow][pick]]        dpRow = dp[dpRow][pick] + 1    }    return res}func getdp(arr []int) [][]int {    size := len(arr)     // 0~N-1    pick := len(arr) + 1 // 1 ~ N    dp := make([][]int, size)    for i := 0; i < size; i++ {        dp[i] = make([]int, pick)    }    // get 不从0开始，因为拿0个无意义    for get := 1; get < pick; get++ { // 1 ~ N        maxIndex := size - get        // i~N-1        for i := size - get; i >= 0; i-- {            if arr[i] >= arr[maxIndex] {                maxIndex = i            }            dp[i][get] = maxIndex        }    }    return dp}func getMax(a int, b int) int {    if a > b {        return a    } else {        return b    }}func getMin(a int, b int) int {    if a < b {        return a    } else {        return b    }}type FddSa struct {    Sa   []int    Rank []int}func NewFddSa(bytes []byte) *FddSa {    ret := &FddSa{}    ret.Rank = make([]int, len(bytes))    ret.Sa = make([]int, len(bytes))    index := suffixarray.New(bytes)    p1 := uintptr(unsafe.Pointer(index)) //获取指针    p1 += 24    p2 := *(*[]int32)(unsafe.Pointer(p1)) //将指针转行成切片    for i := 0; i < len(bytes); i++ {        ret.Sa[i] = int(p2[i])   //sa数组        ret.Rank[int(p2[i])] = i //rank数组    }    return ret}

执行结果如下：

左神java代码
力扣321. 拼接最大数
评论

©著作权归作者所有：来自51CTO博客作者福大大的原创作品，如需转载，请注明出处，否则将追究法律责任

好知识，才能预见未来

赞赏

0人进行了赞赏支持

好知识，才能预见未来

更多相关文章

随机推荐