G eli和字符串 题解

eli和字符串

https://ac.nowcoder.com/acm/contest/3002/G

本题其实用前缀和就可以做
因为每个字母出现一次,那么它的出现次数就+1,所以记录它的每个出现位置,用数组trace记录
具体做法:
struct node
{
int trace[200010], index=1;
} lt[26];

【trace类似于vector,莫习惯这么写了,见谅】

由于要求同个字母出现次数至少为k次的子段,不难证明即为要求同个字母出现k次的子段
这时候只要在刚刚记录下的trace中暴力找就好了
而其中lt记录下了所有字母的trace,所以暴力不会漏掉任意一种情况
时间复杂度(本蒟蒻不会算)估计大概是O(26*(n-k)),不会炸
附上完整代码:

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int trace[200010], in=1;
} sum[30];

int main()
{
    int n, k; cin>>n>>k;
    string s; cin>>s;
    for (int i=0; i<s.length(); i++)
    {
        int c = s[i] - 'a';
        sum[c].trace[sum[c].in++] = i;
    }
    int ans = 10000010;
    for (int i=0; i<26; i++)
    {
        for (int j=1; j<=sum[i].in-k; j++) ans = min(ans, sum[i].trace[j+k-1]-sum[i].trace[j]+1);
    }
    if (ans !=  10000010) cout<<ans;
    else cout<<-1;

}

【其中的10000010类似于inf,如果找完一轮后ans还是inf,那么说明没有满足条件的情况】

全部评论

相关推荐

1.自我介绍2.介绍一下mcp,&nbsp;skills3.了解react哪些状态管理库4.对话是sse还是什么?是用fetch还是EventSource?5.ts中的any&nbsp;和&nbsp;unknown讲一讲6.是直接用组件库的组件还是自己封装了一些别的7.代码输出题1function&nbsp;main()&nbsp;{{var&nbsp;a&nbsp;=&nbsp;1let&nbsp;b&nbsp;=&nbsp;2}console.log(a);console.log(b);}main()console.log(a);8.什么是块级作用域&nbsp;全局作用域&nbsp;函数作用域9.代码输出题2for&nbsp;(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(i);},&nbsp;100);}10.代码输出题3for&nbsp;(var&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&amp;lt;&nbsp;5;&nbsp;i++){function&nbsp;printText(temp)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(temp);},&nbsp;100);}printText(i)}11.代码输出题4for(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++){function&nbsp;printText(temp)&nbsp;{var&nbsp;temp&nbsp;=&nbsp;isetTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(temp);},&nbsp;100);}printText(i)}12.代码输出题5for(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++){function&nbsp;printText(temp)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{var&nbsp;temp&nbsp;=&nbsp;iconsole.log(temp);},&nbsp;100);}printText(i)}13.点击控制台输出题export&nbsp;default&nbsp;function&nbsp;App()&nbsp;{const&nbsp;[count,&nbsp;setCount]&nbsp;=&nbsp;useState(0)console.log('render',count)return&nbsp;(&lt;div&gt;&lt;h1&gt;{count}&lt;/h1&gt;{setCount(count&nbsp;+&nbsp;1)setTimeout(()&nbsp;=&amp;gt;&nbsp;console.log('setTimeout',&nbsp;count),&nbsp;1000)}}&amp;gt;+1&lt;/div&gt;)}//这个组件点击按钮后,控制台的输出顺序和值如下://&nbsp;1.&nbsp;render&nbsp;1&nbsp;(组件重新渲染,&nbsp;count&nbsp;更新为&nbsp;1)//&nbsp;2.&nbsp;setTimeout&nbsp;0&nbsp;(1秒后输出,注意这里是&nbsp;0&nbsp;而不是&nbsp;1)14.算法:给有序数组arr&nbsp;=&nbsp;[-4,&nbsp;-1,&nbsp;0,&nbsp;3,&nbsp;5],返回平方后的排序//&nbsp;有序数组平方后排序const&nbsp;arr&nbsp;=&nbsp;[-4,&nbsp;-1,&nbsp;0,&nbsp;3,&nbsp;5]function&nbsp;solution(arr)&nbsp;{const&nbsp;len&nbsp;=&nbsp;arr.lengthconst&nbsp;result&nbsp;=&nbsp;new&nbsp;Array(len)let&nbsp;left&nbsp;=&nbsp;0let&nbsp;right&nbsp;=&nbsp;len&nbsp;-&nbsp;1let&nbsp;index&nbsp;=&nbsp;len&nbsp;-&nbsp;1while&nbsp;(left&nbsp;&amp;lt;=&nbsp;right)&nbsp;{if&nbsp;(arr[left]&nbsp;*&nbsp;arr[left]&nbsp;&amp;gt;&nbsp;arr[right]&nbsp;*&nbsp;arr[right])&nbsp;{result[index]&nbsp;=&nbsp;arr[left]&nbsp;*&nbsp;arr[left]left++}&nbsp;else&nbsp;{result[index]&nbsp;=&nbsp;arr[right]&nbsp;*&nbsp;arr[right]right--}index--}return&nbsp;result}console.log(solution(arr));15.反问
查看14道真题和解析
点赞 评论 收藏
分享
01-11 08:47
门头沟学院 Java
choumoduji...:读研的目的就是为了以最快的速度和最低的要求完成“学校”规定的毕业标准,而不是所谓课题组的要求
点赞 评论 收藏
分享
评论
9
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务