关于字符串旋转的问题

如:对于字符串”abcdef”,“旋转度”为2,结果为”cdefab”

1:

将字符串中除首位外的字符依次前移,将首位字符移至末位;
每次旋转一个字符,如此重复。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public String LeftShift1(String s, int c) {
char[] ss = s.toCharArray();
for(int j = 0; j < c; j++){
char temp = ss[0];
// 字符依次前移
for(int i = 1; i < ss.length; i++)
ss[i - 1] = ss[i];
// 首位字符移至末位
ss[ss.length - 1] = temp;
}
return new String(ss);
}
2:

对于字符串”abcdef”,旋转部分R为”ab”,保持部分M为”cdef”。
定义S^表示字符串S的逆序字符串,可以看到旋转结果为M + R:

1
M + R = (R^ + M^)^

得到逆序字符串:

1
2
3
4
5
6
7
8
9
10
11
12
public String ReverseString(String s, int from, int to) {
char[] ss = s.toCharArray();
// 定义from、to两个标志位分别指向串首、串尾
while(from < to) {
char c = ss[from];
ss[from++] = ss[to];
ss[to--] = c;
}
return new String(ss);
}

控制字符串的旋转范围:

1
2
3
public static String LeftShift2(String s, int c) {
return ReverseString(ReverseString(ReverseString(s, 0, c - 1), c, s.length() - 1), 0, s.length() - 1);
}

关于字符串旋转的类似问题

旋转链表

如:对于链表1 -> 2 -> 3 -> 4 -> 5 -> 6,旋转度为2,结果为3 -> 4 -> 5 -> 6 -> 1 -> 2

定义一个简化的链表类,包括构建链表、旋转链表和输出链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class SimplifiedLink<E> {
// 内部结点类
class Node<E> {
E element;
Node<E> next;
public Node(E e) {
element = e;
}
}
private Node<E> head;
private Node<E> tail;
public SimplifiedLink() {
}
// 由数组构建链表
public SimplifiedLink(E[] array) {
// 插入头结点
Node<E> node = new Node<E>(array[0]);
head = tail = node;
tail.next = null;
// 依次由尾部插入其他结点
for(int i = 1; i < array.length; i++) {
tail.next = new Node<E>(array[i]);
tail = tail.next;
tail.next = null;
}
}
public String print() {
Node<E> current = head;
StringBuffer sb = new StringBuffer();
while(current != null) {
sb.append(current.element).append(" ");
current = current.next;
}
return sb.toString();
}
/*
* 使尾结点的next指向头结点
* 遍历链表,在指定位区分头结点、尾结点
*/
public void leftShift(int c) {
tail.next = head;
Node<E> current = head;
while(c > 1) {
current = current.next;
c--;
}
head = current.next;
tail = current;
tail.next = null;
}
}

链表操作中均使用

1
tail.next = null;

来标识尾结点

测试旋转链表:
1
2
3
4
5
6
7
8
9
10
public class TestLink {
public static void main(String[] args) {
Integer[] array = {1, 2, 3, 4 , 5, 6};
Linked<Integer> list = new Linked<Integer>(array);
System.out.println(list.print());
list.leftShift(2);
System.out.println(list.print());
}
}

由于使用了泛型,这里使用Integer包装类来定义数组。

输出结果为:

1
2
3
4
#初始化
1 2 3 4 5 6
#旋转后
3 4 5 6 1 2
旋转语句

如:”I am a student.”,旋转结果为”student. a am I”

以空格区分,逐次将单词由尾部旋转至首部,需要注意的是控制旋转范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public String LeftShift3(String s) {
// 定义b、e标识旋转范围
int b = 0;
int e = s.length() - 1;
// 定义e - i标识“旋转度”
int i = e;
while(s.charAt(i) != ' ') {
i--;
// 对于单个单词构成的语句,无空格用于区分
if(i < 0)
return s;
}
/*
* 判断旋转是否完成
* 旋转起点b标识的已完成旋转部分的长度加上下一次待旋转部分的长度等于总长度
* 则下次旋转即为最后一次旋转
*/
while(b + e - i != s.length()) {
s = LeftShift3Help(s, b, e - i);
b = b + e - i;
// 每次旋转单词结束后,旋转一个空格
s = LeftShift3Help(s, b, 1);
b = b + 1;
i = e;
while(s.charAt(i) != ' ')
i--;
}
return s;
}

控制旋转范围:

1
2
3
public String LeftShift3Help(String s, int begin, int end) {
return ReverseString(ReverseString(ReverseString(s, begin, s.length() - 1 - end), s.length() - end, s.length() - 1), begin, s.length() - 1);
}

参考资料

1.1 旋转字符串