代码随想录算法训练营第七天 | LeetCode 344(反转字符串) LeetCode 541(反转字符串II) LeetCode 剑指05(替换空格) LeetCode 151(反转字符串中的单词) LeetCode 剑指58(II.左旋转字符串)
344:反转字符串
双指针遍历 直接交换元素
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
// temp交换方法
// char temp;
// while(left < right){
// temp = s[left];
// s[left] = s[right];
// s[right] = temp;
// left++;
// right--;
// }
// 位运算交换
while(left < right){
s[left] ^= s[right];
s[right] ^= s[left];
s[left] ^= s[right];
left++;
right--;
}
}
}
541:反转字符串II
方法一：
class Solution {
public String reverseStr(String s, int k) {
char[] result = s.toCharArray();
int startIndex = 0;
int length = result.length;
int count = 1;
for (int i = 0; i < length; i++,count++) {
//计数至2k
if(count % (2*k) == 0){
int left = startIndex * k * 2;
int right = left + k - 1;
while(left < right){
result[left] ^= result[right];
result[right] ^= result[left];
result[left] ^= result[right];
left++;
right--;
}
startIndex++;
count = 0;
}
}
//判断退出循环时 count的计数
//不等于零时 则意味着剩余字符大于零且小于2k
count--;
if(count != 0){
if(count >= k){
int left = length - count;
int right = left + k - 1;
while(left < right){
result[left] ^= result[right];
result[right] ^= result[left];
result[left] ^= result[right];
left++;
right--;
}
}else{
int left = length - count;
int right = length - 1;
while(left < right){
result[left] ^= result[right];
result[right] ^= result[left];
result[left] ^= result[right];
left++;
right--;
}
}
}
return new String(result);
}
}
方法二：
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){
ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
return new String(ch);
}
}
剑指05:替换空格
方法一 遍历替换
方法二 直接调用replaceAll函数
方法三 双指针法
方法一
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
int len = s.length();
//遍历
for(int i = 0;i < len;i++){
char c = s.charAt(i);
//判断是不是空格
if(c == ' '){
sb.append("%20");
continue;
}
sb.append(c);
}
return sb.toString();
}
}
方法二
class Solution {
public String replaceSpace(String s) {
return s.replaceAll(" ","%20");
}
}
方法三
class Solution {
public String replaceSpace(String s) {
if(s == null || s.length() == 0){
return s;
}
//扩充空间，空格数量2倍 " " 要被替换成 "%20" 所以是空格数量的两倍
StringBuilder str = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == ' '){
str.append(" ");
}
}
//若是没有空格直接返回
if(str.length() == 0){
return s;
}
//有空格情况 定义两个指针
//左指针：指向原始字符串最后一个位置
int left = s.length() - 1;
s += str.toString();
//右指针：指向扩展字符串的最后一个位置
int right = s.length()-1;
char[] chars = s.toCharArray();
while(left>=0){
if(chars[left] == ' '){
chars[right--] = '0';
chars[right--] = '2';
chars[right] = '%';
}else{
chars[right] = chars[left];
}
left--;
right--;
}
return new String(chars);
}
}
151:反转字符串中的单词
方法一 自己做的时候的代码
import java.util.Arrays;
class Solution {
public String reverseWords(String s) {
//切分
String[] result = s.split(" ");
//去除空字符串
result = Arrays.stream(result).filter(str -> !"".equals(str)).toArray(String[]::new);
int len = result.length;
if(len == 1){
return result[0];
}
StringBuilder sb = new StringBuilder();
//构造结果字符串
//先从后面遍历
for(int i = len - 1; i > len / 2; i--){
sb.append(result[i]);
sb.append(" ");
}
//再从前面遍历
for(int i = len / 2; i >= 0; i--){
sb.append(result[i]);
sb.append(" ");
}
//删除最后一个空格
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
}
方法二
// 双反转+移位，在原始数组上进行反转。空间复杂度O(1)
class Solution {
/**
* 思路：
* ①反转字符串 "the sky is blue " => " eulb si yks eht"
* ②遍历 " eulb si yks eht"，每次先对某个单词进行反转再移位
* 这里以第一个单词进行为演示：" eulb si yks eht" ==反转=> " blue si yks eht" ==移位=> "blue si yks eht"
*/
public String reverseWords(String s) {
//步骤1：字符串整体反转（此时其中的单词也都反转了）
char[] initialArr = s.toCharArray();
reverse(initialArr, 0, s.length() - 1);
int k = 0;
for (int i = 0; i < initialArr.length; i++) {
if (initialArr[i] == ' ') {
continue;
}
int tempCur = i;
while (i < initialArr.length && initialArr[i] != ' ') {
i++;
}
for (int j = tempCur; j < i; j++) {
if (j == tempCur) {
//步骤二：二次反转
//对指定范围字符串进行反转，不反转从后往前遍历一个个填充有问题
reverse(initialArr, tempCur, i - 1);
}
//步骤三：移动操作
initialArr[k++] = initialArr[j];
if (j == i - 1) { //遍历结束
//避免越界情况，例如=> "asdasd df f"，不加判断最后就会数组越界
if (k < initialArr.length) {
initialArr[k++] = ' ';
}
}
}
}
if (k == 0) {
return "";
} else {
//参数三：以防出现如"asdasd df f"=>"f df asdasd"正好凑满不需要省略空格情况
return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1);
}
}
//反转
public void reverse(char[] chars, int begin, int end) {
for (int i = begin, j = end; i < j; i++, j--) {
chars[i] ^= chars[j];
chars[j] ^= chars[i];
chars[i] ^= chars[j];
}
}
}
剑指58:II.左旋转字符串
方法一
class Solution {
public String reverseLeftWords(String s, int n) {
int len = s.length();
//构造结果数组
char[] result = new char[len];
int i = 0;
//遍历n~length
for(int k = n; k < len;k++){
result[i++] = s.charAt(k);
}
//遍历前n个
for(int k = 0; k < n; k++){
result[i++] = s.charAt(k);
}
return new String(result);
}
}
方法二
class Solution {
public String reverseLeftWords(String s, int n) {
int len=s.length();
StringBuilder sb=new StringBuilder(s);
//反转区间为前n的子串
reverseString(sb,0,n-1);
//反转区间为n到末尾的子串
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--;
}
}
}