一、反转字符串
1.方法概述
- 双引用法。创建两个引用left和right，left指向字符数组的开端，right指向字符数组的末端，再进行交换即可。
2.具体实现
Java实现
点击查看代码
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length-1;
while(left < right){
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
}
3.要点总结
- 因为该题存储字母的是字符数组，也就是数组所以元素再内存中是连续分布的，就可以通过头尾引用进行交换，不用开辟新的数组。
- while循环条件是当left<right的时候，等于不需要交换。
二、反转字符串Ⅱ
1.方法概述
- 首先需要将字符串转换为字符数组方便后续的反转，使用for循环来遍历，但是是以2k倍来移动。在移动过程中，需要判断当剩下的元素不够下一次移动时，需要将数组start后k-1位置作为反转引用的结尾，将剩余元素进行反转。最后使用new String()将反转后的字符数组转换为字符串进行返回。
2.具体实现
Java实现
点击查看代码
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0;i<ch.length;i += 2*k){
int start = i;
int end = Math.min(ch.length - 1,start+k-1);
while(start < end){
char tmp = ch[start];
ch[start] = ch[end];
ch[end] = tmp;
start++;
end--;
}
}
return new String(ch);
}
}
3.要点总结
- 本题的解法主要也是双引用来解决，每隔2k个反转前k个，尾数不够k个时候全部反转。但是引用的结尾和开始需要下点功夫来找。首先是反转的开端start，最外层for循环每次以2k倍进行移动，就很好的解决了反转开端start的位置，末端位置就是判断start+k-1的位置和length-1的位置那个小就是末端位置，当尾数不够k个时全部反转。
- new String()：一般使用字符转码的时候，即字节数组转换为字符串的时候。比如在对数据做编解码/加解密转为二进制字符串时，就可以直接使用此方法进行转换处理。
三、剑指Offer 05.替换空格
1.方法概述
- 使用一个新的对象，复制 str，复制的过程对其判断，是空格则替换，否则直接复制，类似于数组复制。
2.具体实现
Java实现
点击查看代码
class Solution {
public String replaceSpace(String s) {
if(s == null){
return null;
}
StringBuilder sb = new StringBuilder();
for(int i = 0;i<s.length();i++){
if(s.charAt(i)==' '){
sb.append("%20");
}else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
3.要点总结
- 选用 StringBuilder 单线程使用，比较快。
四、翻转字符串里的单词
1.方法概述
- 先将多余的空格去除，然后将整个字符串进行反转，最后将每个单词进行反转。
2.具体实现
Java实现
点击查看代码
class Solution {
private StringBuilder removeSpace(String s){
int start = 0;
int end = s.length()-1;
while(s.charAt(start) == ' '){
start++;
}
while(s.charAt(end) == ' '){
end--;
}
StringBuilder sb = new StringBuilder();
while(start <= end){
char c = s.charAt(start);
if(c != ' ' || sb.charAt(sb.length() - 1) != ' '){
sb.append(c);
}
start++;
}
return sb;
}
private void reverseString(StringBuilder sb, int start,int end){
while(start<end){
char tmp = sb.charAt(start);
sb.setCharAt(start,sb.charAt(end));
sb.setCharAt(end,tmp);
start++;
end--;
}
}
private void reverseWords(StringBuilder sb){
int start = 0;
int end = 1;
int n = sb.length();
while(start < n){
while(end < n && sb.charAt(end) != ' '){
end++;
}
reverseString(sb,start,end-1);
start = end + 1;
end = start + 1;
}
}
public String reverseWords(String s) {
StringBuilder sb = removeSpace(s);
reverseString(sb,0,sb.length()-1);
reverseWords(sb);
return sb.toString();
}
}
3.要点总结
- 首先是空格的去除，前后两端是不留空格的，而单词与单词之间是要正常留一个空格的。所以在中间的空格的去除条件是c != ' ' || sb.charAt(sb.length() - 1) != ' '。当新建的sb的最后一个是空格的时候，append一个空格进去，其余情况下不加就能很好的解决该问题。
- 要求空间复杂度是O(1)，就要考虑使用 StringBuilder， StringBuilder 类的对象能够被多次的修改，并且不产生新的未使用对象。
- 字符的反转使用双引用的思路来解决，需要注意的是这里使用setCharAt() 方法将指定索引处的字符设置为 ch。
- 最后就是一个单词一个单词的在进行反转，这里end下标的选定，是判定在空格出现之前的位置为end位置。找到end之后先进行前一单词的位置的反转，先提供第一个单词的start下标和end下标，接下来再start = end + 1，end = start + 1。直到start大于sb停止即可。
五、剑指Offer58-II.左旋转字符串
1.方法概述
- 反转区间为前n的子串，反转区间为n到末尾的子串，反转整个字符串。
2.具体实现
Java实现
点击查看代码
class Solution {
private void reverseString(StringBuilder sb,int start,int end){
while(start < end){
char tmp = sb.charAt(start);
sb.setCharAt(start,sb.charAt(end));
sb.setCharAt(end,tmp);
start++;
end--;
}
}
public String reverseLeftWords(String s, int n) {
int len = s.length();
StringBuilder sb = new StringBuilder(s);
reverseString(sb,0,n-1);
reverseString(sb,n,len-1);
return sb.reverse().toString();
}
}
3.要点总结
- 本题通过局部反转加整体反转的思想实现左旋目的。
仅供个人学习参考，欢迎批评指正！
标签：end,int,反转,II,start,字符串,sb From： https://www.cnblogs.com/neverlate/p/17121277.html