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

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. 拼接最大数

评论

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