代码随想录算法训练营第七天 | LeetCode 344(反转字符串) LeetCode 541(反转字符串II) LeetCode 剑指05(替换空格) LeetCode 151(反转字符串中的单词) LeetCode 剑指58(II.左旋转字符串)

344:反转字符串

LeetCode 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

LeetCode 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:替换空格

LeetCode 剑指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:反转字符串中的单词

LeetCode 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.左旋转字符串

LeetCode 剑指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--;
            }
        }
}

本栏目推荐文章
• 2024/1/13 算法笔记
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 用jacoco统计JAVA项目测试代码覆盖率
• 算法练习题
• 算法学习Day26组合总和、分割回文串
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• 【SPFA】最短路的一种算法
• GDB调试之源代码查看与管理(六)

随想录 训练营 随想 算法 代码随想录 训练营 随想 算法 算法 随想录 训练营 随想 算法 随想录 训练营 序列 算法 随想录 训练营 数组 算法 随想录 训练营 总和 算法 随想录 队列 训练营 算法 随想录 训练营 九天 算法 解数 随想录 训练营 子集 算法 随想录 训练营 训练营 随想 代码python