首页 > 试题广场 >

翻转01

[编程题]翻转01
  • 热度指数：546 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\,\,\,\,\,\,\,\,\,\,给定一个长度为  且仅由 '\tt 0' 、 '\tt 1' 两种字符构成的字符串  。每次操作你都可以选择字符串  的任意一个字符，并将其反置。
\,\,\,\,\,\,\,\,\,\,询问经过恰好  次操作后，字符串  是否为一个回文字符串。

\,\,\,\,\,\,\,\,\,\,若当前字符为 '\tt 0' ，反置后为 '\tt 1' ；若当前字符为 '\tt 1' ，反置后为 '\tt 0' 。
\,\,\,\,\,\,\,\,\,\,一个字符串被称作回文字符串，当且仅当这个字符串从左往右读和从右往左读都是相同的。

输入描述:
\,\,\,\,\,\,\,\,\,\,每个测试文件均包含多组测试数据。第一行输入一个整数 T\ (1\le T\le 100) 代表数据组数，每组测试数据描述如下：
\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n,k \left(1 \le n \le 1000;\ 0 \le k \le n \right)
\,\,\,\,\,\,\,\,\,\,第二行输入一个长度为  且仅由 '\tt 0' 、 '\tt 1' 两种字符构成的字符串  。


输出描述:
\,\,\,\,\,\,\,\,\,\,对于每一组测试数据，如果经过恰好  次操作后，字符串  可以成为一个回文字符串，在一行上输出 \rm YES ；否则，直接输出 \rm NO 。
示例1

输入

3
6 1
101100
6 2
101100
6 3
101100

输出

YES
NO
YES

说明

\,\,\,\,\,\,\,\,\,\,对于第一组测试数据，可得到的回文串为 "\tt101101" 、"\tt 001100" ；
\,\,\,\,\,\,\,\,\,\,对于第二组测试数据，无论如何都不能使得其变成回文串；
\,\,\,\,\,\,\,\,\,\,对于第三组测试数据，由于其包含第一组测试数据，因此也可以变成回文串。
示例2

输入

4
5 4
10101
4 3
1001
6 4
100100
6 5
000001

输出

YES
NO
YES
YES

备注:
\,\,\,\,\,\,\,\,\,\,在几乎全部的情况下，\sf PyPy 的运行速度优于 \sf Python ，我们建议您选择对应版本的 \sf PyPy 进行提交、而不是 \sf Python 。
算法知识视频讲解
添加回答
Python
Sensea头像 Sensea
t = int(input())
res = []
for _ in range(t):
    n, k = map(int, input().split())
    s = input().strip()
    # 二分查找，找到不对称的位置
    cnt = 0
    left, right = 0, n - 1
    while left < right:
        if s[left] != s[right]:
            cnt += 1
        left += 1
        right -= 1
    if k < cnt:
        res.append("NO")
    else:
        if n % 2 == 1:  # 如果长度是奇数，恒成立
            res.append("YES")
        else:
            if (k - cnt) % 2 == 0:  # 如果长度是偶数，恒成立(k - cnt)为偶数时成立
                res.append("YES")
            else:
                res.append("NO")  # 否则不成立
for ans in res:
    print(ans)

发表于 今天 11:46:26 回复(0)
提交观点

问题信息

字符串 饿了么 双指针
难度：
1条回答 126浏览

热门推荐

相关试题

翻转01

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号