网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索

 
 
 
日一二三四五六
       
       
       
       
       
       

签到排名:今日本吧第个签到,

本吧因你更精彩,明天继续来努力!

本吧签到人数:0

一键签到
成为超级会员,使用一键签到
一键签到
本月漏签0次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行补签。
连续签到:天  累计签到:天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
12月12日漏签0天
c语言吧 关注:801,522贴子:4,373,104
  • 看贴

  • 图片

  • 吧主推荐

  • 视频

  • 游戏

  • 9回复贴,共1页
<<返回c语言吧
>0< 加载中...

求助:破坏回文子串

  • 只看楼主
  • 收藏

  • 回复
  • 可泣的stone
  • 低能力者
    5
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼



  • 可泣的stone
  • 低能力者
    5
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
顶一下。。。


2025-12-12 14:59:45
广告
不感兴趣
开通SVIP免广告
  • 瓦妹
  • 麻婆豆腐
    11
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
1,如果是一个大于1的回文,那么修改一个字符就能变成非回文
2,如果长度为奇数,那么中间的那个修改了还是回文。所以修改范围为0到中间的-1。


  • 瓦妹
  • 麻婆豆腐
    11
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
好像不对,说的是里面子数组也不能有回文


  • iwfya_kalorie
  • 毛蛋
    1
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
用栈处理类似于各种括号嵌套匹配问题


  • GTA小鸡
  • 吧主
    14
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
这个问题看上去很复杂,其实仔细想很简单
首先不能存在长度为2的回文串,即任意两个相邻字符不能相同,如果相邻字符相同则改掉其中一个。
接下来思考长度为3的回文串aba的情况。它满足任意两个相邻字符不相同,但是仍然是回文串。所以,还需要确保任意间隔一个字符的两个字符不能相同,即a[i]不能等于a[i+2]。如果相同,需要改掉其中一个。
那么需不需要接着判断长度为4的回文串呢?答案是不需要,因为很显然长度为4的回文串中包含长度为2的回文串。长度为5及以上的回文串同理。所以,我们只需要确保整个字符串中不存在长度为2或3的回文串即可。
接下来把这两种情况合并起来思考。由于长度3包含长度2,直接三个字符为一组判断。首先是abb型,需要破坏掉其中一个b。我们选择破坏掉第3位的b,因为如果破坏掉第二位的b,那么第三位的b还有机会和它后面的字符串构成回文,例如(abb)cb,如果破坏成(a*b)cb,那么bcb仍然是回文,还需要一次破坏;而如果破坏成(ab*)cb,那么字符*不可能与它后面的字符构成回文,第2位的b最多只能与第4位的字符构成b*b。然后是aab型,同理,我们应该破坏掉后面的那个a。然后是aba型,应该破坏掉第3位的a。最后是三位全相同的aaa型,很明显至少需要两次破坏,应该选择破坏掉第23位的a,这样第1位的a不可能构成任何长度的回文。
此时我们已经处理了所有情况,接下来只要将窗口向后滑动1字节处理下一组三字节数据即可。


  • 可泣的stone
  • 低能力者
    5
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
谢谢大佬的帮助。void m10d22p4(){
int T;
char S[2001];
scanf("%d", &T);
for(int i = 0;i< T;i++){
int num = 0;
scanf("%s", S);
if(S[1] == '\0')
{
printf("0\n");
break;
}
for(int j = 1;S[j] != '\0';j++){
if(S[j] == S[j - 1] && S[j - 1] != '#'){
S[j] = '#';
num++;
}
if(S[j+1] != '\0' && S[j - 1] == S[j + 1]){
S[j + 1] = '#';
num++;
}
}
printf("%d\n", num);
}
}


登录百度账号

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频!
  • 贴吧页面意见反馈
  • 违规贴吧举报反馈通道
  • 贴吧违规信息处理公示
  • 9回复贴,共1页
<<返回c语言吧
分享到:
©2025 Baidu贴吧协议|隐私政策|吧主制度|意见反馈|网络谣言警示