刷题日记 Day 7 : 反转字符串、反转字符串II、替换空格、反转字符串中的单词、左旋转字符串

墨蓝 2024-03-26 22:05 66阅读 0赞

#### 刷题日记 Day 7 ####

*  一 . LeetCode 344 . 反转字符串
 *  二 . LeetCode 541 . 反转字符串 II
 *  三 . 剑指Offer 05.替换空格
 *  四 . LeetCode 151 . 反转字符串中的单词
 *  五 . 剑指Offer58-II.左旋转字符串

> 本篇文章 , 是在代码随想录 60 天编程挑战的基础上进行的题目讲解  
> 参与链接在此 : [https://programmercarl.com/other/xunlianying.html][https_programmercarl.com_other_xunlianying.html]

> 大家好 , 这个专栏 , 给大家带来的是 60 天刷题强训 . 最令大家头疼的事就是刷题了 , 题目又臭又长又抽象 , 有的题读都读不懂 , 更别说做了 . 所以 , 这个专栏想要帮助大家摆脱困境 , 横扫饥饿 , 做回自己 . 让大家掌握最常见的面试题 , 面对陌生的题目也不至于无从下手 .  
> 也希望大家监督 , 60 天从 0 到 1 , 咱们一起做大佬 ~  
> 今天是 Day7 , 大家加油~  
> ![image.png][]  
> 专栏链接 : [https://blog.csdn.net/m0\_53117341/category\_12247938.html?spm=1001.2014.3001.5482][https_blog.csdn.net_m0_53117341_category_12247938.html_spm_1001.2014.3001.5482]  
> 昨天的打卡链接 : [http://t.csdn.cn/dUWnw][http_t.csdn.cn_dUWnw]

## 一 . LeetCode 344 . 反转字符串 ##

题目链接 : [344. 反转字符串][344.]  
![image.png][image.png 1]  
这道题 , 非常简单 , 同样是双指针的问题  
定义 left 指针在最左面 , 定义 right 指针在最后面  
然后交换 left 指针和 right 指针对应的元素 , left 往后移动 , right 往前移动  
循环条件就是 left < right , 最中间的那个元素是不需要交换的  
代码就在这里

class Solution {
        
        public void reverseString(char[] s) {
        
            int left = 0;
            int right = s.length - 1;
            while(left < right) {
        
                char t = s[left];
                s[left] = s[right];
                s[right] = t;
    
                left++;
                right--;
            }
    
        }
    }

## 二 . LeetCode 541 . 反转字符串 II ##

题目链接 : [541. 反转字符串 II][541. _ II]  
![image.png][image.png 2]  
本道题目也是在上一道题的基础上产生的变种 , 来看解析  
![image.png][image.png 3]

class Solution {
        
        private static void reverse(char[] chars,int left,int right) {
        
            while(left < right) {
        
                char tmp = chars[left];
                chars[left] = chars[right];
                chars[right] = tmp;
                left++;
                right--;
            }
        }
    
        public String reverseStr(String s, int k) {
        
            // 1. 将字符串转换成数组方便操作
            char[] chars = s.toCharArray();
            // 2. i 每次走 2K 步
            for(int i = 0;i < chars.length;i += 2 * k) {
        
                // 让 left 指向左边
                int left = i;
                // 让 right 指向 k 位置
                // 但是有可能最后一组不够 2K 个元素了,那就把前 k 个元素交换
                // 所以需要分类讨论
                // right 没走到最后面的时候正常交换
                // right 走到最后面不够一组的情况下,直接交换left~数组最后一个元素
                int right = Math.min(left + k - 1,chars.length - 1);
                // 对 left~right 区间进行交换
                reverse(chars,left,right);
            }
            // 再将结果转换成字符串然后返回
            return new String(chars);
        }
    }

## 三 . 剑指Offer 05.替换空格 ##

题目链接 : [剑指 Offer 05. 替换空格][Offer 05.]  
![image.png][image.png 4]  
这道题 , 我们可以借助 Java 中的 StringBuilder  
当遇见普通元素的时候 , 正常拼接即可  
当遇见空格的时候 , 我们直接拼接一个 %20 即可  
代码如下

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();
        }
    }

## 四 . LeetCode 151 . 反转字符串中的单词 ##

题目链接 : [151. 反转字符串中的单词][151.]  
![image.png][image.png 5]  
这道题 , 他是有点东西在的 , 比较麻烦 , 来看栗子  
![image.png][image.png 6]  
推荐大家去看一下视频讲解 : [https://www.bilibili.com/video/BV1uT41177fX/?vd\_source=b0e82af8eb60883fa2180dda1770795d][https_www.bilibili.com_video_BV1uT41177fX_vd_source_b0e82af8eb60883fa2180dda1770795d]  
代码在这里~

class Solution {
        
        public String reverseWords(String s) {
        
            // 1. 先转化成数组方便操作
            char[] chars = s.toCharArray();
            // 2. 去除首尾以及中间多余空格
            chars = removeExtraSpaces(chars);
            // 3. 反转整个字符串
            reverse(chars,0,chars.length-1);
            // 4. 反转每个单词
            reverseEachWord(chars);
            // 5. 返回结果
            return new String(chars);
        }
    
        // 去除首尾以及中间多余空格
        private static char[] removeExtraSpaces(char[] chars) {
        
            // 思路类似于移除元素,把要移除的元素当做空格即可
            // 1. 定义快慢指针
            int fast = 0;
            int slow = 0;
    
            // 快指针负责遍历数组中的每一个元素
            // 找到不是空格的元素,把它放在 slow 上
            for(;fast < chars.length;fast++) {
        
                // 找到了不是空格的元素
                if(chars[fast] != ' ') {
        
                    // 注意:slow不是初始位置的时候,我们应该手动提供一个空格加入到答案中
                    if(slow != 0) {
        
                        // slow 记得往后移动
                        chars[slow++] = ' ';
                    }
                    // 将这一个单词加入到slow位置上
                    while(fast < chars.length && chars[fast] != ' ') {
        
                        chars[slow++] = chars[fast++];
                    }
                }
            }
    
            // 去掉空格之后数组的长度一定变化了
            // 我们直接 new 一个新数组,将目前数组的元素拷贝过来
            // 注意:要拷贝 slow 之前的,slow 之前的都是有效元素
            char[] newChars = new char[slow];
            newChars = Arrays.copyOf(chars,slow);
            return newChars;
        }
    
        // 反转整个字符串
        private static void reverse(char[] chars,int left,int right) {
        
            while(left < right) {
        
                char tmp = chars[left];
                chars[left] = chars[right];
                chars[right] = tmp;
    
                left++;
                right--;
            }
        }
    
        // 反转每个单词
        private static void reverseEachWord(char[] chars) {
        
            // 1. 定义双指针
            int start = 0;
            int end = 0;
    
            // 2. end 负责找到每一个单词的末尾位置
            for(;end <= chars.length;end++) {
        
                // end 走到数组末尾了 || end 找到空格了
                if(end == chars.length || chars[end] == ' ') {
        
                    // 将 start 位置~end的前一个位置进行反转
                    reverse(chars,start,end-1);
                    // 更新新的 start 位置
                    start = end + 1;
                }
            }
        }
    }

## 五 . 剑指Offer58-II.左旋转字符串 ##

题目链接 : [剑指 Offer 58 - II. 左旋转字符串][Offer 58 - II.]  
什么都不多说 , 看图

> 代码随想录当中的这个图能完全说明问题 , 大家看这个即可

先反转前半部分 , 也就是 0~n-1 部分  
再反转后半部分 , 也就是 n~arr.length-1 部分  
最后全部翻转  
我们惊喜地发现 , 竟然达到了左旋转字符串的效果  
![image.png][image.png 7]

class Solution {
        
        public String reverseLeftWords(String s, int n) {
        
            // 1. 将字符串转化成数组
            char[] chars = s.toCharArray();
    
            // 2. 反转前半部分
            reverse(chars,0,n-1);
            // 3. 反转后半部分
            reverse(chars,n,chars.length-1);
            // 4. 一起反转
            reverse(chars,0,chars.length-1);
    
            return new String(chars);
        }
        
        private static void reverse(char[] chars,int left,int right) {
        
            while(left < right) {
        
                char tmp = chars[left];
                chars[left] = chars[right];
                chars[right] = tmp;
    
                left++;
                right--;
            }
        }
    }

--------------------

今天的题可算是完事了  
大家记得给一键三连嗷~  
![image.png][image.png 8]

[https_programmercarl.com_other_xunlianying.html]: https://programmercarl.com/other/xunlianying.html
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1cab09f75c4949bd8a938209df95927c.png
[https_blog.csdn.net_m0_53117341_category_12247938.html_spm_1001.2014.3001.5482]: https://blog.csdn.net/m0_53117341/category_12247938.html?spm=1001.2014.3001.5482
[http_t.csdn.cn_dUWnw]: http://t.csdn.cn/dUWnw
[344.]: https://leetcode.cn/problems/reverse-string/
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/17125194eade4a4a85f7fbf320f5f4c0.png
[541. _ II]: https://leetcode.cn/problems/reverse-string-ii/
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/cab28a0c5afe4c4a8645d548a98bbda3.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/69b2f76f2cc54bd99c12fe3fda683c44.png
[Offer 05.]: https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d5cdaec0268a4674a13448737d737eb0.png
[151.]: https://leetcode.cn/problems/reverse-words-in-a-string/
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b3e505313b7c43388f2510e238d0c676.png
[image.png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0b5b605a08694c4595c4fb4ac40ba739.png
[https_www.bilibili.com_video_BV1uT41177fX_vd_source_b0e82af8eb60883fa2180dda1770795d]: https://www.bilibili.com/video/BV1uT41177fX/?vd_source=b0e82af8eb60883fa2180dda1770795d
[Offer 58 - II.]: https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
[image.png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/dfad718bfaab45128625f88067f2dfd4.png
[image.png 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4c6bec8ef4f5478c9b91fb719ff8b420.png