代码随想录算法训练营Day7 | 344.反转字符串、541.反转字符串||、替换数字、151.反转字符串中的单词、右旋字符串

2023-12-21 21:21:51

LeetCode 344 反转字符串

在这里插入图片描述
本题思路:反转字符串比较简单,定义两个指针,一个 i = 0, 一个 j = s.length-1。然后定义一个临时变量 tmp,进行交换 s[i] 和 s[j]。

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

LeetCode 541 反转字符串||

在这里插入图片描述

本题思路:最重要的理解题目含义,就是每一次走 2*k 步,如果剩余的字符长度大于等于k,就反转前 k 个字符,如果小于 k , 就将剩下的全部反转。 个人感觉这个剩余字符小于 2k的条件毫无软用,

下面用一个例子来分析下思路,方便更好理解。

  • 初始情况下 i = 0, i 每次走 i += 2 * k 步在这里插入图片描述
  • 判断剩余个数是否大于等于 k =2,其实就是判断(i + k <= array.length) 此时符合条件,反转前 K 个 ,调用 reverseSubStr(i,i+k,array),左闭右开。 在这里插入图片描述
  • i 往后移动 i = i + 2 * k,此时 i = 0 + 4 = 4在这里插入图片描述
  • 继续判断 (i + k <= array.length) ,此时条件符合 4 + 2 <= 6, 反转前 K 个 ,调用 reverseSubStr(i,i+k,array),左闭右开。 在这里插入图片描述
  • 此时 i = i + 2 * k = 4 + 8,不符合循环,结束。最终结果如下在这里插入图片描述
class Solution {
    public String reverseStr(String s, int k) {
        // 将字符串转换成数组
        char[] array = s.toCharArray();

        for(int i = 0; i < array.length; i+=2*k){
            // 先判断如果剩余字符个数大于 k,或者小于 2k, 就反转这前 K个
            // 本题主要理清楚,只要剩余个数大于等于k,
            if(i + k <= array.length){
                reverseSubStr(i,i+k,array);
                continue;
            }
            // 如果小于 K,就反转剩下的全部
            reverseSubStr(i,array.length,array);
        }
        return new String(array);
    }

    // 左闭右开
    public static void reverseSubStr(int l,int r, char[] s){
        while(l <= r-1){
            char tmp = s[l];
            s[l] = s[r-1];
            s[r-1] = tmp;
            l++;
            r--;
        }
    }
}

KamaCoder 替换数字

在这里插入图片描述
本题思路:使用字符串拼接,使用 StringBuilder,遍历字符串,如果是 小写字母的话直接拼接,即可,如果是数字的话,就拼接 “number”

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        StringBuilder sb = new StringBuilder();
        for( Character c  : s.toCharArray()){
            if(c >= 'a' && c <= 'z' ){
                sb.append(c);
            }else{
                sb.append("number");
            }
        }
        System.out.println(sb);
    }
}

LeetCode 151 反转字符串中的单词

在这里插入图片描述
本题思路

  1. 去掉前面、后面、单词之间的重复空格
  2. 先整体反转
  3. 再单个单词反转

通过示例 2 ,来画个图分析下思路,下面是初始状态在这里插入图片描述

  • 首先是去空格判断,定义一个 Trim() 方法,来进行去除两端的空格,通过定义两个指针,一个 left ,一个 right, left++, right–。碰到第一个不为空格的就停下。在这里插入图片描述
  • 这是去掉两端空格以后的字符串 s在这里插入图片描述
  • 接下里就要进行字符串之间的多余空格进行去重,遍历字符串 s 分为两步; 新定义一个字符串拼接 StringBuilder sb
    • 如果不是空格的话,就直接拼接 sb.append(s.charAt(left)),如下,left++,直到遇到空格停止在这里插入图片描述
    • 可以看到上图,此时就遇到了空格,因为可能有多个空格,我们需要保留一个空格,所以需要判断 (left-1) 这个元素是不是空格,如果是空格,说明空格已经保存了,就跳过不做任何处理,直到遇到的不是空格为止, 可以看到上图 left-1 元素不是空格,所以直接拼接空格,并且left++;在这里插入图片描述
    • 此时上图,又遇到不是空格,直接拼接在这里插入图片描述
  • 最终得到 sb, 去掉多余空格以后的新字符串 sb在这里插入图片描述

  • 接下来就是反转全部字符串,这个逻辑的话和上述反转字符串一样,定义两个指针,一个 left, 一个 right, 然后定义一个 临时变量来交换 这两个数字
  • 最后反转每一个单词。

此处,使用 StringBuilder的时候, 不能 sb.charAt(left) = sb.charAt(right),会有语法错误。必须使用 sb.setCharAt(原值,要改变的值)

class Solution {
    public String reverseWords(String s) {
        // 1. 先去掉多余的空格
        StringBuilder sb = Trim(s);
        // 2. 先反转全部
        Reverse(sb,0,sb.length()-1);
        // 3. 反转每一个单词;

        // 定义反转起始位置
        int start = 0;
        // 定义反转结束位置
        int end = 0;
        for (int i = 0; i < sb.length(); i++) {
            // 找到第一个为空格的下标
            if (sb.charAt(i) == ' ') {
                end = i - 1;
                Reverse(sb, start, end);
                start = end + 2;
            }
        }
        // 最后一个单词单独进行反转
        Reverse(sb,start,sb.length()-1);
        return sb.toString();
    }
    // 反转所有单词
    public static void Reverse(StringBuilder s, int start, int end) {
        int left = start;
        int right = end;
        while (left <= right) {
            char tmp = s.charAt(left);
            s.setCharAt(left, s.charAt(right));
            s.setCharAt(right, tmp);
            left++;
            right--;
        }
    }

    // 去空格
    public static StringBuilder Trim(String s) {
        int left = 0;
        int right = s.length() - 1;
        StringBuilder sb = new StringBuilder();
        // 去除前面的空格
        while (left <= right && s.charAt(left) == ' ') {
            left++;
        }
        // 去除后面的空格
        while (left <= right && s.charAt(right) == ' ') {
            right--;
        }
        // 去重字符串之间的多余空格
        while (left <= right) {
            // 如果不等于空格,直接拼接这个字符
            if (s.charAt(left) != ' ') {
                sb.append(s.charAt(left));
                left++;
            } else { // 此时等于空格,需要判断前面一个是否为空格
                if (s.charAt(left - 1) != ' ') {
                    sb.append(s.charAt(left));
                    left++;
                } else {
                    left++;
                }
            }
        }
        return sb;
    }
}

虽然整体逻辑不难,但是写代码的时候,出现了很多错误,考虑不周到。还得多写几遍,没那么简单。

KamaCoder 右旋字符串

在这里插入图片描述
本题思路

  1. 先整体反转
  2. 再反转前 k 个
  3. 再反转后 length - k 个

可以通过下图分析得到,为什么这么做!在这里插入图片描述

public static void main (String[] args) {
        /* code */
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int k = scanner.nextInt();     
        // 1. 先整体旋转
        s = reverse(s,0,s.length()-1);
        // 2. 再分别反转
        s = reverse(s,0,k-1);
        s = reverse(s,k,s.length()-1);
        System.out.println(s);

    }

    // 此处左闭右闭
    public static String reverse(String s, int start,int end){
        char[] array = s.toCharArray();
        int left = start;
        int right = end;
        while (left < right) {
            char tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;

            left++;
            right--;
        }
        return new String(array);
    }

写这道题的时候,直接用 String 来进行交换,出现了语法错误。因为 String 是不可变的,不能交换里面的内容!

文章来源:https://blog.csdn.net/hero_jy/article/details/135118168
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。