文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

特殊序列 是由 正整數(shù) 個(gè) 0 ，緊接著 正整數(shù) 個(gè) 1 ，最后 正整數(shù) 個(gè) 2 組成的序列。

比方說，[0,1,2] 和 [0,0,1,1,1,2] 是特殊序列。
相反，[2,1,0] ，[1] 和 [0,1,2,0] 就不是特殊序列。

給你一個(gè)數(shù)組 nums （僅 包含整數(shù) 0，1 和 2），請(qǐng)你返回 不同特殊子序列的數(shù)目 。
由于答案可能很大，請(qǐng)你將它對(duì) 10^9 + 7 取余 后返回。

一個(gè)數(shù)組的 子序列 是從原數(shù)組中刪除零個(gè)或者若干個(gè)元素后，剩下元素不改變順序得到的序列。
如果兩個(gè)子序列的 下標(biāo)集合 不同，那么這兩個(gè)子序列是 不同的 。

示例 1： 輸入：nums = [0,1,2,2] 輸出：3 解釋：特殊子序列為 [0,1,2,2]，[0,1,2,2] 和 [0,1,2,2] 。示例 2： 輸入：nums = [2,2,0,0] 輸出：0 解釋：數(shù)組 [2,2,0,0] 中沒有特殊子序列。示例 3： 輸入：nums = [0,1,2,0,1,2] 輸出：7 解釋：特殊子序列包括： - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2]提示： 1 <= nums.length <= 10^5 0 <= nums[i] <= 2

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-number-of-special-subsequences
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

class Solution { public:int countSpecialSubsequences(vector<int>& nums) {long long p0 = 0, p1 = 0, p2 = 0, mod = 1e9+7;for(auto n : nums){if(n==0){p0 = (p0*2+1)%mod;//前面的0有多少種取法，2進(jìn)制}else if(n==1){p1 = (p0+p1*2)%mod;//以1結(jié)尾的種類//當(dāng)前1是第一個(gè)，前面0結(jié)尾的有 p0種//當(dāng)前1不取，前面以1結(jié)尾的有 p1種//當(dāng)前1取，前面以1結(jié)尾的有 p1種// 三種情況合起來}else{p2 = (p1+p2*2)%mod;//同理}}return p2;} };

156 ms 168.1 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1955. 统计特殊子序列的数目的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。