有四种诗的韵律分别为: AABB、ABAB、ABBA、AAAA。
  xaeiTka4h8LY 29天前 23 0

有四种诗的韵律分别为: AABB、ABAB、ABBA、AAAA。
比如 : 1 1 3 3就属于AABB型的韵律、6 6 6 6就属于AAAA型的韵律等等,
一个数组arr,当然可以生成很多的子序列,如果某个子序列一直以韵律的方式连接起来,我们称这样的子序列是有效的。
比如, arr = { 1, 1, 15, 1, 34, 1, 2, 67, 3, 3, 2, 4, 15, 3, 17, 4, 3, 7, 52, 7, 81, 9, 9 },
arr的一个子序列为{1, 1, 1, 1, 2, 3, 3, 2, 4, 3, 4, 3, 7, 7, 9, 9},
其中1, 1, 1, 1是AAAA、2, 3, 3, 2是ABBA、4, 3, 4, 3是ABAB、7, 7, 9, 9是AABB,
可以看到,整个子序列一直以韵律的方式连接起来,所以这个子序列是有效的。
给定一个数组arr, 返回最长的有效子序列长度。
题目限制 : arr长度 <= 4000, arr中的值<= 10^9。
离散化之后,arr长度 <= 4000, arr中的值<= 4000。

课堂有同学提出了贪心策略(这题还真是有贪心策略),是正确的
AABB
ABAB
ABBA
AAAA
先看前三个规则:AABB、ABAB、ABBA
首先A、A、B、B的全排列为:
AABB -> AABB
ABAB -> ABAB
ABBA -> ABBA
BBAA -> 等同于AABB,因为A和B谁在前、谁在后都算是 : AABB的范式
BABA -> 等同于ABAB,因为A和B谁在前、谁在后都算是 : ABAB的范式
BAAB -> 等同于ABBA,因为A和B谁在前、谁在后都算是 : ABBA的范式
也就是说,AABB、ABAB、ABBA这三个规则,可以这么用:
只要有两个不同的数,都出现2次,那么这一共4个数就一定符合韵律规则。
所以:

1.当来到arr中的一个数字num的时候,
如果num已经出现了2次了, 只要之前还有一个和num不同的数,
也出现了两次,则一定符合了某个规则, 长度直接+4,然后清空所有的统计

2.当来到arr中的一个数字num的时候,
如果num已经出现了4次了(规则四), 长度直接+4,然后清空所有的统计
但是如果我去掉某个规则,该贪心直接报废,比如韵律规则变成:
AABB、ABAB、AAAA
因为少了ABBA, 所以上面的化简不成立了, 得重新分析新规则下的贪心策略
而尝试的方法就更通用(也就是maxLen3),只是减少一个分支而已
这个贪心费了很多心思,值得点赞!

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

package main

import "fmt"

func main() {

    arr := []int{1, 1, 2, 2}
    ret := maxLen4(arr)
    fmt.Println(ret)
}

func maxLen4(arr []int) int {
    // 统计某个数(key),出现的次数(value)
    map0 := make(map[int]int)
    // tow代表目前有多少数出现了2次
    two := 0
    // ans代表目前符合韵律链接的子序列增长到了多长
    ans := 0
    // 当前的num出现了几次
    numTimes := 0
    for _, num := range arr {
        // 对当前的num,做次数统计
        map0[num]++
        // 把num出现的次数拿出来
        numTimes = map0[num]
        // 如果num刚刚出现了2次, 那么目前出现了2次的数,的数量,需要增加1个
        //two += numTimes == 2 ? 1 : 0;
        if numTimes == 2 {
            two += 1
        }
        // 下面的if代表 :
        // 如果目前有2个数出现2次了,可以连接了
        // 如果目前有1个数出现4次了,可以连接了
        if two == 2 || numTimes == 4 {
            ans += 4
            //map.clear();
            map0 = make(map[int]int)
            two = 0
        }
    }
    return ans
}

执行结果如下:

2022-01-05:有四种诗的韵律分别为: AABB、ABAB、ABBA、AAAA。 比如 : 1 1 3 3就属于AABB型的韵律、

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

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

暂无评论

推荐阅读
xaeiTka4h8LY