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 main

import (
    "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. 拼接最大数
评论