本文共 2351 字,大约阅读时间需要 7 分钟。
题目描述
汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,输入字符串”abcXYZdef”和数字3,输出循环左移3位后的结果,即“XYZdefabc”。
分析
直接思路:将字符串分割为两个部分:需要移动的字符和剩下的字符(指不需要左移的字符),分别用两个字符数组存储。再将两个字符数组合并成新的字符串即可。这样使用 O(n) 的辅助空间,实现了 O(n) 的时间复杂度。
牛客AC:
public class Solution { public String LeftRotateString(String str,int n) { if(str == null || str.length() <= 0) return ""; int length = str.length(); char[] moveChars = new char[n]; char[] leftChars = new char[length - n]; // 左旋转 for(int i = 0; i < length; i++) { if(i < n) moveChars[i] = str.charAt(i); else leftChars[i - n] = str.charAt(i); } // 合并 StringBuffer sb = new StringBuffer(); for(int i = 0; i < length - n; i++) sb.append(leftChars[i]); for(int i = 0; i < n; i++) sb.append(moveChars[i]); return sb.toString(); }}
推荐思路:
有前面的关于字符串的翻转的分析(详见,利用翻转函数reverseCharSeq(char[] seq, int startIndex, int endIndex)
,先翻转被分割的左右两个子串,再翻转整个字符串,可以实现题目中的翻转。辅助空间仅仅为翻转是的tmpChar,为 O(1) ,时间复杂度为 O(n) 。
代码:
public String leftRotateStr2(String str,int n) { if(str == null || str.length() <= 0) return ""; if(n <= 0) return str; int firstStartIndex = 0; int firstEndIndex = n - 1; int secondStartIndex = n; int secondEndIndex = str.length() - 1; char[] charSeq = str.toCharArray(); // String 转为 char数组 // 翻转前后两个部分 reverseCharSeq(charSeq, firstStartIndex, firstEndIndex); reverseCharSeq(charSeq, secondStartIndex, secondEndIndex); // 翻转整个字符串 reverseCharSeq(charSeq, firstStartIndex, firstEndIndex); return String.copyValueOf(charSeq); // 返回String } /** * 翻转字符数组 * @param charSeq 字符数组 * @param startIndex 开始索引 * @param endIndex 结束索引 */ public void reverseCharSeq(char[] charSeq, int startIndex , int endIndex) { if(charSeq == null || charSeq.length <= 0 || startIndex > endIndex) return; while(startIndex < endIndex) { char tmp = charSeq[startIndex]; charSeq[startIndex] = charSeq[endIndex]; charSeq[endIndex] = tmp; startIndex++; endIndex--; } }
参考
1. 何海涛,剑指offer名企面试官精讲典型编程题(纪念版),电子工业出版社转载地址:http://ezxgi.baihongyu.com/