class Solution {public void reverseString(char[] s) {int left = 0;
int right = s.length - 1;
while(left< right){s[left] ^= s[right];
s[right] ^= s[left];
s[left] ^= s[right];
left++;
right--;
}
}
}
此题使用双向指针即可，无难度；关键:此题使用了异或运算，异或可以代替三角交换，需要熟悉。
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(i + k - 1,ch.length - 1);
while(start< end){ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
return new String(ch);
}
}此题与上一题类似，区别在于只翻转部分的字符串，对其进行变量控制即可。
三、剑指 Offer 05. 替换空格class Solution {//使用一个新的对象，复制 str，复制的过程对其判断，是空格则替换，否则直接复制，类似于数组复制
public static String replaceSpace(String s) {if (s == null) {return null;
}
//选用 StringBuilder 单线程使用，比较快，选不选都行
StringBuilder sb = new StringBuilder();
//使用 sb 逐个复制 s ，碰到空格则替换，否则直接复制
for (int i = 0; i< s.length(); i++) {//s.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
//if (" ".equals(String.valueOf(s.charAt(i)))){}
if (s.charAt(i) == ' ') {sb.append("%20");
} else {sb.append(s.charAt(i));
}
}
return sb.toString();
}
//方式二：双指针法
public String replaceSpace(String s) {if(s == null || s.length() == 0){return s;
}
StringBuffer sb = new StringBuffer();
for(int i = 0;i< s.length(); i++){if(s.charAt(i) == ' '){sb.append(" ");
}
}
//若是没有空格直接返回
if(sb.length() == 0){return s;
}
int left = s.length() - 1;
s += sb.toString();
int right = s.length() - 1;
char[] ch = s.toCharArray();
while(left>=0){if(ch[left] == ' '){ch[right--] = '0';
ch[right--] = '2';
ch[right] = '%';
}else{ch[right] = ch[left];
}
left--;
right--;
}
return new String(ch);
}
}
此题有两种解法：
解法一：new一个StringBuilder()，判断是否为空格进行追加就行，无难度
解法二：遍历数组得出有多少空格，算出数组的大小，从后往前填充数组；从后往前遍历数组是该算法的关键
class Solution {public String reverseWords(String s) {// 1.去除首尾以及中间多余空格
StringBuilder sb = removeSpace(s);
// 2.反转整个字符串
reverseString(sb, 0, sb.length() - 1);
// 3.反转各个单词
reverseEachWord(sb);
return sb.toString();
}
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;
}
//翻转字符串，使用方法setCharAt();
public void reverseString(StringBuilder sb, int start, int end) {while (start< end) {char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
private void reverseEachWord(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;
}
}
}此题的思路是：先翻转整个字符串，再翻转单个单词。具体看代码内的注释。
五、剑指Offer58-II.左旋转字符串class Solution {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();
}
public void reverseString(StringBuilder sb, int start, int end) {while (start< end) {char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
}与上一题类似，使用局部翻转加全局翻转即可实现左旋字符串。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧