第四章 字符串part01

344.反转字符串

public void reverseString(char[] s) {int len = s.length;int left = 0;int right = len-1;while (left <= right){char tmp = s[right];s[right] = s[left];s[left] = tmp;left++;right--;}
}

反转字符串II

• 注意String不可变，因此可使用char数组或者Stringbuilder

public String reverseStr(String s, int k) {int len = s.length();char[] arr = s.toCharArray();for (int index = 0; index < s.length(); index+=2*k) {if (index+k > len) {// 反转index到末尾reverseString(arr,index,len-1);}else {// 反转前k个reverseString(arr,index,index+k-1);}}return new String(arr);
}public static void reverseString(char[] s,int left,int right) {while (left <= right){char tmp = s[right];s[right] = s[left];s[left] = tmp;left++;right--;}
}

剑指Offer 05.替换空格

public String replaceSpace(String s) {StringBuilder sb = new StringBuilder();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if (ch == ' ') {sb.append("%20");}else {sb.append(ch);}}return sb.toString();
}

151.翻转字符串里的单词

• substring时间复杂度为o(n)
• 使用双指针方法，left指向第一个非空格字符，right指向单词的末尾，当遇到非空格，则将left到right的子字符串加入sb。
• 当遇到连续空格时，便left指针左移

public String reverseWords(String s) {s = s.trim();StringBuilder sb = new StringBuilder();int left = s.length()-1;int right = s.length()-1;while (left != 0) {char ch = s.charAt(left);if (ch != ' ') {left--;}// 将left到right的内容加入stringelse {sb.append(s.substring(left+1,right+1).toCharArray());sb.append(" ");while (s.charAt(left) == ' '){left--;}right = left;}}sb.append(s.substring(left,right+1).toCharArray());return sb.toString().trim();
}

剑指Offer58-II.左旋转字符串

如果使用C++可以实现o(1)的空间复杂度，而Java只能o(n)空间复杂度

• 方法1：开辟StringBuilder，将后面字符加入，再加入前面字符，实现反转

public String reverseLeftWords(String s, int n) {StringBuilder sb = new StringBuilder();for (int i = n; i < s.length(); i++) {sb.append(s.charAt(i));}for (int i = 0; i < n; i++) {sb.append(s.charAt(i));}return sb.toString();
}

• 方法2:直接使用substring

public String reverseLeftWords(String s, int n) {String s1 = s.substring(n);String s2 = s.substring(0,n);return s1+s2;}