[日常] 算法-旋转字符串-三步翻转法

题目描述

给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串“abcdef”前面的2个字符‘a‘和‘b‘移动到字符串的尾部,使得原字符串变成字符串“cdefab”。请写一个函数完成此功能,要求对长度为n的字符串操作的时间复杂度为 O(n),空间复杂度为 O(1)。

分析与解法

解法二:三步反转法

对于这个问题,换一个角度思考一下。

将一个字符串分成X和Y两个部分,在每部分字符串上定义反转操作,如X^T,即把X的所有字符反转(如,X="abc",那么X^T="cba"),那么就得到下面的结论:(X^TY^T)^T=YX,显然就解决了字符串的反转问题。

例如,字符串 abcdef ,若要让def翻转到abc的前头,只要按照下述3个步骤操作即可:

  1. 首先将原字符串分为两个部分,即X:abc,Y:def;
  2. 将X反转,X->X^T,即得:abc->cba;将Y反转,Y->Y^T,即得:def->fed。
  3. 反转上述步骤得到的结果字符串X^TY^T,即反转字符串cbafed的两部分(cba和fed)给予反转,cbafed得到defabc,形式化表示为(X^TY^T)^T=YX,这就实现了整个反转。

c语言版:

#include <stdio.h>
#include <string.h>
void ReverseString(char* s,int from,int to)
{
    while (from < to)
    {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}
void LeftRotateString(char* s,int n,int m)
{
    m %= n;               //若要左移动大于n位,那么和%n 是等价的
    ReverseString(s, 0, m - 1); //反转[0..m - 1],套用到上面举的例子中,就是X->X^T,即 abc->cba
    ReverseString(s, m, n - 1); //反转[m..n - 1],例如Y->Y^T,即 def->fed
    ReverseString(s, 0, n - 1); //反转[0..n - 1],即如整个反转,(X^TY^T)^T=YX,即 cbafed->defabc。
}
int main(){

        char a[]="hello world";
        LeftRotateString(a,strlen(a),2);
        printf("%s\n",a);
}

go语言版:

package main
import(
        "fmt"
)
func ReverseString(s []byte,from int,to int){
        for{
                t:=s[from]
                s[from]=s[to]
                s[to]=t
                from++
                to--
                if from>to{
                        break
                }

        }
}
func LeftRotateString(s []byte,n int,m int){
        m%=n
        ReverseString(s,0,m-1)
        ReverseString(s,m,n-1)
        ReverseString(s,0,n-1)
}

func main(){

        a:=[]byte("hello world")
        LeftRotateString(a,len(a),2)
        fmt.Println(string(a))

}

php版:

<?php
function ReverseString(&$str,$from,$to){
        while($from<$to){
                $t=$str[$from];
                $str[$from++]=$str[$to];
                $str[$to--]=$t;
        }
}
function LeftRotateString(&$str,$n,$m){
        $m%=$n;//如果转换前几个字符的长度比字符串长度大
        ReverseString($str,0,$m-1);
        ReverseString($str,$m,$n-1);
        ReverseString($str,0,$n-1);
}
$a="hello world";
LeftRotateString($a,strlen($a),2);
echo $a."\n";

  

  

  

原文地址:https://www.cnblogs.com/taoshihan/p/9156487.html

时间: 06-06

[日常] 算法-旋转字符串-三步翻转法的相关文章

【程序员编程艺术】学习记录1:左旋转字符串之指针翻转法

[程序员编程艺术]学习记录1:左旋转字符串之指针翻转法 题目:左旋转字符串 定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部,如把字符串abcdef左旋转2位得到字符串cdefab.请实现字符串左旋转的函数,要求对长度为n的字符串操作的时间复杂度为O(n),空间复杂度为O(n) 思路一.暴力移位法 //暴力移位法 void leftshiftone(char *s, int n) { char t = s[0]; for(int i = 1;i < n; i++) s[i-1]

43左旋转字符串+三步反转法

题目描述 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果.对于一个给定的字符序列S,请你把其循环左移K位后的序列输出.例如,字符序列S="abcXYZdef",要求输出循环左移3位后的结果,即"XYZdefabc".是不是很简单?OK,搞定它! 思路:所有的反转题目尤其是字符串,都记得使用三步反转法.旋转类问题,比如字符串反转. 使用三步反转法: 1)使用O(n)的时间,直接遍历找到反转的中间元素: 2)将中间

[日常] 算法-旋转字符串-暴力移位法

题目描述 给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串"abcdef"前面的2个字符'a'和'b'移动到字符串的尾部,使得原字符串变成字符串"cdefab".请写一个函数完成此功能,要求对长度为n的字符串操作的时间复杂度为 O(n),空间复杂度为 O(1). 分析与解法 解法一:暴力移位法 初看此题,可能最先想到的方法是按照题目所要求的,把需要移动的字符一个一个地移动到字符串的尾部,如此我们可以实现一个函数LeftShiftOne(ch

小技巧----“三步翻转法”

例:实现字符串左移函数,比如"abcdefghi"循环左移3位就是"defghiabc". #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<string.h> void revers(char *left,char *right) //翻转函数,left代表起始位置,right代表结束位置 { assert(left); assert(r

三步翻转法

class Solution { public void reverse(char[] ch, int l ,int r) { for ( ; l<r; l++,r--){ char t = ch[l]; ch[l] = ch[r]; ch[r] = t; } } public void fun(String str, int n, int m){ if(str == null || str.length()==0) return; m %= n; char[] ch = str.toCharA

【算法】字符串的最小表示法

字符串的最小表示法,就是对于一个字符串,可以将它的最后一位放到第一位来,依次类推,一共有n种变形,n为字符串长度 例如: s="00ab" 变形有(省略引号)b00a ab00 0ab0 一共4种 那么找到其中字典序最小的一个,用的算法便是这个. 定义三个指针,i,j,k 初始i=0;j=1;k=0 首先,如果s[i]<s[j]那么很明显j++ 如果s[i]>s[j]那么也很明显i=j++ 省下的就是如果s[i]==s[j]的时候. 这时候有一个性质就是在i和j之间的所有的

【程序员编程艺术】学习记录2:左旋转字符串之循环移位法

[程序员编程艺术]学习记录2:左旋转字符串之循环移位法 GCD算法:(辗转相除法/欧几里得算法) gcd是求最大公约数的算法,作为TAOCP第一个算法 gcd算法流程: 首先给定两个整数m,n(m大于等于n)如果小于则直接交换再处理 ①求余数 r=m%n ②假如r=0,算法结束,n即为所求 否则,重新令m <- n, n <-r 之后循环 <<<<<<<<<<<<<<<<<<<&l

字符串左旋右旋——三步旋转法和移相法

题目:实现一个函数,可以左旋字符串中的k个字符. AABCD左旋一个字符得到ABCDA AABCD左旋两个字符得到BCDAA 方法一:三步旋转法 左旋程序思路:首先根据画图得知左旋后的结果,然后在分析实现的简约步骤: 第一步:字符串全逆序: 第二步:左边的字符串逆序: 第三步:右边的字符串逆序: 举例:左旋K=1个字符: 首先是头文件和主函数部分: #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<windows.h

编程算法 - 左旋转字符串 代码(C)

左旋转字符串 代码(C) 本文地址: http://blog.csdn.net/caroline_wendy 题目: 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部. 请定义一个函数实现字符串左旋转操作的功能. 编程珠玑, 首先翻转前部分, 再翻转后部分, 最后全部翻转. 代码: /* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*/ #include <stdio