代码随想录第八天
- Leetcode 344 反转字符串
- Leetcode 541 反转字符串 II
- Leetcode 剑指 Offer 05. 替换空格
- Leetcode 151. 反转字符串中的单词
- Leetcode 剑指 Offer 58 - II. 左旋转字符串
Leetcode 344 反转字符串
题目链接: 反转字符串
自己的思路:要交换第一个元素和最后一个元素,交换第二个元素和倒数第二个元素。。。,可以分析出是两个指针移动的过程,所以我们想到用双指针法来处理,定义左右两个指针,分别交换两个指针的元素,移动指针,一直到两个指针相等为止。
正确思路:双指针
代码:
class Solution {public void reverseString(char[] s) {//定义左右两个指针int left = 0;int right = s.length-1;while(left<right){//交换两个指针对应的元素char temp = s[left];s[left] = s[right];s[right] = temp;//移动两个指针left++;right--;}}
}
复杂度分析:
时间复杂度: O ( n ) \mathcal{O}(n) O(n)
空间复杂度: O ( 1 ) \mathcal{O}(1) O(1)
Leetcode 541 反转字符串 II
题目链接: 反转字符串 II
自己的思路:自己没想到
正确思路:首先将字符串转换为数组,方便进行操作,每次让i移动2k个单位(这非常重要),移动之后使用双指针反转前k个元素,如果剩余元素不足k个,那么反转剩余元素,所以要对chars.length-1和i+k-1的大小进行判断,取最小值,因为可能剩余元素不足k个,最后返回新的字符串即可。
代码:
class Solution {public String reverseStr(String s, int k) {//先将字符串转换为数组,方便操作char[] chars= s.toCharArray();//i每次移动2k个单位for (int i =0;i<chars.length;i+=2*k){int start = i;//判断是否还剩下k个元素,int end = Math.min(chars.length-1,i+k-1);//反转前k个元素或者反转剩余元素while(start<end){char temp = chars[start];chars[start] = chars[end];chars[end] = temp;start++;end--;}}//返回新字符串return new String(chars);}
}
复杂度分析:
时间复杂度: O ( n ) \mathcal{O}(n) O(n)
空间复杂度: O ( n ) \mathcal{O}(n) O(n)
Leetcode 剑指 Offer 05. 替换空格
题目链接: 替换空格
自己的思路:在替换完以后数组一定会扩大,由于java的字符串不可变,所以不能在原有的字符串的基础上进行扩容,我们选择新建一个字符串来存放替换之后的字符,使用双指针来完成赋值操作,一个指针index1指向原先字符串的尾部,另一个指针index2指向新字符串的尾部,如果index1指向非空格字符,则直接赋值给index2的位置,否则依次给index2的指针赋值’0’,‘2’,‘%’,直到index指向非0为止。
正确思路:扩容+双指针
代码:
class Solution {public String replaceSpace(String s) {//最初s的长度int length = s.length();//记录空格的数量int count = 0;for (int i =0;i<length;i++){if (s.charAt(i)==' '){count++;}}//新建一个数组存储最后的字符数组char[] chars = new char[length+count*2];//定义两个指针用于存储新数组的元素int index1 = length - 1;int index2 = chars.length-1;while(index1>=0){//如果不是空格的话直接赋值给chars即可if (s.charAt(index1)!=' '){chars[index2] = s.charAt(index1);index1--;index2--;}else{//如果是空格的话,则依次给chars赋值chars[index2] = '0';index2--;chars[index2] = '2';index2--;chars[index2] = '%';index2--;index1--;}}//返回最后的字符串return new String(chars);}
}
复杂度分析:
时间复杂度: O ( n ) \mathcal{O}(n) O(n)
空间复杂度: O ( n ) \mathcal{O}(n) O(n)
Leetcode 151. 反转字符串中的单词
题目链接: 反转字符串中的单词
自己的思路:没想出来
正确思路:双指针法+新建字符串;使用双指针进行处理,左右双指针,先使用双指针去除左右两边的空格,然后移动右边的指针,当碰到第一个为空格的字符时,说明已经遍历了一个单词,则将这个单词放置在新的字符串中,再加入一个空格,继续遍历,直到遍历完整个字符串。
代码:
class Solution {public String reverseWords(String s) {//定义两个指针int left = 0;int right = s.length()-1;//新建一个可变的字符串StringBuilder sb = new StringBuilder();//除去左右两边空格while(s.charAt(left)==' ')left++;while(s.charAt(right)==' ')right--;while(left<=right){int index = right;while(index>=left&&s.charAt(index)!=' ') index--;//将单词赋值给新的字符串for (int i = index+1;i<=right;i++){sb.append(s.charAt(i));}//如果没有把所有单词加进去,则加个空格if (index>left) sb.append(' ');while(index>=left&&s.charAt(index)==' ') index--;right = index;}return sb.toString();}
}
复杂度分析:
时间复杂度: O ( n ) \mathcal{O}(n) O(n)
空间复杂度: O ( n ) \mathcal{O}(n) O(n)
Leetcode 剑指 Offer 58 - II. 左旋转字符串
题目链接: 左旋转字符串
自己的思路:拼接截取;先将原来字符串加上原来字符串,然后从n到n+length进行截取即可
正确思路:
代码:
class Solution {public String reverseLeftWords(String s, int n) {int length = s.length();//将原来字符串复制一份进行拼接String res = s + s;//直接截取res = res.substring(n,n+length);return res;}
}
复杂度分析:
时间复杂度: O ( 1 ) \mathcal{O}(1) O(1)
空间复杂度: O ( n ) \mathcal{O}(n) O(n)