这道题我做的方法用了n2 的时间复杂度 太麻烦了
官方解答里用了 n的时间复杂度
一开始没看懂 这里详细解释一下
假设有一个序列
1 2 3 4 5 6 7 8 9
包含6 的长度为奇数的子序列有多少个？
6左边有5个数字 右边有3个数字
首先不看这个问题 写一个表格 加入某个数字在一个子序列里，不同长度下 左右两侧的数字分别有多少个：
长度为1： 0-0
长度为3：0-2 1-1 2-0
长度为5：0-4 1-3 2-2 3-1 4-0
长度为7：0-6 1-5 2-4 3-3 4-2 5-1 6-0
对于6而言 只满足这几种情况
0-0 0-2 和 2-0 2-2 和 4-0 4-2
1-1 1-3 和 3-1 3-3 和 5-1 5-3
左侧为偶数的 不能超过5 右侧为偶数的不能超过3
左侧为奇数的 不能超过5 右侧为奇数的 不能超过3
所以一共是
((5+1)//2 )((3+1)//2) + (5//2+1)(3//2+1) =32+32=12种
所有的数字都可以这么算 最后就得到答案了
这种方法只需要 n的时间复杂度
1588
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 题目描述 有两个长度分别为 n1，n2 的长条，长条每格高度分别为 h 或 2h，呈齿状上下咬合在一起。长条不能调...
- 1）这本书为什么值得看： Python语言描述，如果学的Python用这本书学数据结构更合适 2016年出版，内容...
- 笔者按照目录刷题，对于每一道题，力争使用效率最高（时间复杂度最低）的算法，并全部通过C++代码实现AC。(文中计算...
