基础知识
// String -> char[]
char[] string=s.toCharArray();
// char[] -> String
String.valueOf(string)注意replace replaceAll区别，都是全局匹配替换，不过replaceAll是正则匹配
LeetCode 344.反转字符串
分析1.0
基础的前后指针元素互换
class Solution {
public void reverseString(char[] s) {
if(s==null){
return;
}
int len=s.length;
if(len==0 || len==1){
return;
}
int left=0, right=len-1;
while(left<right){
char temp=s[right];
s[right]=s[left];
s[left]=temp;
left++;
right--;
}
return;
}
}LeetCode 541. 反转字符串II
分析1.0
涉及多次反转，考虑写一个根据索引反转字符串的函数，反转部分之后，考虑剩下的元素个数；
String -> StringBuilder 或者采用字符数组的方式处理
class Solution {
public String reverseStr(String s, int k) {
int len=s.length();
if(s==null){
return null;
}
char[] string=s.toCharArray();
int endIndex=len-1;
int startIndex=0;
while(startIndex<=endIndex){
//System.out.println("start position: "+startIndex);
int gap=endIndex-startIndex+1;
//System.out.println("gap: "+gap);
if(gap<k){
reverse(string, startIndex, endIndex);
break;
}else if(gap<2*k && gap>=k){
reverse(string, startIndex, startIndex+k-1);
break;
}else{
reverse(string, startIndex, startIndex+k-1);
startIndex=startIndex+2*k;
}
//System.out.println(string);
}
return String.valueOf(string);
}
public void reverse(char[] s, int left, int right){
while(left<right){
char temp=s[left];
s[left]=s[right];
s[right]=temp;
left++;
right--;
}
}
}LeetCode
分析1.0
直接用了API
class Solution {
public String replaceSpace(String s) {
return s.replace(" ","%20");
}
}LeetCode 151.翻转字符串里的单词
分析1.0
遍历，遍历过程中去除多余空格，将获得的一个一个单词采用尾插法加入List<StringBuilder>,最后再使用空格拼接
获取单词首指针、检查合法性、获取尾指针
class Solution {
public String reverseWords(String s) {
if(s==null){
return null;
}
// s=s.trim();
ArrayDeque<String> stack = new ArrayDeque();
int len=s.length();
int leftIndex=0, rightIndex=0;
while(leftIndex<len){
// 获取s中每个单词的起始索引
while(leftIndex<len && s.charAt(leftIndex)==' '){
leftIndex++;
}
// 这里要注意跳出
if(leftIndex>=len){
break;
}
rightIndex=leftIndex;
while(rightIndex<len && s.charAt(rightIndex)!=' '){
rightIndex++;
}// 此时rightIndex指向某个单词的最后一个字符的索引的后面的空格
String temp=s.substring(leftIndex, rightIndex);
System.out.println("----"+temp);
stack.push(temp);
leftIndex=rightIndex;
}
StringBuilder ans = new StringBuilder();
while(!stack.isEmpty()){
ans.append(stack.pop())
.append(" ");
}
// return ans.toString().trim(); 二者都行
return ans.substring(0, ans.length()-1);
}
}失误
每次获取一个单词前都要检查当前额left指针是否超过了s的长度
substring() 要小写 subString()是错的
分析2.0
反转s，再反转所有的单词
采用trim()方法去除收尾多余空格，再用replaceAll()
LeetCode 剑指Offer58-II.左旋转字符串
分析1.0
相当于逻辑左移所有字符串元素，左移个数如果是元素个数的倍数，那就不移动，即要将移动次数对字符串长度取余，再向左移动，增加字符串空间，取余后的索引为n的元素为新的首元素，将原字符串截断后拼接即可
class Solution {
public String reverseLeftWords(String s, int n) {
int len=s.length();
n=n%len;
String s1=s.substring(0,n);
String s2=s.substring(n,len);
return s2+s1;
}
}分析2.0
反转两个局部，再整体反转
总结
- 数组长度 arr.length 字符串长度 s.length()
双指针-前后指针、快慢指针、滑动窗口 降低时间复杂度利器
工具：Arrays、Collections、队列、栈(逆序好帮手)、哈希表/map
substring() 要小写 subString()是错的
s.trim().replaceAll("\\s+", " ") 去除收尾多余空格并将字符串内多余空格变成一个空格
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end
