1. LeetCode 344. 反转字符串
1.1 思路
- 根据题意很自然想到头尾双指针
- 头指针left=0；尾指针right=arr.length-1；定义临时变量temp进行交换
- while(left<right)这里有无等于号均可，交换以后两指针均往中间靠拢
1.2 代码
class Solution { public void reverseString(char[] s) { int l = 0; int r = s.length - 1; while(l < r){ char temp = s[l]; s[l] = s[r]; s[r] = temp; l++; r--; } } }
2. LeetCode 541. 反转字符串 II
2.1 思路
- 理清题意：够2k个字符，则前k个翻转；不够2k个也不够k个，则这部分全部翻转；不够2k个但够k个，则这部分不用翻转
- i遍历方法，由于这题是2k个2k个字符进行检验的，因此i+=2k，这样避免i++后用一个计数变量控制检验，避免了麻烦
- 如果符合2k长度的话，则翻转i到i+k，由于编程语言自己实现的函数一般都是左闭右开，因此i到i+k一般是不包含第i+k个的，因此这样就是翻转了k长度的字符串。这里需要判断一下if(i+k<=arr.length)，不要超了数组的长度，这里需要等于号，因为假设i=0，k=3，剩余数组长度是3，符合翻转条件，这时i+k<=arr.length，可以翻转，说明要等于号
- 如果剩余数组不够k个了，那就将i到arr.length这部分直接翻转
2.2 代码
class Solution { public String reverseStr(String s, int k) { char[] strs=s.toCharArray(); for(int i=0;i<strs.length;i+=2*k){ if(i+k<=strs.length){ reverse(strs,i,i+k-1); }else{ reverse(strs,i,strs.length-1); } } return new String(strs); } public static void reverse(char[] ch,int i,int j){ char temp; while(i<=j){ temp=ch[i]; ch[i]=ch[j]; ch[j]=temp; i++; j--; } } }
3. 剑指Offer 05.替换空格
3.1 思路
- 使用一个新的对象，复制 str，复制的过程对其判断，是空格则替换，否则直接复制，类似于数组复制
- 使用 StringBuilder 逐个复制 s ，遇到空格就append("%20")，否则就直接添加元素
3.2 代码
//使用一个新的对象，复制 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(); }
4. LeetCode 151. 反转字符串中的单词
4.1 思路
- 整体思路是将整个字符串翻转，然后再将翻转后的单词逐个翻转
- 需要把开头、结尾、中间多余的空格删除，这里参考day01的移除元素这题
- 翻转字符串，参考day08的翻转字符串
- 翻转单词，同理参考day08的翻转字符串2
4.2 代码
class Solution { /** * 不使用Java内置方法实现 * <p> * 1.去除首尾以及中间多余空格 * 2.反转整个字符串 * 3.反转各个单词 */ public String reverseWords(String s) { // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]"); // 1.去除首尾以及中间多余空格 StringBuilder sb = removeSpace(s); // 2.反转整个字符串 reverseString(sb, 0, sb.length() - 1); // 3.反转各个单词 reverseEachWord(sb); return sb.toString(); } private StringBuilder removeSpace(String s) { // System.out.println("ReverseWords.removeSpace() called with: s = [" + 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++; } // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]"); return sb; } /** * 反转字符串指定区间[start, end]的字符 */ public void reverseString(StringBuilder sb, int start, int end) { // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]"); while (start < end) { char temp = sb.charAt(start); sb.setCharAt(start, sb.charAt(end)); sb.setCharAt(end, temp); start++; end--; } // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]"); } 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; } } }
5. 剑指Offer 58-II.左旋转字符串
5.1 思路
- 整体思路：局部翻转+整体翻转
- 先翻转区间为n的子字符串
- 再翻转区间为n到末尾的子字符串
- 最后翻转整个字符串
5.2 代码
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--; } } }
