b2c电商网站建设_上海网站推广定制_网站优化排名方案_企业品牌推广方案

Problem: 2207. 字符串中最多数目的子序列

前面先是我的两次遍历的代码及思路，后面是学习灵神的思路写的一此遍历的改进。

思路

贪心：

本题主要思路就是贪心，我们需要在text中插入pattern的一个元素使能够找到最多的pattern串，其实不难发现pattern[0]插入位置越靠左，能和text串其他元素组成pattern的个数就越多，而pattern[1]插入位置越靠右能组成的个数也越多，那么把它们分别插入到头尾就是最贪的做法。

前缀和：

如何统计子序列的个数呢，需要分类讨论：

1. 当在首部插入pattern[0]时，可以统计其前缀和cnt0，后面每次遍历到pattern[1]就能组成cnt0个序列。
2. 对于尾部插入pattern[1]也是同样的道理。、
   到这里这道题也就解决了，我这个笨蛋思路就是统计两遍，但后来看了灵神题解才突然想到两次统计对于text中原始的pattern串的个数时重复统计的，不论是首插还是尾插，新增的序列的个数都是和新插入元素的组合，所以最后返回答案的时候加入一个最大的即可

一次遍历

class Solution {
public:long long maximumSubsequenceCount(string text, string pattern) {//插入pattern[0]在尽量靠前插入pattern[1]尽量靠后int cnt0 = 0, cnt1 = 0;long long ans = 0;for(char c : text){if(c == pattern[1]){ans += cnt0;cnt1++;}if(c == pattern[0]){cnt0++;}}return ans + max(cnt0, cnt1);}
};

笨蛋写法：

class Solution {
public:long long maximumSubsequenceCount(string text, string pattern) {//插入pattern[0]在尽量靠前插入pattern[1]尽量靠后int cnt0 = 1, cnt1 = 1;long long ans0 = 0, ans1 = 0;for(int i = 0; i < text.size();i++){ans0 += text[i] == pattern[1] ? cnt0 : 0;cnt0 += text[i] == pattern[0];}for(int i = text.size() - 1; i >= 0; i--){ans1 += text[i] == pattern[0] ? cnt1 : 0;cnt1 += text[i] == pattern[1];}return max(ans0, ans1);}
};