左旋字符串 - wtstengshen/blog-page GitHub Wiki

命题要求：左旋字符串的定义是，例如 123abcde 这个字符串，把123左旋后的结果是abcde123，时间复杂度为O(n),空间复杂度为O(1);

思路1. 暴力循环

1，首先把1放到临时变量tmp;

2，把23abcde分别向前移动一位，然后把1（tmp里的只）放到结尾;

3，一次循环23;

这种方式确实可以解决问题，最先想到的也是这个方法，具体代码不在描述，放弃；

思路2. 使用两个指针变量，移动因为要求空间复杂度为O(1)，所以可以考虑使用连个指针变量p1,p2;

p1指向123的1，p2指向a，然后对两个指针指向的内容进行替换，

例如；

1, p1-->1,p2-->a，p1和p2指向的内容互换位置，这时变为 a23 1bcde;然后 p1++,p2++;

2, p1-->2,p2-->b, 互换内容，变为 ab3 12cde;然后依次循环；

这个会有个问题，当循环到 abc 123de的时候，p1指向1，p2指向d,这个时候在像刚才那样循环，p2就溢出了，

这个时候，需要我们进行特殊处理：我们只需要把d和e向前循环替换就可以了

例如：

abc123de p1-->1,p2-->d,把d分别向前移动到p1指向的位置:

abc123de -> abc12d3e -> abc1d23e -> abcd123e

然后把e和d一样向前移动；

代码如下：

       /**
	 * 时间o(n)，空间o(1)， 左旋数组,省略参数校验
	 * 
	 * @param ch
	 * @param m
	 * @return
	 */
	public char[] leftRotate1(char[] ch, int m) {

		int size = ch.length;

		// 初始化两个指针
		int p1 = 0;
		int p2 = m;

		// 1,第一层循环，进行循环处理，向后校验元素,处理能够被整除的循环
		int k = (size - m) - size % m;

		while (k-- != 0) {
			this.swap(ch, p1, p2);
			p1++;
			p2++;
		}

		// 2,处理最后结尾，剩下的数据
		int n = size - p2;
		while (n-- != 0) {
			int i = p2;
			while (i > p1) {
				this.swap(ch, i, i - 1);
				i--;
			}
			p1++;
			p2++;
		}

		return ch;
	}
	
	/**
	 * 交换位置
	 * 
	 * @param ch
	 * @param i
	 * @param j
	 */
	private void swap(char[] ch, int i, int j) {
		char tmp = ch[i];
		ch[i] = ch[j];
		ch[j] = tmp;
	}

思路3.翻转方法

还是刚才的例子：把123abcde 分成两个部分：123 和 abcde

1，把123进行翻转，结果是 321 ;

2，把abcde进行翻转，结果是edcba ；

3，然后把两个部分组合，进行翻转，既 3 2 1 e d c b a 翻转为a b c d e 1 2 3;

其中，在《编程珠玑》上也有这样一个类似的问题的描述

代码如下：

       /**
	 * 时间o(n)，空间o(1)，把字符串分成两组，分别进行翻转，然后对整体进行翻转
	 * 
	 * @param ch
	 * @param m
	 * @return
	 */
	public char[] leftRotate2(char[] ch, int m) {

		int size = ch.length;

		this.invert(ch, 0, m - 1);
		this.invert(ch, m, size - 1);
		this.invert(ch, 0, size - 1);

		return ch;
	}

	/**
	 * 翻转数组
	 * 
	 * @param ch
	 * @param begin
	 * @param end
	 */
	private void invert(char[] ch, int begin, int end) {

		while (begin != end) {
			this.swap(ch, begin, end);
			begin++;
			end--;
		}
	}

本次博客总结左旋字符串翻转的几个常用的方法，欢迎拍砖；

作者 @悠悠小竹子

博客 iocoding