字符串part01 算法

字符串part01

今日任务

●??344.反转字符串

●??541.?反转字符串II

●? 卡码网：54.替换数字

●??151.翻转字符串里的单词

●? 卡码网：55.右旋转字符串

1.344.反转字符串

344.?反转字符串

//import java.util.Arrays;
class Solution {
    public void reverseString(char[] s) {
        //我们什么时候使用库函数，什么时候不要用库函数呢？
        //如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。
        //这样子是错误的，后面才看见必须原地修改输入数组
        // //思路1：反着遍历出来
        // //定义一个新的数组
        // char[] s2=new char[s.length];
        // int j=0;
        // for(int i=s.length-1;i>=0;i--){
        //     s2[j]=s[i];
        //     j++;
        // }
        // //重新赋值给原数组
        // s=s2;

        //思路2，使用函数
        //Arrays.reverse(s);

        //思路上，两个指针，一左一右，互相换位置
        //直到left>right//需不需要等于呢，等于就不用换了，所以作为不用的条件left>=right
        int left=0;
        int right=s.length-1;
        while(left<right){
            //交换值
            char temp=s[left];
            s[left]=s[right];
            s[right]=temp;

            left++;
            right--;
        }
    }
}

2.?541.?反转字符串II

541.?反转字符串 II

class Solution {
    public String reverseStr(String s, int k) {
        char[] c = s.toCharArray();
        //这道题目问题说的不清楚，是每隔2k个
        for(int i=0;i<c.length;i+=2*k){
            //也是定义两个指针，用来反转
            int left=i;//没想到的点
            //判断够不够k个来决定right的大小
            //剩余字符少于 k 个，则将剩余字符全部反转,right=c.length-1;
            //如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
            //right=left+k-1;
            //我们计算最后面的位置到2k+1的地方还有多少个元素
            int rest=c.length-2*k;
            //剩余字符少于 k 个，则将剩余字符全部反转
            // int right;
            // if(rest<k){
            //     right=c.length-1;
            // }else if(rest<2*k&&rest>=k){
            //     right=left+k-1;
            // }
            int right=Math.min(c.length-1,left+k-1);

            //进行反战操作
          while(left<right){
                char temp=c[left];
                c[left]=c[right];
                c[right]=temp;

                left++;
                right--;
          }
        }
        s=String.valueOf(c);
        return s;
        //return new String(c);
        // //超出时间限制
        // char[] c = s.toCharArray();
        // //思路：3个指针
        // //如果里面长度的大小等于0时，返回空字符串(题目已经限制好)
        // //如果里面长度不足到2k，也返回原有字符串
        // if(s.length()<2*k){
        //     return s;
        // }

        // //长度大于等于2k时
        // //两个指针用作反转位置
        // int left=0;
        // int right=k-1;
        // for(int i=0;i<c.length;i++){
        //     //一个指针用做遍历当前位置
        //     //每计数至 2k 个字符，就反转前 k 个字符
        //     //先进行反转，在进行当前指针的跳转
        //     if(i==2*k){
        //         //反转前 k 个字符进行反转
        //         while(left<right){
        //             char temp=c[left];
        //             c[left]=c[right];
        //             c[right]=temp;
        //         }

                
        //     //当前指针在第2k的地方
        //     //我们计算最后面的位置到2k+1的地方还有多少个元素
        //     int rest=c.length-2*k;
        //     //剩余字符少于 k 个，则将剩余字符全部反转
        //     if(rest<k){
        //         left=2*k+1-1;
        //         right=c.length-1;
        //         while(left<right){
        //             char temp=c[left];
        //             c[left]=c[right];
        //             c[right]=temp;
        //         }
        //     }else if(rest<2*k&&rest>=k){
        //         //则反转前 k 个字符
        //         left=2*k+1-1;
        //         right=k-1;
        //         while(left<right){
        //             char temp=c[left];
        //             c[left]=c[right];
        //             c[right]=temp;
        //         }
        //     }
        //     }
        // }
        // s=String.valueOf(c);
        // return s;
    }
}

3.卡码网：54.替换数字

https://kamacoder.com/problempage.php?pid=1064

import java.util.*;
public class Main{
    public static void main (String[] args){
        //输入
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        //不要想着在原有的字符串改变了，那是不现实的
        //定义一个新的字符串来接收
        String news="";
        //开始遍历字符串
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)>='a'&&s.charAt(i)<='z'){
                //如果是字母，就不懂的加上去
                news+=s.charAt(i);
            }else{
                //是数字的话就加上number
                news+="number";
            }
        }
        System.out.println(news);
        
    }
}

4.?151.翻转字符串里的单词

151.?反转字符串中的单词

class Solution {
    public String reverseWords(String s) {
        //这样子定义一个新的空的字符串就失去了意义

        //看完代码随想录后
        //反转
        //先移除多余空格，再将整个字符串反转，最后把单词逐个反转 

        //空格的问题还挺麻烦，有单词前中后的空格
        //删除空格思路
        //定义两个指针
        //快指针用来遍历字符串，指向每一个元素不为空格的位置
        //慢指针用来将不为空格的字符进行存储，是一个新数组的下标
        

        //先移除多余空格//那就是去除首尾以及中间多余空格
        //先将字符串转为数组，因为字符串不能修改
        char[] c=s.toCharArray();
        //进行删除首位空格
        c=removenull(c);
        //现在的数组是移除掉多余的空格的了
        //接下来是再将整个字符串反转
        reversec(c,0,c.length-1);
        //最后把单词逐个反转
        reversecw(c);
        //将这个数组转为字符串
        //String str = Arrays.toString(c);
        //return str;
        return new String(c);

    }
    //去除首尾以及中间多余空格函数（用快慢指针去移除多余的空格）
    public char[] removenull(char[] c){
        int slow=0;
        for(int fast=0;fast<c.length;fast++){
            if(c[fast]!=' '){
                if(slow!=0){
                    //给非第一个单词前面加上空字符串
                    c[slow]=' ';
                    slow++;
                }
                //开始遍历一个完整的单词
                //因为是show和fast都是++，所以我们要控制fast不能越界
                while(fast<c.length&&c[fast]!=' '){
                    c[slow]=c[fast];
                    slow++;
                    fast++;
                }
                //到一个单词遍历完之后遇见的就是空字符串，然后我们就进行遍历下一个
            }
        }
        //return c[slow];
        //不能返回原数组c,因为slow之后的位置元素可能存在多个空格
        char[] newarr=new char[slow];
        System.arraycopy(c,0,newarr,0,slow);
        return newarr;
    }
    //数组反转
    public void reversec(char[] c,int start,int end){
        while(start<end){
            char temp=c[start];
            c[start]=c[end];
            c[end]=temp;

            start++;
            end--;
        }
    }
    //每个单词逐步反转
    public void reversecw(char[] c){
        int start=0;
        for(int end=0;end<=c.length;end++){//不加等于会报错
            //如果遇到了为空，那么就将空前的位置传输反转的end中，进行反转
            if(end==c.length||c[end]==' '){//不加end==c.length会报错
                reversec(c,start,end-1);
                //移动此时start的位置，就在空格后一个了，也就是
                start=end+1;
            }
        }
    }
}

5.卡码网：55.右旋转字符串

https://kamacoder.com/problempage.php?pid=1065

用java写老是会超时

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        //int k=sc.nextInt();
        //String s=sc.next();
        int k=Integer.parseInt(sc.nextLine());
        String s=sc.nextLine();
        
        //思路：先让转成数组
        //将数组进行反转（一个函数）
        //遍历到第k个（下标为k-1)，分别进行拆开反转（另外一个函数）
        //先让转成数组
        char[] c=s.toCharArray();
        //反转整个数组
        reversec(c,0,c.length-1);
        //反转单独单词
        //reversecw(c,k);
        reversec(c,0,k-1);
        reversec(c,k,c.length-1);
        //将数组转为字符串
        //String news=new String(c);
        //输出
        System.out.println(c);
    }
    public static void reversec(char[] c,int start,int end){
        while(start<end){
            char temp=c[start];
            c[start]=c[end];
            c[end]=temp;
            
            start++;
            end--;
        }
        //异或法反转字符串，参照题目 344.反转字符串的解释
        // while (start < end) {
        //     c[start] ^= c[end];
        //     c[end] ^= c[start];
        //     c[start] ^= c[end];
        //     start++;
        //     end--;
        // }
    }
    // public void reversecw(char[] c,int k){
    //   int end=k;
    //   for(int start=0;start<c.length;start++){
    //       if(start==k){
    //           reversec(c,start,end);
    //           start=k+1;
    //           end=c.length-1;
    //       }
    //       while(start<end){
    //           char temp=c[start];
    //           c[start]=c[end];
    //           c[end]=temp;
            
    //           start++;
    //           end--;
    //       }
    //   }
    // }
}