每日一刷《剑指offer》字符串篇之左旋转字符串
左旋转字符串
难度：中等
描述
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S ，请你把其循环左移 K 位后的序列输出。例如，字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果，即 “XYZdefabc”
举例
解题思路
方法一：遍历拼接;既然循环左移是前面n个字符平移到了最后，我们就可以分开加入字符串中，先挨个加入后面部分字符，然后再回过头加入前面的字符。但需要注意的是需要进行取余；
方法二：三次反转；循环左移相当于从第n个位置开始，左右两部分视作整体翻转。即abcdefg左移3位defgabc可以看成AB翻转成BA（这里小写字母看成字符元素，大写字母看成整体）。既然是翻转我们就可以用到reverse函数。
实现代码（java）
方法一：
import java.util.*; public class Solution { public String LeftRotateString(String str,int n) { //取余，因为每次长度为n的旋转数组相当于没有变化 if(str.isEmpty() || str.length() == 0) return ""; int m = str.length(); //取余，因为每次长度为m的旋转数组相当于没有变化 n = n % m; StringBuilder res = new StringBuilder(); //先遍历后面的，放到前面 for(int i = n; i < m; i++) res.append(str.charAt(i)); //再遍历前面的放到后面 for(int i = 0; i < n; i++) res.append(str.charAt(i)); return res.toString(); } }
方法二：
public class Solution { public String LeftRotateString(String str,int n) { //取余，因为每次长度为n的旋转数组相当于没有变化 if(str.isEmpty() || str.length() == 0) return ""; int m = str.length(); n = n % m; //第一次逆转全部元素 char[] s = str.toCharArray(); reverse(s, 0, m - 1); //第二次只逆转开头m个 reverse(s, 0, m - n - 1); //第三次只逆转结尾m个 reverse(s, m - n, m - 1); return new String(s); } //反转函数 private void reverse(char[] s, int start, int end){ while(start < end){ swap(s, start++, end--); } } //交换函数 private void swap(char[] s, int a, int b){ char temp = s[a]; s[a] = s[b]; s[b] = temp; } }
学习完本题的思路你可以解决如下题目：
替换空格
难度：简单
描述
请实现一个函数，将一个字符串s中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
举例
解题思路
方法一：和上面题目一样可以使用StringBuilder,把字符串中的每个字符一个个添加到StringBuilder中，如果遇到空格就把他换成%20。
方法二：先将字符串转换为单个字符，申请一个临时数组，然后再遍历这个字符串的每个字符，如果不是空格就把遍历的字符添加到临时数组中，如果是空格就添加3个字符'%'，'2'，'0'分别到临时数组中，最后再把临时数组转化为字符串即可。
实现代码（java）
方法一：
public String replaceSpace(String s) { StringBuilder stringBuilder = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ' ') stringBuilder.append("%20"); else stringBuilder.append(s.charAt(i)); } return stringBuilder.toString(); }
方法二：
public String replaceSpace(String s) { int length = s.length(); char[] array = new char[length * 3]; int index = 0; for (int i = 0; i < length; i++) { char c = s.charAt(i); if (c == ' ') { array[index++] = '%'; array[index++] = '2'; array[index++] = '0'; } else { array[index++] = c; } } String newStr = new String(array, 0, index); return newStr; }
学习完本题的思路你可以解决如下题目：
翻转单词序列
难度：简单
描述
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
举例
解题思路
方法一：栈;我们都知道栈是先进后出的，于是我们可以用方法一中分割单词的方式，在大的句子字符串中分割出一个一个地单词。然后从头到尾遍历单词，将分割出来的单词送入栈中，然后按照栈中弹出的字符串顺序拼接单词即可使单词之间逆序。
- step 1：遍历字符串，将整个字符串按照空格分割然后入栈。
- step 2：遍历栈，将栈中内容弹出拼接成字符串。
方法二：两次反转;我们需要的是将单词位置反转，也即是单词内部不变，属于字符串部分反转问题。如果将整个字符串反转，单词位置倒是反转了，但是内部次序也改变了，此时就需要将内部再反转回去，因此两次反转可以解决。
- step 1：将字符串整体反转。
- step 2：遍历反转后的字符串，以空格为界限找到一个单词。
- step 3：将每个单词部分反转。
实现代码（java）
方法一：
import java.util.*; public class Solution { public String ReverseSentence(String str) { Stack<String> st = new Stack<String>(); String[] temp = str.split(" "); //单词加入栈中 for(int i = 0; i < temp.length; i++){ st.push(temp[i]); st.push(" "); } StringBuilder res = new StringBuilder(); //去掉最后一个空格 if(!st.isEmpty()) st.pop(); //栈遵循先进后厨，单词顺序是反的 while(!st.isEmpty()) res.append(st.pop()); return res.toString(); } }
方法二：
import java.util.*; public class Solution { //字符串反转函数 private void reverse(char [] c, int l, int h){ //双指针反转 while(l < h) swap(c, l++, h--); } //字符交换函数 private void swap(char [] c, int l, int h){ char temp = c[l]; c[l] = c[h]; c[h] = temp; } public String ReverseSentence(String str) { int n = str.length(); char[] c = str.toCharArray(); //第一次整体反转 reverse(c, 0, n - 1); for(int i = 0; i < n; i++){ int j = i; //以空格为界找到一个单词 while(j < n && c[j] != ' ') j++; //将这个单词反转 reverse(c, i, j - 1); i = j; } return new String(c); } }
