3 条题解
-
1
#include<bits/stdc++.h> using namespace std; int a[10]; int main(){ string s; cin>>s; for(int i=0;i<s.size();i++){ if(s[i]'s'){ int k=i+1; for(int j=i+1;j<s.size();j++){ if(s[j]'w'){ for(int l=j+1;l<s.size();l++){ if(s[l]'i'){ for(int p=l+1;p<s.size();p++){ if(s[p]'p'){ for(int o=p+1;o<s.size();o++){ if(s[o]'e'){ for(int h=o+1;h<s.size();h++){ if(s[h]'r'){ cout<<k; return 0; } } } } } } } } } } } } cout<<-1;return 0; }
-
0
捣蛋鬼别捣蛋
顶级智斗,其实就是按顺序在所给串里依次匹配目标串的每个字符,只要匹配完最后一个字符便可直接结束遍历,反之则无法成功匹配。做得我冷汗直冒
参考代码(python)
from sys import stdin s=list(stdin.readline().rstrip()) goal=list('swiper') begin=-1 idx=0 for i in range(len(s)): if s[i]==goal[idx]: idx+=1 if idx==1: begin=i+1 if idx==6: break if idx==6: print(begin) else: print(-1) -
0
捣蛋鬼别捣蛋
我们要在一个字符串
s中判断是否存在单词"swiper"的子序列(即可以不连续,但顺序要保持)。 一旦找到"swiper"的完整序列,就输出其中第一个字母's'的位置(从 1 开始计数); 如果整篇游记中都无法找到完整的"swiper",则输出-1。换句话说,我们要在字符串
s中寻找一个满足顺序的匹配:s → w → i → p → e → r但中间允许夹杂任意其他字符。
题目本质是 子序列匹配 问题。
我们可以用两个指针来做:
- 指针
i:遍历游记字符串s; - 指针
j:匹配"swiper"当前需要的字母。
算法逻辑如下:
-
初始
j = 0(要找"swiper"[0]" == 's'); -
从左到右扫描
s;-
如果
s[i] == t[j]:- 若此时
j == 0,说明刚匹配到's',记录start = i; j++,进入下一个要匹配的字母;- 若
j == 6,说明"swiper"已完整匹配; 输出start + 1(因为题目要求 1-based 下标); 程序结束。
- 若此时
-
-
扫描完若仍未匹配完整,则输出
-1。
参考代码
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin >> s; string t = "swiper"; int j = 0; int start = -1; for (int i = 0; i < (int)s.size(); i++) { if (s[i] == t[j]) { if (j == 0) start = i; j++; if (j == (int)t.size()) { cout << start + 1 << "\n"; return 0; } } } cout << -1 << "\n"; return 0; }
总结
“Swiper, no swiping! Dora 用双指针就能抓住你。”
- 指针
- 1
信息
- ID
- 1098
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 264
- 已通过
- 43
- 上传者