一个子序列的消除规则
  xaeiTka4h8LY 29天前 23 0

 一个子序列的消除规则如下:
1、在某一个子序列中,如果’1’的左边有’0’,那么这两个字符->“01"可以消除;
2、 在某一个子序列中,如果’3’的左边有’2’,那么这两个字符->“23"可以消除;
3、当这个子序列的某个部分消除之后,认为其他字符会自动贴在一起,可以继续寻找消除的机会。
比如,某个子序列"0231”,先消除掉"23”,那么剩下的字符贴在一起变成"01",继续消除就没有字符了,
如果某个子序列通过最优良的方式,可以都消掉,那么这样的子序列叫做“全消子序列”,
一个只由’0’、‘1’、‘2’、'3’四种字符组成的字符串str,可以生成很多子序列,返回“全消子序列”的最大长度,
字符串str长度 <= 200。

递归。

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

package main

import "fmt"

func main() {
    str1 := "010101"
    fmt.Println(maxDisappear(str1))
    str2 := "021331"
    fmt.Println(maxDisappear(str2))
}

// str[L...R]上,都能消掉的子序列,最长是多少?
func f(str string, L, R int) int {
    if L >= R {
        return 0
    }
    if L == R-1 {
        if (str[L] == '0' && str[R] == '1') || (str[L] == '2' && str[R] == '3') {
            return 2
        } else {
            return 0
        }
        //return (str[L] == '0' && str[R] == '1') || (str[L] == '2' && str[R] == '3') ? 2 : 0;
    }
    // L...R 有若干个字符 > 2
    // str[L...R]上,都能消掉的子序列,最长是多少?
    // 可能性1,能消掉的子序列完全不考虑str[L],最长是多少?
    p1 := f(str, L+1, R)
    if str[L] == '1' || str[L] == '3' {
        return p1
    }
    // str[L] =='0' 或者 '2'
    // '0' 去找 '1'
    // '2' 去找 '3'
    find := byte('1')
    if str[L] != '0' {
        find = '3'
    }
    //find := str[L] == '0' ? '1' : '3';
    p2 := 0
    // L() ......
    for i := L + 1; i <= R; i++ {
        // L(0) ..... i(1) i+1....R
        if str[i] == find {
            p2 = getMax(p2, f(str, L+1, i-1)+2+f(str, i+1, R))
        }
    }
    return getMax(p1, p2)
}

func maxDisappear(str string) int {
    if len(str) == 0 {
        return 0
    }
    return disappear(str, 0, len(str)-1)
}

// s[l..r]范围上,如题目所说的方式,最长的都能消掉的子序列长度
func disappear(s string, l, r int) int {
    if l >= r {
        return 0
    }
    if l == r-1 {
        if (s[l] == '0' && s[r] == '1') || (s[l] == '2' && s[r] == '3') {
            return 2
        } else {
            return 0
        }
        //return (s[l] == '0' && s[r] == '1') || (s[l] == '2' && s[r] == '3') ? 2 : 0;
    }
    p1 := disappear(s, l+1, r)
    if s[l] == '1' || s[l] == '3' {
        return p1
    }
    p2 := 0
    find := byte('1')
    if s[l] != '0' {
        find = '3'
    }
    //find := s[l] == '0' ? '1' : '3';
    for i := l + 1; i <= r; i++ {
        if s[i] == find {
            p2 = getMax(p2, disappear(s, l+1, i-1)+2+disappear(s, i+1, r))
        }
    }
    return getMax(p1, p2)
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

执行结果如下:

2021-12-29: 一个子序列的消除规则如下: 1、在某一个子序列中,如果‘1‘的左边有‘0‘,那么这两个字符->“01“可以消除; 2、 在某一个子序列中,如果‘3‘的左边有‘2‘,那么这两个字

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 29天前 0

暂无评论

推荐阅读
xaeiTka4h8LY