代码随想录算法训练营第八天 |344.反转字符串，541.反转字符串II，54.替换数字，151.反转字符串里的单词，55.右旋转字符串

比眉伴天荒 2024-04-23 03:56 37阅读 0赞

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

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 1]

3、视频讲解： [字符串基础操作！ | LeetCode：344.反转字符串\_哔哩哔哩\_bilibili][_ LeetCode_344._bilibili]

4、题目：

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char\[\] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：  
输入：\["h","e","l","l","o"\]  
输出：\["o","l","l","e","h"\]

示例 2：  
输入：\["H","a","n","n","a","h"\]  
输出：\["h","a","n","n","a","H"\]

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

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

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 2]

3、视频讲解：

[字符串操作进阶！ | LeetCode：541. 反转字符串II\_哔哩哔哩\_bilibili][_ LeetCode_541. _II_bilibili]

4、题目：

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

输入: s = "abcdefg", k = 2  
输出: "bacdfeg"

*  时间复杂度: O(n)
 *  空间复杂度: O(1)

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

#### （卡码网）54、替换数字 ####

1、题目链接：[题目页面][Link 3]

2、文章讲解：[代码随想录][Link 4]

3、题目：

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"

输入：一个字符串 s,s 仅包含小写字母和数字字符。

输出：打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

数据范围：1 <= s.length < 10000。

4、思路：后面补上

import java.util.Scanner;
    
    class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            String s = in.nextLine();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                if (Character.isDigit(s.charAt(i))) {
                    sb.append("number");
                }else sb.append(s.charAt(i));
            }
            System.out.println(sb);
        }
    }

#### 151、反转字符串里的单词 ####

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 5]

3、视频讲解：

[字符串复杂操作拿捏了！ | LeetCode:151.翻转字符串里的单词\_哔哩哔哩\_bilibili][_ LeetCode_151._bilibili]

4、题目：

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：  
输入: "the sky is blue"  
输出: "blue is sky the"

示例 2：  
输入: " hello world! "  
输出: "world! hello"  
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：  
输入: "a good example"  
输出: "example good a"  
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

5、思路：后面补上

class Solution {
        public String reverseWords(String s) {
            // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
            // 1.去除首尾以及中间多余空格
            StringBuilder sb = removeSpace(s);
            // 2.反转整个字符串
            reverseString(sb, 0, sb.length() - 1);
            // 3.反转各个单词
            reverseEachWord(sb);
            return sb.toString();
        }
    
        private StringBuilder removeSpace(String s) {
            // System.out.println("ReverseWords.removeSpace() called with: s = [" + 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++;
            }
            // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
            return sb;
        }
    
        /**
         * 反转字符串指定区间[start, end]的字符
         */
        public void reverseString(StringBuilder sb, int start, int end) {
            // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
            while (start < end) {
                char temp = sb.charAt(start);
                sb.setCharAt(start, sb.charAt(end));
                sb.setCharAt(end, temp);
                start++;
                end--;
            }
            // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
        }
    
        private void reverseEachWord(StringBuilder sb) {
            int start = 0;
            int end = 1;
            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;
            }
        }
    }

####  ####

#### （卡码网）55、右旋转字符串 ####

1、题目链接：[题目页面][Link 6]

2、文章讲解：[代码随想录][Link 7]

3、、题目：

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

输入：输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出：输出共一行，为进行了右旋转操作后的字符串。

样例输入：

2
    abcdefg

样例输出：

fgabcde

数据范围：1 <= k < 10000, 1 <= s.length < 10000;

4、思路：后面补上

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = Integer.parseInt(in.nextLine());
            String s = in.nextLine();
    
            int len = s.length();  //获取字符串长度
            char[] chars = s.toCharArray();
            reverseString(chars, 0, len - 1);  //反转整个字符串
            reverseString(chars, 0, n - 1);  //反转前一段字符串，此时的字符串首尾尾是0,n - 1
            reverseString(chars, n, len - 1);  //反转后一段字符串，此时的字符串首尾尾是n,len - 1
            
            System.out.println(chars);
    
        }
    
        public static void reverseString(char[] ch, int start, int end) {
            //异或法反转字符串，参照题目 344.反转字符串的解释
            while (start < end) {
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
    }

[LeetCode_ -]: https://leetcode.cn/problems/reverse-string/
[Link 1]: https://www.programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_344._bilibili]: https://www.bilibili.com/video/BV1fV4y17748
[LeetCode_ - 1]: https://leetcode.cn/problems/reverse-string-ii/
[Link 2]: https://www.programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_541. _II_bilibili]: https://www.bilibili.com/video/BV1dT411j7NN
[Link 3]: https://kamacoder.com/problempage.php?pid=1064
[Link 4]: https://programmercarl.com/kama54.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html
[LeetCode_ - 2]: https://leetcode.cn/problems/reverse-words-in-a-string/
[Link 5]: https://www.programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_151._bilibili]: https://www.bilibili.com/video/BV1uT41177fX
[Link 6]: https://kamacoder.com/problempage.php?pid=1065
[Link 7]: https://programmercarl.com/kama55.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.html