首页 > 试题广场 >

字符反转

[编程题]字符反转

热度指数：331 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现在有一个长度为n的字符串，进行循环右移k位的操作，少对这个字符串进行几次区间反转操作能实现循环右移k位呢。反转操作指字符串某一区间 $\left[ L,R \right]$ 内的字符反转，例如“123456”，区间[3,5]进行反转字符串变为“125436”。假设字符串每一位都不同。给定一个字符串长度n和循环右移次数k，求最少反转次数。

示例1

输入

3,4

输出

说明

例如字符串为123 那么循环右移4次变为312，用区间反转操作代替的话，就是先对[1,3]反转得到321，再对[2,3]反转得到312，最少进行两次反转操作

备注:

算法知识视频讲解

牛客100843934号

有谁像我一样看不懂题目的么？

发表于 2021-02-25 17:15:14 回复(0)

牛客516598323号

分为两部分，循环移出的和没有移除的。至多需要3步。第一步全部反转。第二步移出部分反转。第三步未移出部分反转。

特殊情况：字符串太短（1，2）。移出字符太少（0，1，2）。

class Solution:
    def solve(self, n, k):
        k = k % n
        if k == 0:
            return 0
        elif k == 1 or k == 2 or k == n-1 or k == n-2:
            if n == 2:
                return 1
            return 2
        else:
            return 3

编辑于 2020-09-05 19:37:44 回复(0)