力扣第249场比赛

力扣第249场比赛

1930题

题目:

给你一个字符串 s ,返回 s 中 长度为 3 的不同回文子序列 的个数。

即便存在多种方法来构建相同的子序列,但相同的子序列只计数一次。

回文 是正着读和反着读一样的字符串。

子序列 是由原字符串删除其中部分字符(也可以不删除)且不改变剩余字符之间相对顺序形成的一个新字符串。

例如,"ace" 是 "abcde" 的一个子序列。

提示:

  • 3 <= s.length <= 105
  • s 仅由小写英文字母组成

题解:

主要找到26个字母的最开始位置和最终的位置;

然后找到相同字母之间最多的不同字母数量;

然后把不同的数量统计在ans中即可。

需要会map的map.count和string s的s.size()和统计出现的不同的字母,相当于标注,用vector[i]==2(一个常量)。

代码:

 1 class Solution {
 2 public:
 3     int countPalindromicSubsequence(string s) {
 4         map<char,int> map1;
 5         map<char,int> map2;
 6         int n=s.size();
 7 
 8         for(int i=0;i<n;i++)
 9         {
10             if(map1.count(s[i])==1)//不断更新字母出现在终点的位置
11             {
12                 map2[s[i]]=i;
13             }
14             else
15             {
16                 map1[s[i]]=i;
17             }
18         }
19         int ans=0;
20         for(cahr i=a;i<a+26;i++)
21         {
22             if(!map1.count(i) || !map2.count(i))
23             {
24                 continue;
25             }
26             int start=map1[i];
27             int end=map2[i];
28             vector<int> vec(26);//用vec可变数组保存相距最远的相同字母之间的不同的字母的个数,最多是26个,
29             //也就是vec最长是26的长度
30             for(int j=start+1;j<end;j++)
31             {
32                 //把所有存在的可能性统计出来
33                 vec[s[i]-a]=3;
34             }
35             for(int k=0;k<26;k++)
36             {
37                 if(vec[k]==3)
38                 ans++;
39             }
40 
41         }
42         return ans;
43     }
44 };

 

 

 

参考链接:https://leetcode-cn.com/problems/unique-length-3-palindromic-subsequences/

https://leetcode-cn.com/problems/unique-length-3-palindromic-subsequences/solution/c-xun-zhao-hui-wen-guan-jian-huan-shi-yi-264r/

 

力扣第249场比赛

上一篇:centos7 centos-home 磁盘空间转移至centos-root下


下一篇:最大正方形 暴力+动态规划