• 字符串的算法题目

    题目一：

    描述
    对于一个长度为 n 字符串，我们需要对它做一些变形。

    首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。

    比如"Hello World"变形后就变成了"wORLD hELLO"。

    数据范围: 1\le n \le 10^61≤n≤10
    6
    , 字符串中包括大写英文字母、小写英文字母、空格。
    进阶：空间复杂度 O(n)O(n) ， 时间复杂度 O(n)O(n)

    思路：

    在这里插入图片描述

    需要用到的知识点：

    1. JAVA关于字符串（String）类的常用方法

    1、str.length()方法
    作用：返回字符串的长度。

    2、str.equals(Object)
    作用：将给定字符串与当前字符串相比较，若两字符串相等，则返回true，否则返回false。

    3、str.substring（int beginIndex） 截取
    作用：返回字符串中从beginIndex开始的子串(从beginIndex 开始到末尾)。

    4、str.substring（int beginIndex,int endIndex） 截取
    作用：返回从beginIndex开始到endIndex-1的子串。或者说含头不含尾部来截取。

    5、str.charAt(int index)
    作用：返回index指定位置的字符。

    6、indexOf（String str）
    作用：返回str在字符串中第一次出现的位置/下标。注：从0开始数

    //1.返回的是字符第一次出现的角标/下标位置。
int indexOf（int ch）； 

 //2.返回的是从fromIndex开始字符出现的角标/下标位置。
int indexOf（int ch，int fromIndex）；

int indexOf（String str）； //3返回的是字符串第一次出现的角标/下标位置。

//4.返回的是从fromIndex开始字符串 出现的角标/下标位置。
int indexOf（String str，int fromIndex）； 

当访问的字符 或 字符串不存在时，返回 -1

//5. 反向索引，注：反向索引只是从右向左索引找到第一次出现目标的角标位置， 
//返回的依然是角标位置。
int lastIndexOf（int ch）： 反向索引（种类和解释与正向索引相同 ）

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    7、str.compareTo(String anotherString)
    作用：
    若调用该方法的字符串大于参数字符串，则返回大于0的值；
    若相等，则返回数0；
    若小于参数字符串，则返回小于0的值。

    8、str.replace（char oldChar,char newChar）
    作用：以newChar字符替换字符串中所有oldChar字符。

    9、trim（）
    作用：去掉字符串的首尾空格。
    注意： String s = " 我喜 欢java "; 中间的字符串不能被去掉；

    10、toLowerCase（）
    作用：将字符串中的所有字符都转换为小写字符。

    11、toUpperCase（）
    作用：将字符串中的所有字符都转换为大写字符。

    12、boolean contains(CharSequence str) CharSequence：为String实现的接口
    作用：判断字符串中是否包含指定字符串

    13、boolean isEmpty()
    作用：　　 判断字符串是否有内容，当且仅当长度为0时返回true。

    14、String[] split(String regex) 分割
    作用：指定其中某一个字符或字符串，以其下刀，切割字符串（其实应当依据正则表达式规则拆分）
    　　
    2.3、判断字符串是否以某某开头
    　　　　　　　　　　　　boolean startsWith(String prefix)
    2.4、判断字符串是否以某某结尾
    　　　　　　　　　　　　boolean endsWith(String suffix)
    2.5、判断字符串的内容是否相同 ，（不考虑大小写）
    　　　　　　　　　　　　boolean equalsIgnoreCase(String anotherString)
    3、转换。
    3.1、 将字符数组转换成字符串
    构造函数：
    String(char[] value)
    String(char[] value, int offset, int count)： 将数组中从下标offset开始，一共count位字符转换成字符串。

    静态方法：
    static String copyValueOf(char[] data)
    static String copyValueOf(char[] data, int offset, int count)
    static String valueOf(char[] data)

    3.2、 将字符串转换成字符数组
    char[] toCharArray()

    3.3、 将字节数组转换成字符串
    String(byte[] value)
    String(byte[] value, int offset, int count)： 将数组中从下标offset开始，一共count位字符转换成字符串。

    3.4、 将字符串转换成字节数组
    byte[] getBytes(String charsetName)

    3.5、 将基本数据类型转换成字符串

    static String valueOf(boolean b)
    static String valueOf(char c)
    static String valueOf(char[] data)
    static String valueOf(double d) 等等。

    注意：字符串和字节数组在转换过程中是可以指定编码表的。

    1. JAVA关于StringBuffer类的常用方法

    1.字符串连接操作（append（））

     StringBuffer sb = new StringBuffer();
        sb.append("a");
        sb.append("b");
        sb.append("c");
        sb.append("哈哈").append("d");
        System.out.println(sb);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    2.在任意位置处为StringBuffer添加内容（insert（））

     StringBuffer sb = new StringBuffer();
        sb.append("123456");
        sb.insert(0,"hello"); //在最开始加字符
        sb.insert(3,"添加"); //从0下标开始 在第三个字符后开始加字符

        sb.insert(sb.length(),"world");//在最后加字符
        System.out.println(sb);


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    3.字符串反转操作（reverse（））
    把字符串反过来输入

    StringBuffer sb = new StringBuffer();
        sb.append("world");
        sb.reverse();
        System.out.println(sb);
        输出：dlrow

    • 1
    • 2
    • 3
    • 4
    • 5

    4.替换指定范围的内容（replace（））

     StringBuffer sb = new StringBuffer();
        sb.append("world");
        sb.replace(0,2,"l"); //从零下标开始 后面2个字符 变成l
        System.out.println(sb);
输出：lrld

    • 1
    • 2
    • 3
    • 4
    • 5

    5.字符串截取（subString）//和字符串的用法一样

      StringBuffer sb = new StringBuffer();
        sb.append("ABc123465");
        String str = sb.substring(3,9);  //从第几个字符开始 到第几个结束
        System.out.println(str);


    • 1
    • 2
    • 3
    • 4
    • 5

    6.删除指定的字符串（delete（））

    deleteCharAt(int index) //删除指定下标处的字符

//删除从--到end 位置中间 的 几个字符
String str  =sb.delete(0,6).toString(); //从第一开始删除 到第6个字符

    • 1
    • 2
    • 3
    • 4

    3、获取 indexOf
    char charAt(int index) 返回此序列中指定索引处的 char 值。
    int indexOf(String str) 返回第一次出现的指定子字符串在该字符串中的索引。
    int indexOf(String str, int fromIndex) 从指定的索引处开始，返回第一次出现的指定子字符串在该字符串中的索引。
    int lastIndexOf(String str) 返回最右边出现的指定子字符串在此字符串中的索引。
    int lastIndexOf(String str, int fromIndex) 返回最后一次出现的指定子字符串在此字符串中的索引。

    在项目中经常会遇到截取字符串的需求，这里重点介绍两种常见的截取字符串方法。

    方法一：通过split()

    将正则传入split()。返回的是一个字符串数组类型。不过通过这种方式截取会有很大的性能损耗，因为分析正则非常耗时。

    方法二：通过subString()方法来进行字符串截取

    Java中的我们可以利用split把字符串按照指定的分割符进行分割，然后返回子字符串数组
    将一个字符串分割为子字符串，然后将结果作为字符串数组返回。

    注意事项
    在java.lang包中有String.split()方法，返回是一个数组。

    使用时要注意参数如果是特殊符号的话要进行转义。

    1、“.”和“|”都是转义字符，必须得加"“;
    　　如果用“.”作为分隔的话，必须是如下写法：
    String.split(”.“),这样才能正确的分隔开，不能用String.split(”.“);
    如果用“|”作为分隔的话，必须是如下写法：
    String.split(”|“),这样才能正确的分隔开，不能用String.split(”|");

    2、如果在一个字符串中有多个分隔符，可以用“|”作为连字符，比如：“acount=? and uu =? or n=?”,把三个都分隔出来，可以用
    　　String.split(“and|or”);

    3、public String[] split(String regex,int limit)根据匹配给定的正则表达式来拆分此字符串。
    　　此方法返回的数组包含此字符串的每个子字符串，这些子字符串由另一个匹配给定的表达式的子字符串终止或由字符串结束来终止。数组中
    　　的子字符串按它们在此字符串中的顺序排列。如果表达式不匹配输入的任何部分，则结果数组只具有一个元素，即此字符串。

    方法一：

    package com.company.day01;
/*
题目要求：
* 输入字符串：
"This is a sample",16

返回值：
"SAMPLE A IS tHIS"*/
public class Solution1 {
    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        String res = solution1.trans("This is a sample", 16);
        System.out.println(res);
    }

    /**
     *
     * @param s
     * @param n
     * @return
     */
    public String trans(String s, int n) {
        //第一步：先做容易的大小写转换，所有下小写颠倒
        if(n == 0)
            return s;

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            //如果是大写
            if(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'){
                //stringBuilder用于将转换后的字母串起来
                stringBuilder.append( (char)(s.charAt(i) + 32) );
            }else if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z'){
                stringBuilder.append( (char)(s.charAt(i)-32) );
            }else {
                stringBuilder.append(s.charAt(i));//串空格
            }
        }
        //stringBuilder存的是大小写转换后的字符串
        //第二步：整个字符串反转
        StringBuilder reverse = stringBuilder.reverse(); //ELPMAS ---
        //第三步：每一个单词内部进行反转
        for (int i = 0; i < n; i++) {
            int j = i; //j指针 从 i位置开始遍历
            while(j
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    方法二：

    package com.company.day01;

import java.util.ArrayList;
import java.util.List;

/*
题目要求：
* 输入字符串：
"This is a sample",16

返回值：
"SAMPLE A IS tHIS"*/
public class Solut2 {
    public static void main(String[] args) {
        Solut2 solut2 = new Solut2();
        String this_is_a_sample = solut2.trans("nowcoder",8);
        System.out.println(this_is_a_sample);
    }

    /**
     *
     * @param s
     * @param n
     * @return
     */
    public String trans(String s, int n) {
        //第一步：利用str.split将字符串分割成字符数组
        String[] strings = s.split(" ");//将字符串分割成字符数组：
        //第二步：倒序取出字符串数组
        StringBuffer res = new StringBuffer();
        for (int i = strings.length-1; i >= 0; i--) {
            //System.out.println(strings[i]);
            //大小写转换
            StringBuffer stringWord = new StringBuffer(strings[i]);
            //遍历单词sample
            for (int j = 0; j < stringWord.length(); j++) {//遍历单词数组
                if(stringWord.charAt(j)>='A' && stringWord.charAt(j)<='Z'){
                    stringWord=stringWord.replace(j,j+1, 
                            String.valueOf((char) (stringWord.charAt(j) + 32)));
                }else if(stringWord.charAt(j)>='a' && stringWord.charAt(j)<='z'){
                    stringWord =stringWord.replace(j,j+1, 
                            String.valueOf((char) (stringWord.charAt(j)-32)));
                }else{
                    stringWord =stringWord.replace(j,j+1, " " );
                }
            }
            System.out.println("大小写后的："+stringWord);
            res.append(stringWord).append(" ");
        }
        //去掉最后一个空格
        res.deleteCharAt(n);
        return res.toString();
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    题目二：

    描述
    给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

    思路：

    既然是公共前缀，那我们可以用一个字符串与其他字符串进行比较，从第一个字符开始，逐位比较，找到最长公共子串。

    具体做法：

    step 1：处理数组为空的特殊情况。
    step 2：因为最长公共前缀的长度不会超过任何一个字符串的长度，因此我们逐位就以第一个字符串为标杆，遍历第一个字符串的所有位置，取出字符。
    step 3：遍历数组中后续字符串，依次比较其他字符串中相应位置是否为刚刚取出的字符，如果是，循环继续，继续查找，如果不是或者长度不足，说明从第i位开始不同，前面的都是公共前缀。
    step 4：如果遍历结束都相同，最长公共前缀最多为第一个字符串。
    图示：
    在这里插入图片描述

    package com.company.day02;
import java.util.*;

public class Solution {
    /**
     *
     * @param strs string字符串一维数组
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {

        // write code here
        //第一步：处理空数组,返回空串，竖排数组
        int n = strs.length;
        if(n == 0)
            return "";
        //第二步：遍历第一个字符串的所有位置，取出字符
        //i代表第一个数组的下标，移动的方向是横向右移
        for (int i = 0; i < strs[0].length(); i++) {
            //j代表的数组的容量长度，j移动的方向是向下纵向移动
            for (int j = 1; j < n; j++) {
                //必须先判断长度不足的，然后判断字符不等的
                //条件1：数组中第二个字符串长度刚好等于i 下标，，则证明第二个字符串结束了
                //条件2: 数组中第二个字符串 i 位置的字符和标杆字符串i位置字符不相等
                if(strs[j].length()==i  ||  
                strs[0].charAt(i)!= strs[j].charAt(i) )
                    return strs[0].substring(0,i);//返回到i的截取字符串
            }
        }
        //比较完毕
        return strs[0];
    }

    public static void main(String[] args) {
        //["abca","abc","abca","abc","abcc"]
        Solution solution = new Solution();
        String[] strings = new String[]{"abca","abc","abca","abc","abcc"};

        String s = solution.longestCommonPrefix(strings);
        System.out.println(s);
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    也可以这样判断第一步
    // //第一步，处理空数组或者一个容量的数组
    if(strs.length == 1)
    return strs[0];
    if(strs.length == 0)
    return “”;

    方法二：

    在这里插入图片描述

    import java.util.*;
 
public class Solution {
     //找出两个字符串的最长公共前缀
    public String twoLLongestCommonPrefix (String str1,String str2){   
     //找出短的字符串长度
        int length=str1.length()>str2.length()?str2.length():str1.length();   
        StringBuilder sb=new StringBuilder();
        for(int i=0;i
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    推荐这种做法：

    package day01;

public class Test04 {
    public static void main(String[] args) {
        Test04 test04 = new Test04();
        String[] strs = new String[]{"abc","abx","abca","abc","abcc"};
        String s1 = test04.twoCommonPrefix("abcc", "abx");
        System.out.println(s1);
        String s = test04.longestCommonPrefix(strs);
        System.out.println("最终结果:"+s);
    }
    //横向比较
    public String longestCommonPrefix (String[] strs) {
        if(strs.length ==0)
            return "";
        for (int i = 0; i < strs.length-1; i++) {
            String temp = twoCommonPrefix(strs[i], strs[i + 1]);
            strs[i + 1]=temp;//覆盖掉旧的
        }
        return strs[strs.length-1];
    }
    public String twoCommonPrefix(String str1,String str2){
        //比较两个单独的字符串的公共串
        //取最小长度，少比较几次
        int n = str1.length()>str2.length() ? str2.length() : str1.length();
        for (int i = 0; i < n; i++) {
            if(str1.charAt(i) != str2.charAt(i)){
                return str1.substring(0,i);
            }
        }
        return str1.substring(0,n);//正常循环完毕
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    其他题库:

    package com.company.day02;
/*
* 计算字符串最后一个单词的长度，
* 单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）*/
public class StringTest1 {
    public static void main(String[] args) {
        StringTest1 stringTest1 = new StringTest1();
        System.out.println(stringTest1.stringLen(" i  like   javac"));
    }

    public int stringLen(String s){
        String[] strs = s.split(" ");
       /* System.out.println(strs[strs.length-1]);
        System.out.println((strs[strs.length-1]).length() );*/
        return (strs[strs.length-1]).length() ;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
  • 相关阅读:
    ftp发布服务器
    【问题解决】load_dataset报错An error occurred while generating the dataset
    【Python技巧】字典
    java 类和对象（方法与方法重载）
    神经网络 06(优化方法)
    Vue插槽详解
    opencv入门笔记（二）
    docker-compose采用前后端分离部署vue和springboot项目
    SpringBoot整合Quartz
    Spring Boot 介绍
  • 原文地址：https://blog.csdn.net/weixin_38568503/article/details/127902365