反转字符串II
link:541. 反转字符串 II - 力扣(LeetCode)
思路分析
关键点在于我们要找对反转思路,2k是一个区间,没达到条件和达到条件之后怎么处理.
因此考虑怎么筛选条件.
首先创建一个字符数组用于存储遍历的下标位置用于筛选【其实类似双指针判断 此时尾指针的判断 避免越界】判断区间为[数组长度-1,起始位置 + k - 1]
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;//防止越界 平移判断区间和length比较int end = Math.min(ch.length -1 ,start + k - 1);while(start < end) {ch[start] ^= ch[end];ch[end] ^= ch[start];ch[start] ^= ch[end];start++;end--;}}//最终返回字符串return new String(ch);}
}
反转字符串中的单词
link:151. 反转字符串中的单词 - 力扣(LeetCode)
思路分析
倒序遍历字符串,记录左右边界i,j,找到空格删除,挨个遍历.最后蒋单词拼接返回字符串.
class Solution {public String reverseWords(String s) {//删除首尾空格s = s.trim();int j = s.length() - 1;int i = j;StringBuilder res = new StringBuilder();//搜索第一个空格while(i >= 0) {while(i >= 0 && s.charAt(i) != ' '){i--;}//添加单词res.append(s.substring(i + 1, j + 1) + " ");while(i >= 0 && s.charAt(i) == ' '){i--;}//继续遍历下一个单词j = i;}//转换字符串return res.toString().trim();}
}
除此之外还能用双指针法解决.用fast和slow指针解决空格.
1.首先利用双指针取出空格(但是保留单词之间的空格【slow指针++为空的时候赋值为空再++】
2.反转整个字符串
3.单个单词内部反转
class Solution {public String reverseWords(String s) {// 将字符串转换为字符数组char[] ch = s.toCharArray();// 去除多余空格并接收返回的字符数组ch = removeExtraSpaces(ch);// 反转整个字符串reverse(ch, 0, ch.length - 1);// 单词内部反转reverseWords(ch);// 输出字符串return new String(ch);}public char[] removeExtraSpaces(char[] ch) {int slow = 0;for (int fast = 0; fast < ch.length; fast++) {if (ch[fast] != ' ') {// 如果 slow 不为 0,意味着不是首单词前的字符,需要添加空格if (slow != 0) {ch[slow++] = ' ';}// 复制单词while (fast < ch.length && ch[fast] != ' ') {ch[slow++] = ch[fast++];}}}// 创建新数组来存储去除多余空格后的字符串char[] newCh = new char[slow];System.arraycopy(ch, 0, newCh, 0, slow);return newCh;}public void reverse(char[] ch, int left, int right) {while (left < right) {ch[left] ^= ch[right];ch[right] ^= ch[left];ch[left] ^= ch[right];left++;right--;}}public void reverseWords(char[] ch) {int start = 0;for (int end = 0; end <= ch.length; end++) {// 当 end 遇到空格或者到达字符数组末尾,开始反转单词if (end == ch.length || ch[end] == ' ') {reverse(ch, start, end - 1);start = end + 1;}}}
}
Tip
1.String substring(int start, int end) 返回一个新的 String
,它包含此序列当前所包含的字符子序列。
2.在使用 StringBuffer 类时,每次都会对 StringBuffer 对象本身进行操作,而不是生成新的对象,所以如果需要对字符串进行修改推荐使用 StringBuffer。
3.trim() 方法用于删除字符串的头尾空白符。