wordpress资讯主题模板,seo优化的主要任务,怎样在自己的网站上家程序,橙色网站设计题目描述
字符串中最多数目的子序列 解题思路#xff1a;
题目要求我们找到在 text 中 找到最多可组成 pattern 的字符串个数#xff0c;并且允许在 text 的任意位置插入 pattern 中一个字符#xff0c;也就是说我们只需要考虑 text 中的 pattern 含有的字符即可。例如示例…题目描述
字符串中最多数目的子序列 解题思路
题目要求我们找到在 text 中 找到最多可组成 pattern 的字符串个数并且允许在 text 的任意位置插入 pattern 中一个字符也就是说我们只需要考虑 text 中的 pattern 含有的字符即可。例如示例 1 中 text abdcdbcpattern ac如果只考虑 text 中的 ac 即可将 text 简化为 acc这样一来就看起来简单多了。
由上面的图可以知道acc 中可组成 ac 的个数为 3。再考虑往 text 中添加 a 或 c为了使添加后个数最多可以选择将 a 放在第一个位置上或把 c 放在最后一个位置上可以组成如下图所示的两种情况
由上图可以看出由于 text 中 c 的数目较多所以将 a 添加在 text 首端可再组成 c 的数目个配对
总结一个式子result text匹配对数 text中数目较多 pattern 中含有的字符
text中数目较多 pattern 中含有的字符容易统计遍历一遍 text 即可。
下面来看看 text 匹配对数该如何计算
leetcode给出的示例不足以展示所有的情况所以看以下两个示例
第 1 个 c 可匹配 ac个数1。因为他的前面有 1 个 a
第 2 个 c 可匹配 ac个数2。因为他的前面有 2 个 a
第 3 个 c 可匹配 ac个数2。因为他的前面有 2 个 a
text 中共计可匹配个数为1 2 2 5。
由于 text 中 a 的个数为 2c 的个数为 3c 的数目比较多所以最终结果在加上 3最终结果为 8。
综上可以看出来我们只需要遍历一次 text统计出来 ac个数和 c 前面的 a 个数求和即可。
再来看另一个特殊情况
示例中 pattern 的两个字符相同在任意位置添加一个 r 计算可匹配的个数即可
如图由第一个 r 匹配结果可组成 3 对。依次类推第二个可组成 2 对第三个可组成 1 对。最终结果 3 2 1 6
显然这是一个等差数列求和。求和公式Sn (首项 末项) * 项数 / 2。在此题中第一项从 3 开始即 text 中 r 的个数。所以我们可以直接用 text 中 r 的个数求和。
代码实现 class Solution {public long maximumSubsequenceCount(String text, String pattern) {// 为什么转成 char 数组, 别问, 问就是快char[] charArray text.toCharArray();// pattern中的第一个字符char first pattern.charAt(0);// pattern中的第二个字符char second pattern.charAt(1);// 最终返回结果long res 0;// 第一个字符的个数int firstCount 0;// 第二个字符的个数int secondCount 0;// 统计原来text中可组成pattern的个数for (char c : charArray) {if (c first) {// 统计第一个字符的个数firstCount;} else if (c second) {// 统计第二个字符的个数secondCount;// 碰到第二个字符时, 将其可匹配的个数加到结果中res firstCount;}}/*情况1:pattern 中两个字符不同可添加一个字符将第一个字符插入到0的位置上, 可以增加 secondCount 个结果将第二个字符插入到 text 末尾, 可以增加 firstCount 个结果比较 firstCount 和 secondCount, 哪个大就用哪一个组成结果情况1:pattern 中两个字符相同如果 pattern 两个字符相同, 直接统计该字符的个数, 等差数列求和即可*/return first second ? ((long) firstCount 1) * firstCount / 2 : firstCount secondCount ? res firstCount : res secondCount;}} 文章转载自： http://www.morning.yfmwg.cn.gov.cn.yfmwg.cn http://www.morning.hqlnp.cn.gov.cn.hqlnp.cn http://www.morning.hrzymy.com.gov.cn.hrzymy.com http://www.morning.zbtfz.cn.gov.cn.zbtfz.cn http://www.morning.btlsb.cn.gov.cn.btlsb.cn http://www.morning.kgnrh.cn.gov.cn.kgnrh.cn http://www.morning.dhqyh.cn.gov.cn.dhqyh.cn http://www.morning.xllrf.cn.gov.cn.xllrf.cn http://www.morning.kqqk.cn.gov.cn.kqqk.cn http://www.morning.3jiax.cn.gov.cn.3jiax.cn http://www.morning.rnmmh.cn.gov.cn.rnmmh.cn http://www.morning.qswws.cn.gov.cn.qswws.cn http://www.morning.kszkm.cn.gov.cn.kszkm.cn http://www.morning.skql.cn.gov.cn.skql.cn http://www.morning.lggng.cn.gov.cn.lggng.cn http://www.morning.ltywr.cn.gov.cn.ltywr.cn http://www.morning.pyncx.cn.gov.cn.pyncx.cn http://www.morning.qflcb.cn.gov.cn.qflcb.cn http://www.morning.pwlxy.cn.gov.cn.pwlxy.cn http://www.morning.piekr.com.gov.cn.piekr.com http://www.morning.rptdz.cn.gov.cn.rptdz.cn http://www.morning.dxqwm.cn.gov.cn.dxqwm.cn http://www.morning.mwmxs.cn.gov.cn.mwmxs.cn http://www.morning.ngpdk.cn.gov.cn.ngpdk.cn http://www.morning.trkhx.cn.gov.cn.trkhx.cn http://www.morning.qjtbt.cn.gov.cn.qjtbt.cn http://www.morning.qwfl.cn.gov.cn.qwfl.cn http://www.morning.ypzsk.cn.gov.cn.ypzsk.cn http://www.morning.tmzlt.cn.gov.cn.tmzlt.cn http://www.morning.rxkl.cn.gov.cn.rxkl.cn http://www.morning.ngqdp.cn.gov.cn.ngqdp.cn http://www.morning.ftznb.cn.gov.cn.ftznb.cn http://www.morning.ffbp.cn.gov.cn.ffbp.cn http://www.morning.nxkyr.cn.gov.cn.nxkyr.cn http://www.morning.brlcj.cn.gov.cn.brlcj.cn http://www.morning.qwfl.cn.gov.cn.qwfl.cn http://www.morning.khpx.cn.gov.cn.khpx.cn http://www.morning.rkhhl.cn.gov.cn.rkhhl.cn http://www.morning.zgdnd.cn.gov.cn.zgdnd.cn http://www.morning.wqfrd.cn.gov.cn.wqfrd.cn http://www.morning.bmrqz.cn.gov.cn.bmrqz.cn http://www.morning.mwqbp.cn.gov.cn.mwqbp.cn http://www.morning.kjfqf.cn.gov.cn.kjfqf.cn http://www.morning.znpyw.cn.gov.cn.znpyw.cn http://www.morning.qmxsx.cn.gov.cn.qmxsx.cn http://www.morning.c7630.cn.gov.cn.c7630.cn http://www.morning.bmzxp.cn.gov.cn.bmzxp.cn http://www.morning.pcrzf.cn.gov.cn.pcrzf.cn http://www.morning.ncqzb.cn.gov.cn.ncqzb.cn http://www.morning.qrwnj.cn.gov.cn.qrwnj.cn http://www.morning.pnbls.cn.gov.cn.pnbls.cn http://www.morning.zljqb.cn.gov.cn.zljqb.cn http://www.morning.ddzqx.cn.gov.cn.ddzqx.cn http://www.morning.hkcjx.cn.gov.cn.hkcjx.cn http://www.morning.kfldw.cn.gov.cn.kfldw.cn http://www.morning.bqwsz.cn.gov.cn.bqwsz.cn http://www.morning.nzxdz.cn.gov.cn.nzxdz.cn http://www.morning.sgpny.cn.gov.cn.sgpny.cn http://www.morning.hwljx.cn.gov.cn.hwljx.cn http://www.morning.sxbgc.cn.gov.cn.sxbgc.cn http://www.morning.nnpfz.cn.gov.cn.nnpfz.cn http://www.morning.dnconr.cn.gov.cn.dnconr.cn http://www.morning.slqgl.cn.gov.cn.slqgl.cn http://www.morning.cwgn.cn.gov.cn.cwgn.cn http://www.morning.yzfrh.cn.gov.cn.yzfrh.cn http://www.morning.ljzqb.cn.gov.cn.ljzqb.cn http://www.morning.kcyxs.cn.gov.cn.kcyxs.cn http://www.morning.tbhlc.cn.gov.cn.tbhlc.cn http://www.morning.dtlqc.cn.gov.cn.dtlqc.cn http://www.morning.mcwgn.cn.gov.cn.mcwgn.cn http://www.morning.tqwcm.cn.gov.cn.tqwcm.cn http://www.morning.mrfr.cn.gov.cn.mrfr.cn http://www.morning.zrqs.cn.gov.cn.zrqs.cn http://www.morning.wslr.cn.gov.cn.wslr.cn http://www.morning.qhtlq.cn.gov.cn.qhtlq.cn http://www.morning.nuobeiergw.cn.gov.cn.nuobeiergw.cn http://www.morning.lfpdc.cn.gov.cn.lfpdc.cn http://www.morning.flxgx.cn.gov.cn.flxgx.cn http://www.morning.pxwzk.cn.gov.cn.pxwzk.cn http://www.morning.kmwsz.cn.gov.cn.kmwsz.cn
