反转字符串
确定左右边界left，right
更换s[left]、s[right]
class Solution {
public void reverseString(char[] s) {
int left = 0,right = s.length - 1;
while (left < right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}复杂度分析
时间复杂度：O（n）
空间复杂度：O（1）
反转字符串Ⅱ
将字符串转化为字符数组：char[] ch = s.toCharArray()
每次循环以2k为长度，确定开始和结束位置
int start = i;
int end = Math.min(ch.length - 1,start + k - 1);
替换start、end的字符
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;
//这里是判断尾数够不够k个，取决于end指针的位置
int end = Math.min(ch.length - 1,start + k - 1);
while (start < end){
char temp = ch[start];
ch[start] = ch[end];
ch[end] = temp;
start++;
end--;
}
}
return new String(ch);
}
}复杂度分析
时间复杂度：O（n）
空间复杂度：O（n）
替换空格
剑指 Offer 05. 替换空格 - 力扣（LeetCode）
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0;i < s.length();i++){
if (s.charAt(i) == ' '){
sb.append("%20");
} else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}复杂度分析：
时间复杂度：O（n）
空间复杂度：O（n）
反转字符串里的单词
去除首尾以及中间多余空格
反转整个字符串
反转各个单词
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();
}
public 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;
}
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--;
}
}
public void reverseEachWord(StringBuilder sb){
int start = 0;
int end = 1;//end指向空格的下标
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;
}
}
}复杂度分析
时间复杂度：O（n）
空间复杂度：O（n）
左旋转字符串
剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode）
假设有序列：a b c d e f g，k = 2
反转前 2 个 字符：b a c d e f g
反转前 2 个字符后的序列：b a g f e d c
反转所有序列：c d e f g a b
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);
reverseString(sb,0,len - 1);
return sb.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--;
}
}
}复杂度分析
时间复杂度：O（n）
空间复杂度：O（n）
实现strStr()
28. 实现 strStr() - 力扣（LeetCode）
class Solution {
public int strStr(String haystack, String needle) {
int[] next = new int[needle.length()];
getNext(next, needle);
int j = -1;
for (int i = 0; i<haystack.length();i++){
while (j >=0 && haystack.charAt(i) != needle.charAt(j+1)){
j = next[j];
}
if (haystack.charAt(i) == needle.charAt(j+1)){
j++;
}
if (j == needle.length() - 1){
return (i - needle.length() + 1);
}
}
return -1;
}
public void getNext(int[] next, String s){
int j = -1;
next[0] = j;
for (int i = 1; i<s.length(); i++){
while (j >= 0 && s.charAt(i) != s.charAt(j+1)){
j=next[j];
}
if (s.charAt(i) == s.charAt(j+1)){
j++;
}
next[i] = j;
}
}
}重复的子字符串
class Solution {
public boolean repeatedSubstringPattern(String s) {
int[] next = new int[s.length()];
getNext(next,s);
int len = s.length();
if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0){
return true;
}
return false;
}
public void getNext(int[] next, String s){
int j = -1;
next[0] = j;
for (int i = 1; i<s.length(); i++){
while (j >= 0 && s.charAt(i) != s.charAt(j+1)){
j = next[j];
}
if (s.charAt(i) == s.charAt(j+1)){
j++;
}
next[i] = j;
}
}
}无重复的最长子串
新建一个Hashmap用来<字符，索引>的键值对
滑动窗口维持一个不重复字符串
left为滑动窗口的最左边
i为滑动窗口的最右边
如果新加入的字符已经在滑动窗口中存在了
将重复字符从窗口左边移除
更新左边界
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) return 0;
HashMap<Character,Integer> map = new HashMap<>();
int max = 0;//最长子串长度
int left = 0;//滑动窗口左下标，i相当于滑动窗口右下标
for (int i = 0;i < s.length();i++){
if (map.containsKey(s.charAt(i))){//出现重复字符时
int hitVal = map.get(s.charAt(i)) + 1;//为了把重复的字符从窗口左边移除
left = Math.max(left,hitVal);
}
map.put(s.charAt(i),i);
max = Math.max(max,i - left + 1);//i - left + 1是当前窗口大小
}
return max;
}
}复杂度分析
时间复杂度：O（n）
空间复杂度：O（1）