2021-04-04:给定一个非负数组arr,和一个正数m。 返回arr的所有子序列中累加和%m之后的最大值。

福大大 答案2021-04-04:

自然智慧即可。
1.递归,累加和。
2.动态规划,累加和。
3.动态规划,累加和%m。
4.双向动态规划,累加和%m。

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

package mainimport (    "fmt"    "math/rand"    "sort"    "time")func main() {    rand.Seed(time.Now().Unix())    const TOTAL = 500    RightCount := 0    for i := 0; i < TOTAL; i++ {        arr := NewRandArr()        m := rand.Intn(200) + 1        fmt.Println(arr, m)        ret1 := max1(arr, m)        fmt.Println("1.递归,累加和:", ret1)        ret2 := max2(arr, m)        fmt.Println("2.动态规划,累加和:", ret2)        ret3 := max3(arr, m)        fmt.Println("3.动态规划,累加和%m:", ret3)        ret4 := max4(arr, m)        fmt.Println("4.双向动态规划,累加和%m:", ret4)        fmt.Println("---------------------")        if ret1 == ret2 && ret1 == ret3 && ret1 == ret4 {            RightCount++        }    }    fmt.Println("总数:", TOTAL)    fmt.Println("正确:", RightCount)}//递归,算出所有子序列的累加和func max1(arr []int, m int) int {    set := make(map[int]struct{})    process(arr, 0, 0, set)    max := 0    for sum, _ := range set {        max = getMax(max, sum%m)    }    return max}func process(arr []int, index int, sum int, set map[int]struct{}) {    if index == len(arr) {        set[sum] = struct{}{}    } else {        process(arr, index+1, sum, set)        process(arr, index+1, sum+arr[index], set)    }}func getMax(a int, b int) int {    if a > b {        return a    } else {        return b    }}//2.动态规划,算出所有的累加和func max2(arr []int, m int) int {    sum := 0    N := len(arr)    for i := 0; i < N; i++ {        sum += arr[i]    }    dp := make([][]bool, N)    for i := 0; i < N; i++ {        dp[i] = make([]bool, sum+1)    }    for i := 0; i < N; i++ {        dp[i][0] = true    }    dp[0][arr[0]] = true    for i := 1; i < N; i++ {        for j := 1; j <= sum; j++ {            dp[i][j] = dp[i-1][j]            if j-arr[i] >= 0 {                dp[i][j] = dp[i][j] || dp[i-1][j-arr[i]]            }        }    }    ans := 0    for j := 0; j <= sum; j++ {        if dp[N-1][j] {            ans = getMax(ans, j%m)        }    }    return ans}//3.动态规划,算出所有的模m的累加和。数组长度巨大,m不大。func max3(arr []int, m int) int {    N := len(arr)    // 0...m-1    dp := make([][]bool, N)    for i := 0; i < N; i++ {        dp[i] = make([]bool, m)    }    for i := 0; i < N; i++ {        dp[i][0] = true    }    dp[0][arr[0]%m] = true    for i := 1; i < N; i++ {        for j := 1; j < m; j++ {            // dp[i][j] T or F            dp[i][j] = dp[i-1][j]            cur := arr[i] % m            if cur <= j {                dp[i][j] = dp[i][j] || dp[i-1][j-cur]            } else {                dp[i][j] = dp[i][j] || dp[i-1][m+j-cur]            }        }    }    ans := 0    for i := 0; i < m; i++ {        if dp[N-1][i] {            ans = i        }    }    return ans}// 如果arr的累加和很大,m也很大// 但是arr的长度相对不大func max4(arr []int, m int) int {    if len(arr) == 1 {        return arr[0] % m    }    mid := (len(arr) - 1) / 2    sortSet1 := make(map[int]struct{})    process4(arr, 0, 0, mid, m, sortSet1)    sortSet2 := make(map[int]struct{})    process4(arr, mid+1, 0, len(arr)-1, m, sortSet2)    ans := 0    s1 := make([]int, 0)    for key, _ := range sortSet1 {        s1 = append(s1, key)    }    sort.Ints(s1)    //fmt.Println("s1:", s1)    s2 := make([]int, 0)    for key, _ := range sortSet2 {        s2 = append(s2, key)    }    sort.Ints(s2)    //fmt.Println("s2:", s2)    for _, leftMod := range s1 {        //ans = getMax(ans, leftMod + sortSet2.floor(m - 1 - leftMod));        index := NearestIndex2(s2, m-1-leftMod)        if index >= 0 {            ans = getMax(ans, leftMod+s2[index])        } else {            ans = getMax(ans, leftMod)        }    }    return ans}// 在arr上,找满足<=value的最右位置func NearestIndex2(arr []int, v int) int {    L := 0    R := len(arr) - 1    index := -1 // 记录最右的对号    for L <= R {        mid := L + (R-L)>>1        if arr[mid] <= v {            index = mid            L = mid + 1        } else {            R = mid - 1        }    }    return index}// 从index出发,最后有边界是end+1,arr[index...end]func process4(arr []int, index int, sum int, end int, m int, sortSet map[int]struct{}) {    if index == end+1 {        sortSet[sum%m] = struct {        }{}    } else {        process4(arr, index+1, sum, end, m, sortSet)        process4(arr, index+1, sum+arr[index], end, m, sortSet)    }}func NewRandArr() []int {    arrLen := rand.Intn(10) + 5    arr := make([]int, arrLen)    for i := 0; i < arrLen; i++ {        arr[i] = rand.Intn(50)    }    return arr}

执行结果如下:


左神java代码
评论

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

每一份赞赏源于懂得

赞赏

0人进行了赞赏支持

更多相关文章

  1. 用x种方式求第n项斐波那契数,99%的人只会第一种
  2. 20210104 递归
  3. 函数递归、匿名函数、内置函数
  4. 2021-03-30:给定一个整数组成的无序数组arr,值可能正、可能负、可
  5. 函数的递归
  6. C语言中的函数概念
  7. 解读:什么是Java的递归算法?
  8. 2021-03-21:给定一棵二叉树的头节点head,求以head为头的树中,最小深
  9. 面试题:为什么Java中的Collection类都继承了抽象类还要实现抽象类

随机推荐

  1. Android 图片侧滑展示RecyclerView简单实
  2. android的TableLayout布局界面元素填满整
  3. [转]Android EditView属性
  4. android 笔记 --- Android应用程序的权限
  5. 手动更新 Android SDK
  6. android adb命令 抓取系统各种 log
  7. android字体加粗的方法
  8. android studio ndk 开发以及问题
  9. Your CPU does not support required fea
  10. Android ProgressBar 各种样式大全