【程序员编程艺术】学习记录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] = s[i];
    s[n-1] = t;
}

void leftshift(char *s, int n, int m)
{
    while(m--)
        leftshiftone(s,n);
}

思路二、指针翻转法

参考代码:

#include <iostream>
#include <string>
using namespace std;

void rotate(string &str, int m)
{
    if(str.length() == 0 || m <= 0)
        return;

    int n = str.length();
    //处理m>n的情况
    if(m % n <= 0)
        return;

    int p1 = 0,p2 = m;
    int k = (n - m) - n % m;
    //交换p1、p2指向的元素,之后移动p1,p2
    while(k --)
    {
        swap(str[p1], str[p2]);
        p1++;
        p2++;
    }

    //处理尾部,r为尾部左移次数
    int r = n - p2;
    while(r--)
    {
        int i = p2;
        while(i > p1)
        {
            swap(str[i], str[i-1]);
            i--;
        }

        p2++;
        p1++;
    }
}

int main()
{
    string ch = "abcdefghijk";
    rotate(ch, 3);
    cout << ch << endl;
    return 0;
}

swap交换函数

思路三、

参考代码:

#include <iostream>
#include <string>
using namespace std;

void rotate(string &str, int m)
{
    if(str.length() == 0 || m < 0)
        return;

    //初始化p1p2
    int p1 = 0,p2 = m;
    int n = str.length();

    //处理m大于n
    if(m%n == 0)
        return;

    //循环至p2到达字符串的末尾
    while(true)
    {
        swap(str[p1],str[p2]);
        p1++;

        if(p2 < n+1)
            p2++;
        else
            break;
    }

    //处理尾部,r为尾部循环左移动的次数
    int r = m - n%m;
    while(r--)
    {
        int i = p1;
        char temp = str[p1];
        while(i < p2)
        {
            str[i] = str[i+1];
            i++;
        }
        str[p2] = temp;
    }
}

思路4、上述都是假设m<n,我们现在考虑m为负数和m大于n的可能

参考代码:

#include <iostream>
#include <string>
using namespace std;

//const int positiveMod(m,n) = (m % n + n) % n; //无效
//#define positiveMod(m,n) ((m) % (n) + (n)) % (n) //宏定义切记这里不能加上;号
inline int positiveMod(int m, int n) //内联
{
    return ((m) % (n) + (n)) % (n);
}
//左旋转字符串str,如果m为负数,则有右旋转
void rotate(string &str, int m)
{
    if(str.length() == 0)
        return;

    //初始化
    int n = str.length();
    int p1 = 0,p2 = m;

    //处理m大于n以及m为负数的情况,positiveMod
    m = positiveMod(m,n);
    if(m == 0)
        return;

    int round;

    //p2当前所指和之后的m-1个字母共m个字母,就可以和p2前面的m个字母交换
    while(p2 + m - 1 < n)
    {
        round = m;
        while(round--)
        {
            swap(str[p1], str[p2]);
            p1++;
            p2++;
        }
    }

    //剩下的不足m个字母一个一个交换
    int r = n - p2;
    while(r--)
    {
        int i = p2;
        while(i > p1)
        {
            swap(str[i], str[i-1]);
            i--;
        }
        p2++;
        p1++;
    }
}

//测试
int main()
{
    cout << ((-15)%7 + 7)%7 << endl;
    cout << (-15)%7 << endl;
    string ch = "abcdefg";
    int len = ch.length();

    for(int m = -2*len; m <= len * 2; m++)
    {
        //由于传给rotate的是string的引用,所以每次调用都用一个新字符
        string s = "abcdefg";
        rotate(s,m);
        cout << positiveMod(m,len) << ": " << s << endl;
    }
    return 0;
}

思路5、递归转换法

参考代码:

#include <iostream>
using namespace std;

void rotate(string &str, int n, int m, int head, int tail, bool flag)
{
    //n表示待处理的字符串长度,m为待处理部分的旋转长度
    //head:待处理部分的头指针 tail待处理部分的尾指针
    //flag = true表示左旋,否则右旋

    //返回条件
    if(head == tail || m <= 0)
        return;

    if(flag == true)
    {
        int p1 = head;
        int p2 = head + m;

        int k = (n-m) - n % m; //p1,p2移动距离,向右

        for(int i = 0; i < k; i++,p1++,p2++)
            swap(str[p1], str[p2]);

        //结束左旋进入右旋
        rotate(str, n-k, n %m, p1, tail, false);
    }
    else
    {
        int p1 = tail;
        int p2 = tail - m;

        //p1,p2移动距离
        int k = (n-m)-n%m;

        for(int i = 0; i < k; i++, p1--,p2--)
            swap(str[p1],str[p2]);

        rotate(str,n-k,n % m, head, p1, true);
    }
}

int main()
{
    int i = 3;
    string str = "abcdefghijk";
    int len = str.length();
    rotate(str,len, i%len ,0,len-1,true);
    cout << str.c_str() << endl;//转化成字符数组的形式输出
    return 0;
}

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

时间: 07-16

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

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

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

【程序员编程艺术】学习记录3:字符串包含问题

[程序员编程艺术]学习记录3:字符串包含问题 题目: 假设这有一个各种字母组成的字符串A,和另外一个字符串B,字符串里B的字母数相对少一些.什么方法能最快的查出所有小字符串B 里的字母在大字符串A里都有? <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

程序员编程技术学习笔记——左旋转字符串

程序员编程技术学习笔记--左旋转字符串 1.    题目描述 给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串"abcdef"前面的2个字符'a'和'b'移动到字符串的尾部,使得原字符串变成字符串"cdefab".请写一个函数完成此功能,要求对长度为n的字符串操作的时间复杂度为 O(n),空间复杂度为 O(1). 2.    解法1:暴力左移 这个解法简单粗暴易想!你不是要以为k个字符吗,我先移动一位,然后把移动一位的函数运行k次就好啦~~

程序员编程艺术

本书来自一位很有奉献精神的大神July,希望有一天能够看到本书出版. 对作者致以最真诚的感谢! 作者博客 作者微博 本书GitHub地址 CSDN下载链接 百度云盘下载链接 本书目录: 程序员编程艺术第一~三十七章集锦.............................................1 前言........................................................................1 目录................

python代码 程序员编程艺术 1.1

<程序员编程艺术:面试和算法心得>http://taop.marchtea.com/ https://github.com/julycoding/The-Art-Of-Programming-By-July/tree/master/ebook/code/python 1.1 旋转字符串 1: def simpleShift(str, n): 2: tmpStr = str[n:] + str[:n] 3: return tmpStr 4:   5: def LeftShiftOne(str):

程序员编程技术学习笔记——字符串包含

程序员编程技术学习笔记--字符串包含 1.题目描述 给定两个分别由字母组成的字符串A和字符串B,字符串B的长度比字符串A短.请问,如何最快地判断字符串B中所有字母是否都在字符串A里?为了简单起见,我们规定输入的字符串只包含大写英文字母,请实现函数boolStringContains(string &A, string &B) 比如,如果是下面两个字符串: String 1:ABCD String 2:BAD 答案是true,即String2里的字母在String1里也都有,或者说Strin

python代码 程序员编程艺术 2.1

首先一般考虑"万能的"暴力穷举(递归.回溯).但因为穷举时间复杂度通常过高,所以需要考虑更好的方法,如分治法(通过分而治之,然后归并),以及空间换时间(如活用哈希表). 此外,选择合适的数据结构可以显著提升效率,如寻找最小的k个数中,用堆代替数组. 再有,如果题目允许排序,则可以考虑排序.比如,寻找和为定值的两个数中,先排序,然后用前后两个指针往中间扫.而如果如果已经排好序了(如杨氏矩阵查找中),则想想有无必要二分.但是,如果题目不允许排序呢?这个时候,我们可以考虑不改变数列顺序的贪心

Mac开发利器之程序员编辑器MacVim学习总结

Emacs和Vim都是程序员专用编辑器,Emacs被称为神的编辑器,Vim则是编辑器之神.至于两者到底哪个更好用,网络上两大派系至今还争论不休.不过,相比之下,Emacs更加复杂,已经不能算是一个编辑器了,有人这么说:Emacs是伪装成编辑器的操作系统.与之相反,Vim的定位很明确,就是要做一个强大的编辑器.由于笔者精力有限,决定还是选择自己认为相对简单点的Vim来学习.因此,笔者将会在本文跟大家介绍Mac下Vim的安装以及简单使用.          首先,Mac系统默认已经安装了Vim.打开

程序员编程语录

程序员编程语录 1. 一个好的程序员是那种过单行线马路都要往两边看的人.(Doug Linder) 2. 程序有问题时不要担心.如果所有东西都没问题,你就失业了.(软件工程的 Mosher 定律) 3. 程序员的麻烦在于,你无法弄清他在捣腾什么,当你最终弄明白时,也许已经晚了.(超级计算机之父 Seymour Cray) 4. 我想大部分人都知道通常一个程序员会具有的美德.当然了,有三种:懒惰,暴躁,傲慢.(Perl 语言发明者 Larry Wall) 5. 编程时要保持这种心态:就好象将来要维