问题六
字符串左(右)移问题
问题描述：
将一个字符串按照要求左移或者右移
问题举例：
将abcdef左移2位的结果就是cdefab，相当于第二位之后的cdef向左边挤过去，把ab向后移动。
思路分析：
这个问题有多种方法，可以采用比较暴力的解法，将需要左移的数据进行存储，并将其他数据依次移动，这个思路比较简单直接，但是空间复杂度比较高，适用于用空间换时间的情景。另外一种方法就是利用技巧进行观察，我们可以发现如下规律，分别将移位点前和移位点后的元素翻转，最后将整体翻转可以达到同样的效果，并且空间复杂度为O(1)。比如abcdef，将其左移两位，我们按照上面的说法进行实验，首先翻转ab变成bacdef，再翻转cdef变成bafedc，此时再对整个字符串进行翻转就能得到cdefab。
代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public class StringLeftShift {
private String reverse(String s,int from,int to){
char[] sArr = s.toCharArray();
while(from<to){
char temp = sArr[from];
sArr[from++] = sArr[to];
sArr[to--] = temp;
}
return String.valueOf(sArr);
}
private String sls(String s,int shift){
return reverse(reverse(reverse(s,0,shift-1),shift,s.length()-1),0,s.length()-1);
}
public static void main(String[] args) {
StringLeftShift SLS = new StringLeftShift();
System.out.println(SLS.sls("abcdef",2));;
}
}
代码分析：
上面的代码主要是根据之前的描述中所提及的思路进行的编写，只包括了一个翻转函数和一个主逻辑函数，其中主逻辑中多次使用了翻转函数。
问题七
字符串的全排列问题(不含有相同字符)
问题描述：
求解给定字符串的全排列
问题举例：
字符串abc的全排列包括bca、acb、abc、cba、bac、cab
思路分析：
这个问题实际上是一个占位的问题，就是a在bc和cb中如何进行插入操作，可以手工演算出abc、bac、bca以及acb、cab和cba，这样其实就已经得到了最终的全部结果。我们把问题规模扩大到4个字符，以abcd为例，首先考虑的还是最小范围内的字符，此处为cd和dc，然后计算的是b插入后的情况，共有6种，bcd、cbd、cdb以及bcd、dbc和dcb，然后继续考虑a插入的情况，共有6个小规模字符，每个字符都有四个位置可以插入，所以共有24种情况。
代码实现：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
41public class FullPermutationWithNoSameChar {
private static Set<String> fullPer(char[] A, int p, int r) {
if (r - p <= 1) {
char[] cs = new char[2];
cs[0] = A[p];
cs[1] = A[r];
Set<String> set = new HashSet<>();
set.add(new String(cs));
cs[0] = A[r];
cs[1] = A[p];
set.add(new String(cs));
return set;
}
return insertChar(A[p], fullPer(A, p + 1, r));
}
private static Set<String> insertChar(char c, Set<String> setIn) {
Set<String> set = new HashSet<>();
for (String s : setIn) {
char[] cs = s.toCharArray();
int len = cs.length + 1;
char[] result = new char[len];
for (int i = 0; i < len; i++) {
result[i] = c;
for (int j = 0, k = 0; k < len - 1; j++, k++) {
if (j == i)
j++;
result[j] = cs[k];
}
set.add(new String(result));
}
}
return set;
}
public static void main(String[] args) {
char[] A = "abc".toCharArray();
Set<String> set = fullPer(A, 0, A.length - 1);
System.out.println("set:" + set);
}
}
代码分析：
上面的代码分成了两个模块，一个是全排列，一个是插入字符，全排列模块的作用就是当问题规模缩小到两个字符之间的时候就进行简单组合，然后将这个两个长度的字符串抛给插入字符的函数，用于使用剩下的那个字符进行插入操作。在插入字符函数中使用了一个判断，就是1
2if (j == i)
j++;
因为i代表了插入字符所在的位置，所以如果发生冲突，则将代表新生成字符串的j向后移动，比如以a开始插入，此时i=0，j的初始也是0，此时result[j]如果还是0的话就会把a给覆盖掉，所以j+1以避免这种情况的发生。
问题八
字符串的全排列问题(含有相同字符)
问题描述：
求解含有重复元素的字符串的全排列
问题举例：
字符串abb的全排列包括abb、bab、bba
思路分析：
如果继续按照上面那种不含有重复字符的做法，就会出现两次或者多次重复，因为之前的操作只是单纯插入，没有对带插入的字符串进行识别，比如将第二个b插入ab中，其插入第二个位置和第三个位置在运算中是不同的，但是在结果看来是相同，所以需要进行判断，以免产生重复字符。我们需要保证的是当第i个字符和第j个字符进行交换时，要求[i,j)中没有与第j个字符相等的字符，比如在bab中，如果发现第一个b和第二个b需要交换则跳过，因为两个在数值上相同。
代码实现：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
38public class FullPermutationWithSameChar {
private boolean isSwap(char[] array,int begin,int end){
for (int i=begin;i<end;i++){
if(array[i]==array[end])
return false;
}
return true;
}
private void perm(char[] array,int i,int n){
int j;
if (i==n){
System.out.println(array);
}else {
for (j=i;j<=n;j++){
if(isSwap(array,i,j)){
System.out.println("array:"+String.valueOf(array)+",i1="+i+",j1="+j);
swap(array,i,j);
perm(array,i+1,n);
System.out.println("array:"+String.valueOf(array)+",i2="+i+",j2="+j);
swap(array,i,j);
}
}
}
}
private void swap(char[] array,int i,int j){
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
FullPermutationWithSameChar fpwsc = new FullPermutationWithSameChar();
char[] array = {'a','b','b'};
fpwsc.perm(array,0,array.length-1);
}
}
代码分析：
在上面的代码中包含了三个函数，一个isSwap函数，它是用于判断在需要进行交换的这个区间内，是否存在与array[end]字符相同的字符，如果存在则跳过此次交换，因为一旦有两个相同字符则交换无意义。一个swap函数，就是进行字符交换。还有一个主逻辑函数，i代表了字符的起始值，也就是0，n代表的是长度-1，当i==n时代表达到了字符串的边界，则输出，否则就进入循环，此处也是这个程序比较复杂的地方，因为它涉及到了递归。有关递归问题的分析，比较好的方法就是将关键数据进行输出然后分析每一步的运行方式。
上图中的i1、j1和i2、j2分别代表了在对perm进行递归前后i和j数据的变化。我们分块进行分析，首先abb输出之前的原始数组是abb，i1=0，j1=0，则在isSwap中无法进入循环，所以return true，然后进行递归，此时i1变成1、j1变成1,在isSwap中依然无法进入循环，所以return true，然后继续递归，此时i1=2，在perm中进行判断的时候i==n，所以直接进行输出，所以输出的第一个字符串是abb。输出abb之后，之前递归进入的第二层perm函数(我们称未进入递归前的函数是顶层函数，进入后的递归函数从第一层开始计算)就自行退出，然后运行至对i2和j2进行计算，此时函数还处在第一层递归中，所以i2=1，j2=1。运行结束后，继续交换array[i]和array[j]。此时第一层的perm函数运行结束，回到了顶层的perm函数，请注意，此时i2和j2的值还是原来顶层的值，也就是恢复到了最开始的0和0，这一点是要注意的细节，然后第一次循环结束。
第二轮循环开始，此时变化的只是j的值，j变为1，而i依旧为0。继续按上述的思路分析，当i=0，j=1时，array[0]=a，array[b]=b，两者不同，所以i+1后不小于j，故return true，然后就是对array[0]和array[1]进行交换，也就形成了字符串bab，然后i1+1(此时进入第一层递归)，i1==j1，所以return true，然后由于i==j，所以等效于不交换，继续进入了第二层递归，此时i继续加1，与n相等，故输出了bab，然后跳出第二层递归，所以此时i2=1，j2=1，然后此次循环结束，此时i2的值就是i的值，也就是第三次循环中，i的起始值就是1，而j已经增长至2。所以进入函数就进行交换，这样使得字符串变成bba，然后i就由于加1，在第一层递归中完成了输出bba的操作，之后就是跳出这层递归，输出了i2=1，j2=2，最后跳出的那层递归是第二次循环当中的递归，而不是第三次循环当中的，请注意这一点。(从上面的程序运行过程也能看出进和出的时间)，由于递归的方式与栈类似，所以如果没有完全出栈就代表依旧在栈中。这里就有一个疑问的地方，那就是为什么在递归前和后都要进行swap的操作，在递归前进行swap可以看做是对字符进行排序，然后方便递归时输出，那么递归之后的swap作用在什么地方呢，那个swap的作用在于在退栈的时候还原原来的字符串，比如进去的时候是abb，最后退栈的时候也应该是abb，这样的作用是进行检查，因为最初abb进去的时候i=0，j=0，检测范围较小，但是到了最后能检查的范围成了0-arr.length-1，能够避免错误的发生。
问题九：
字符串的全排列问题(字典顺序,递归以及非递归)
问题描述：
求解给点字符串的全排列，其中全排列的顺序应以字典顺序给出。所谓字典顺序，就是从小到大排列。
问题举例：
abc的下一个序列是acb，之后是bac。
思路分析：
我们以43521作为例子进行说明，43521的下一个序列应该是45123，这种顺序才满足字典序，那么如何得到45123呢。
1、 自右向左进行扫描，找出第一个比右边数字小的数字，这里是3。
2、 然后在该数字之后的数字中，找出比3大的数中最小的一个数字，这里是5。
3、 将5和3进行交换得到45321。
4、 然后将从3开始将其以及之后的数字翻转得到45123，结束。
代码实现：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
61
62
63
64
65
66
67
68
69
70
71
72public class FullPermutationWithDicSort {
private char[] initialSort(char[] c){
for (int i=0;i<c.length;i++){
for (int j=0;j<c.length-i-1;j++){
if(c[j]>c[j+1]){
char temp = c[j];
c[j] = c[j+1];
c[j+1] = temp;
}
}
}
return c;
}
private boolean isDescend(char[] c){
boolean flag = true;
for (int i=0;i<c.length-1;i++){
if(c[i]<c[i+1])
return false;
}
return flag;
}
private char[] findNext(char[] c){
System.out.println(c);
if (isDescend(c))
return c;
if (c.length<2)
return c;
int lessThanRightIndex = c.length-2;
int smallestBiggerIndex = 0;
char base = 'z';
/*第一步：找到第一个小于右边值的字符，并记录其位置*/
for (int i=c.length-2;i>=0;i--){
if(c[i]<c[i+1]){
lessThanRightIndex = i;
break;
}
}
/*第二步：找到第一个小于右边值的字符之后的字符中比它大，但是比其余要小的字符*/
for (int j = lessThanRightIndex;j<c.length;j++){
if(c[j]>c[lessThanRightIndex]&&c[j]<=base){
smallestBiggerIndex = j;
base = c[j];
}
}
/*第三步：交换，第一个小于右边值的字符和之后比它大的最小字符*/
swap(c,lessThanRightIndex,smallestBiggerIndex);
/*第四步：翻转第一个小于右边值字符之后的字符*/
reverse(c,lessThanRightIndex+1,c.length-1);
return findNext(c);
}
private void swap(char[] c,int i,int j){
char temp = c[i];
c[i] = c[j];
c[j] = temp;
}
private char[] reverse(char[] c,int i,int j){
while(i<j)
swap(c,i++,j--);
return c;
}
public static void main(String[] args) {
FullPermutationWithDicSort fpwnr = new FullPermutationWithDicSort();
char[] c = new char[]{'1','2','2','3'};
c = fpwnr.initialSort(c);
fpwnr.findNext(c);
}
}
代码分析：
这次的代码从上到下进行分析，最开始的方法initialSort用来对给入的字符串进行初始化排序，以满足一个升序的要求，因为我们求的是字典顺序，所以如果初始不是升序的话，结果就不会包含最小的那个数据了。接下来的isDescend就是判断当前的这个字符串是否满足了降序排列，因为如果一个字符串满足降序排列，则它就达到了最大，不需要再继续求解其后续了。findNext函数是此次的重点，有关其中每步的步骤我都添加了注解，并且使用到了递归，只有当序列满足降序要求时才会停止递归。
将该函数改造成非递归形式比较简单，主要针对findNext函数进行修改。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
29private boolean findNext(char[] c){
if (isDescend(c))
return false;
if (c.length<2)
return false;
int lessThanRightIndex = c.length-2;
int smallestBiggerIndex = 0;
char base = 'z';
/*第一步：找到第一个小于右边值的字符，并记录其位置*/
for (int i=c.length-2;i>=0;i--){
if(c[i]<c[i+1]){
lessThanRightIndex = i;
break;
}
}
/*第二步：找到第一个小于右边值的字符之后的字符中比它大，但是比其余要小的字符*/
for (int j = lessThanRightIndex;j<c.length;j++){
if(c[j]>c[lessThanRightIndex]&&c[j]<=base){
smallestBiggerIndex = j;
base = c[j];
}
}
/*第三步：交换，第一个小于右边值的字符和之后比它大的最小字符*/
swap(c,lessThanRightIndex,smallestBiggerIndex);
/*第四步：翻转第一个小于右边值字符之后的字符*/
reverse(c,lessThanRightIndex+1,c.length-1);
System.out.println(c);
return true;
}
主要是将递归中返回数组转换成一个判断，然后在主函数中对其进行循环即可，因为对数组c的改变是永久性的，这样下次运行的时候的c就变成了上一次运行时候的c，这个目的和使用递归是相似的，所以只要保证满足一个结束条件即可不断对其进行循环。1
2
3
4
5
6
7
8public static void main(String[] args) {
FullPermutationWithDicSortAndNoRecursion fpwdsanr = new FullPermutationWithDicSortAndNoRecursion();
char[] c = new char[]{'1','2','3','4'};
FullPermutationWithDicSort fpwds = new FullPermutationWithDicSort();
c = fpwds.initialSort(c);
System.out.println(c);
while (fpwdsanr.findNext(c));
}
以上是对主函数的修改。